◆刘 岩 顾益军 张大瀚

（中国人民公安大学网络安全保卫学院 北京 102623）

基于节点相似度的个人网络社交圈发现算法改进研究

◆刘 岩 顾益军 张大瀚

（中国人民公安大学网络安全保卫学院 北京 102623）

随着互联网和在线社交平台的飞速发展，社会网络开始发展壮大起来，针对社会网络的研究也变得越来越热门。特别是在大数据时代，社会网络研究的价值和意义也将越来越大。个人网络是一种特殊的社会网络，针对个人网络的社交圈发现算法研究意义重大。各种社交平台基本都允许用户将其朋友手动划分到不同的社交圈中，但是对个人网络社交圈进行自动划分的方法研究十分稀少，不断变庞大、变复杂的个人网络致使对其社交圈发现算法研究的难度也在不断提高。Julian等人于2012年首先提出了基于概率模型的个人网络社交圈发现算法（DSCEN算法），实验证明该算法可以有效发现个人网络中的社交圈，并允许社交圈存在重叠、嵌套。本文在研究DSCEN算法的基础上，加入节点相似度因素对算法进行改进，并同时考虑属性相似度和拓扑相似度保证节点相似度的准确性。通过实验验证，改进后的算法具有更好的效果。

个人网络；社交圈发现；DSCEN算法；节点相似度

0 引言

在现实生活中，人与人之间进行着各种各样的活动，产生多种多样的联系，并且通过这些活动和联系形成了复杂多样的社交网络。我们将社会个体通过活动和联系形成的相对稳定的网络称为社会网络[1]。随着互联网的发展，特别是以Facebook、Twitter、QQ、微博、微信等为代表的在线社交平台的兴起，使得社会网络变得复杂多变，动辄成千上万的网络节点和连接给社会网络的分析带来了巨大的挑战[2]。

图1 个人网络示意图

个人网络是指以一个独立的节点（即个人）为中心，包含其所有相邻节点和他们之间的连接，由此形成的网络为个人网络。个人网络的特点就是在网络中有一个节点为中心，网络中的其他所有节点都与该节点存在连接，如图1所示即为一个个人网络（其中698号节点为中心节点）。现实社会中，每个人都不是一个孤立的个体，而是总会与其他人保持关联，这样每个人都会有自己的社交网络，并且随着人类活动的推进，个人网络也在时刻发生着改变。特别是在互联网已经深入到人类生活方方面面的信息时代，随着各种在线社交平台的兴起、壮大，传统的社交模式正经历着翻天覆地式的变革，个人网络开始变得越来越复杂。

虽然各种在线社交平台基本都会提供社交圈的划分功能，对用户维护自己的社交圈和个人网络起到了巨大的作用。但其社交圈的划分基本上是由用户手工划定，费时费力，并且在个人网络不断变化的同时，社交圈的划分不能做到及时自动更新。同时，个人网络的社交圈发现具有很大的研究价值，主要有以下几点：[3]

（1）有助于用户对自己的社交圈和个人网络的维护和及时更新；

（2）有助于深入理解个人网络的拓扑结构和本质，发现其中的隐藏规律，预测网络行为，分析网络的发展过程，从而对个人网络的内部结构有更深刻直观的了解；

（3）有助于深入探索个人网络中节点之间的逻辑关系，展现网络中节点的聚集情况；

（4）公安机关对个人网络中社交圈的分析和发现可以充分准确的挖掘社会个体尤其是犯罪嫌疑人的个人信息和社交网络，进而发现犯罪团伙的组织架构，给破案带来极大的帮助。

为此，本文将在前人的研究基础上，提出一种针对个人网络的社交圈发现算法，并利用该算法有效的得到个人网络中的各个社交圈。该算法发现的社交圈模型应具有以下三点性质：[4]

（1）同一社交圈内的各个节点必须有相似的性质或属性；

（2）不同社交圈应该是由不同的性质或属性形成的；

（3）社交圈应该允许重叠、嵌套现象发生。

1 DSCEN算法

目前，社区发现算法的研究比较多，但针对个人网络的社交圈发现算法研究相对较少，个人网络是一种特殊的社会网络，有着其特有的性质，在社交圈发现过程中需要进行特定的研究。Julian等人于2012年提出了个人网络的社交圈发现算法（DSCEN算法）[4]，首先关注并研究了个人网络的社交圈发现算法。2014年，Julian等人采用MCMC方法对DSCEN算法进行改进，提出MCMCS_SCD算法[5]，大大降低了时间复杂度。黄佳鑫等人在MCMCS_SCD算法的基础上提出SCD_MCMCS_LCD算法[6]，加入局部模块度和节点间紧密度因素，降低了算法时间复杂度的同时也提高了算法的准确度。本文将着重研究DSCEN算法，在该算法的基础上加入节点相似度因素，提高算法的准确度。

在DSCEN算法中，首先定义个人网络),(EVG=，其中V指节点的集合，E指边的集合。接着定义G中任意两个节点x、y之间存在连接的概率，公式如下：

其中kθ表示社交圈kC的特征向量，),(yxφ表示节点x、y之间的属性向量。由公式（1），可得到在社交圈集为C情况下关于G的对数似然函数，即公式（2）：

该算法的最终目的是使公式（2）最大，这样就可以保证划分的社交圈集C最优。从而将个人网络G的社交圈识别问题转化为求对数似然函数即公式（2）的最大值问题。

在社交圈识别过程中，为了求得公式（2）的最优值，通常在给定社交圈集kCC（即除kC外的其他社交圈集）条件下，求kC的最优值，公式如下：

在对社交圈kC的kα值和特征向量kθ进行优化时采用了L-BFGS算法，这是一种典型的拟牛顿法[10]，分别对kθ和kα进行求偏导，公式如下：

2 对DSCEN算法的改进

在DSCEN算法中，根据公式（1）我们可以看出，在定义G中两个节点间存在边的概率时，仅考虑了G的社交圈划分以及节点间的属性向量、社交圈的特征向量三方面的因素，而对两个节点间的其他属性考虑较少，特别是对节点间存在边的概率影响较大的节点相似度因素并未考虑在内。

在社会网络分析中，节点相似度是用来衡量节点与节点之间相似程度一个重要指标，我们认为，两个节点的相似度越高，节点之间存在连接的可能性也就越大，即节点间存在连接的概率应与节点相似度成正比[11]。所以公式（1）可以进行如下改进：

其中，),(yxs表示节点x与节点y的相似度。在社会网络分析中，两节点的相似度不仅与这两个节点的属性相关，还与这两个节点所处的局部网络环境相关，因此，在分析两个节点的相似度时，不能单一地考虑节点属性或节点所处的环境因素，而应该将能影响节点相似度的因素进行综合考虑，这样得出的节点相似度才能越接近真实值。根据节点属性和局部网络环境因素，定义公式如下：

其中),(yxfs表示节点x和y之间的属性相似度，),(yxts表示节点x和y的拓扑相似度[12]。在计算两节点的属性相似度时，用余弦相似度来计算[13]。在计算两个节点之间的拓扑相似度时，用Jaccard相似度来计算[14]。

其中N（x）和N（y）表示节点x和y的邻居节点，Jaccard相似度表明，当两个节点拥有的共同邻居在两节点所有邻居中所占的比重越大时，这两个节点的相似度就越高[15]。通常情况下，节点x的邻居节点不包含节点本身x，这就导致那些相连但没有公共邻居节点的节点相似度为0，可以将节点本身包括在它们的邻居节点中来进行纠正。

由以上的分析，可推导出在DSCEN算法中公式（2）改进如下：

公式（4）、（5）可改进如下：

公式（3）改进如下：

对公式（6）、（7）的改进如下：

3 实验结果与分析

3.1 算法的评估指标

在DSCEN算法中，用平衡误差率[4]（Balanced Error Rate，BER）和1F分数[4]作为指标来评估算法的准确度，当算法预测的社交圈集为，真实社交圈集为时，平衡误差率和1F分数的公式分别如下：

由于预测的社交圈个数与真实的社交圈个数之间可能存在差异，在进行实验评估时，首先需要对预测的社交圈和真实的社交圈进行线性匹配，找到预测社交圈集C和真实社交圈集的一个映射f，通过公式（20）和公式（21）来分别计算预测社交圈集C和真实社交圈集的（1-BER）值和F1分数。

3.2 实验数据

实验数据采用斯坦福大学SNAP（Stanford Network Analysis Project）小组提供的Facebook数据集，该数据集共包含了10个用户的个人网络，总共4039个用户和193个社交圈，平均每个用户拥有19个社交圈，每个社交圈平均有22个好友。本文中的实验选取了其中4个规模不同的个人网络，其中1号个人网络中有348个用户节点，2号个人网络中有228个用户节点，3号个人网络中有160个用户节点，4号个人网络中有171个用户节点。

3.3 实验方案

本论文将采取对比实验的方法。实验中，首先进行两组对比实验，用以确定相似度公式中参数β的值。这两组实验分别设置K=3和K=5，然后取}1,75.0,5.0,25.0,0{=β这五个数值进行实验，比较各组实验结果，确定最优β值。

在确定β值后，接下来就需要进行实验分析改进后的DSCEN算法的效果。对这4个不同的个人网络，分别取}15,10,3{=K进行实验，将改进后算法的实验结果与原DSCEN算法的实验结果进行分析比较。在实验中，除进行对比分析需要修改的实验参数外，其他的实验参数均采用原DSCEN算法中的推荐参数。

3.4 实验结果和分析

图2和图3是当K=3，β取不同值时，对不同的个人网络进行社交圈识别后的1F分数和（1-BER）的结果。图4和图5是当K=5，β取不同值时，各网络的1F分数和（1-BER）的结果。从这四个图中，可以明显地看出当β取不同值时对实验结果将产生重要的影响，并且对于不同的个人网络，不同的β值对算法准确性的影响也是各不相同的。例如当K=5时，对于3号个人网络来说，β=0.75时算法的准确性更高，而对于4号个人网络而言β=0.25时算法准确性更高。

综合考虑实验中不同的个人网络，计算各个网络的平均1F分数和平均（1-BER）值，可以发现：对于K=3和K=5这两组实验，当β=0.25或0.75时，实验结果中的平均1F分数和（1-BER）都比较高，即算法的准确性更高。需要注意的是，这并不是肯定的结果，由于个人网络千差万别，针对特定个人网络的社交圈划分，都应有一个最优的β值，这里采取平均效果较好的β=0.25和0.75进行接下来的对比实验。

图2 β取不同值时1F分数比较（K=3）

图3 β取不同值时（1-BER）比较（K=3）

图4 β取不同值时1F分数比较（K=5）

图5 β取不同值时（1-BER）比较（K=5）

确定了β值后，接下来需要进行实验比较分析改进后的DSCEN算法的性能。根据实验方案，分别取}15,10,3{=K，进行实验，将改进后算法的实验结果与原DSCEN算法的实验结果进行比较。图6、图7、图8为实验结果图。从图中，可以明显地观察到对于大部分的个人网络而言，改进后的算法的不论是在1F分数还是在（1-BER）上都有了一定的提升，但由于改进后的算法准确度很大程度上需要依赖于β值的设置和优化。同时由于考虑到个人隐私问题，用户在社交平台上注册的属性信息往往是不完整并存在虚假信息情况，致使在计算节点的属性相似度时存在误差，进而影响了整个算法的准确度。所以，在个别网络中也存在改进后的算法准确度低于原算法的情况。但是从总体上来看，即从平均结果来看，改进后的算法准确度较原算法还是有一定提升的。

图6 K=3时改进后算法与DSCEN算法的性能比较

图7 K=10时改进后算法与DSCEN算法的性能比较

图8 K=15时改进后算法与DSCEN算法的性能比较

4 结束语

随着互联网的快速发展，在线社交平台的不断壮大，个人网络已经发生了翻天覆地的变化，从线下到线上，个人网络变得越来越庞大，也越来越复杂，但是针对个人网络的研究甚少，尤其是对个人网络的社交圈发现的研究更少。

本文主要研究了针对个人网络的社交圈发现算法——DSCEN算法，并在此基础上提出了改进方案，综合考虑了节点间的相似度因素。通过实验，验证了改进后的算法在社交圈发现的准确性上比原算法有所提高。

在实验中，改进后的算法准确度很大程度上依赖于β的取值情况，而对于不同的个人网络，最优β值往往又是不相同的，以后还需要对最优β值的确定做进一步的研究讨论。

[1]刘军．社会网络分析导论[M]．社会科学文献出版社，2004．

[2]孙迎友．复杂动态网络的状态估计方法研究[D]．南京邮电大学，2014．

[3]辛佰惠．基于MMSB的加权社交网络社团发现算法研究[D]．电子科技大学，2014．

[4]McAuley J J,Leskovec J．Learning to Discover Social Circles in Ego Networks[C]//NIPS,2012．

[5]Mcauley J,Leskovec J．Discovering social circles in egonetworks[J]．ACM Transactions on Knowledge Discovery from Data（TKDD），2014．

[6]黄佳鑫，郭红，郭昆．基于影响簇选择模型和 MCMC采样的社交圈子识别算法[J]．福州大学学报（自然科学版），2015．

[7]班艳丽，柴乔林，王琛．基于能量均衡的 ZigBee 网络树路由算法[J]．计算机应用，2008．

[8]Kolmogorov V，Rother C．Minimizing nonsubmodular functions with graph cuts-a review[J]．Pattern Analysis and Ma chine Intelligence，IEEE Transactions on，2007．

[9]Boros E，Hammer P L．Pseudo-boolean optimization[J]．Discrete applied mathematics，2002．

[10]Nocedal J．Updating quasi-Newton matrices with limit ed storage[J]．Mathematics of computation，1980．

[11]张健沛，姜延良．一种基于节点相似性的链接预测算法[J]．中国科技论文，2013．

[12]王玙，高琳．基于社交圈的在线社交网络朋友推荐算法[J]．计算机学报，2014．

[13]张沪寅，温春艳，刘道波，等．改进的基于本体的语义相似度计算[J]．计算机工程与设计，2015．

[14]王林澍．社会网络中的链接分析与预测研究[D]．哈尔滨工程大学，2013．

[15]张宏志．社会网络中社团发现算法研究[D]．湘潭大学，2013．

[16]赵一甲．社会网络中社团发现算法研究[D]．电子科技大学，2013．