大规模社交网络重叠社区发现技术综述

王李冬,张　赟

(1. 杭州师范大学钱江学院, 浙江 杭州 310036；2. 浙江传媒学院,浙江 杭州 310018)

大规模社交网络重叠社区发现技术综述

王李冬1,张赟2

(1. 杭州师范大学钱江学院, 浙江 杭州 310036；2. 浙江传媒学院,浙江 杭州 310018)

摘要：随着社交网站的发展,大规模、结构复杂的社交网络应运而生,发现大规模社交网络的潜在结构是当前数据挖掘领域的研究难点.针对近几年出现的4种重叠式社区挖掘算法(SLPA,TopGC,SVINET,UEOC),详细分析各方法的设计原理,概括出各算法的特点和应用范畴.并将各算法应用于具备先验社区知识的多种大规模社交网络,通过多种性能评价指标进行定量对比分析.结果表明,SLPA和TopGC分别在性能和效率上取得最优,但所有算法无法同时在效率和性能上取得理想效果.

关键词：社交网络；重叠社区挖掘；SLPA；TopGC

0概述

随着当前互联网载体下人类互动和沟通需求的扩展,社交网络已经逐渐影响人们的生活.社交网络的基本载体为用户,如何对这些大规模用户数据进行分析并发现一些动向,从而作为营销时代价值创造的前提分析工具,是当前研究的热点之一.网络社区挖掘方法为解决此问题提供了一些策略.

社交网络具备六度分割理论,属于“小世界”网络.借助复杂网络原理,对社交网络的社区分析一般借助于当前复杂网络的社区挖掘方法,如基于最优化的方法、基于启发式规则方法等.传统社区挖掘算法将网络划分为若干个互不连接的簇,每个节点都隶属于唯一的社区.目前多数现实世界网络都具备重叠社区,同时包含权重边.也就是说,在社交网络中,每个用户往往会依据不同的划分规则隶属于不同的社区,如学校、家人以及朋友等.可见,挖掘社交网络中的重叠社区结构更具有现实意义.当前重叠社区挖掘已经具备一定的研究基础,但在实际应用中社交网络一般包含上千至上百万用户节点,网络结构复杂,使得大规模社交网络的社区挖掘变成一个难题,普通的社区挖掘算法无法取得满意的效果.此外,很多研究者认为社区代表紧密连接的节点群,而且群与群之间属于稀疏连接,目前存在多种社区定义都符合该特性,但一直缺乏能被研究者广泛接受的正式定义[1],这一点更是加大了社交网络社区发现的难度.现有研究不能满足大规模网络潜在模式发现的需求,还需要研究者借鉴已有的技术和模型,为大规模社交网络的重叠社区结构发现问题设计更好的模型和算法.

本文对当前最新的重叠社区挖掘主流算法进行了梳理,详细分析这些主流算法的设计动机和原理,并利用已经具备先验社区结构的社交网络数据集,针对不同方法的特点和性能进行定性和定量的对比分析,为该领域的研究者利用和改进这些技术提供帮助.

1相关工作

近几年已有相关学者针对社区挖掘算法进行综述性研究,但主要针对独立社区挖掘.Fortunato[1]和Coscia等[2]针对独立和重叠社区挖掘算法作出了详尽的对比.Fortunato根据方法的原理进行分类描述,Coscia等则根据社区的不同定义进行分类描述.Malliaros等[3]针对有向网络图将方法进行归类,并提出基于方法学(methodology-based)的社区挖掘算法分类系统.除了理论方面的整理与分析,也有部分研究者将多种社区挖掘算法进行性能评价.Orman等[4]将8种非重叠社区挖掘算法应用于多种合成网络图,并将取得的实验结果和识别的社区结构特性进行整理与分析.柴变芳等[5]对基于概率模型的大规模网络社区挖掘算法按照模型参数求解策略进行归类,并应用于多种社交网络,最后利用实验结果对各种方法进行定量的对比和分析.Xie等[6]提炼出14种重叠社区挖掘算法,并将算法分成5类,分别为团过滤方法(Clique Percolation Method),边分割(Line Partitioning),基于代理和动态算法(Agent-based and Dynamic Algorithms)[7],局部扩展与优化(Local Expansion and Optimization)[8]以及模糊检测(Fuzzy Detection)[9],最终面向人工合成网络以及真实社交网络进行实验分析.

可见,现有的重叠社区挖掘算法主要面向人工合成网络以及部分社交网络进行设计与实验,而这些社交网络都不具备先验社区知识,无法验证这些算法的真正性能.本文针对多种最新重叠社区挖掘算法(发表于2010年后)进行详细的算法原理分析并面向多种大规模社交网络进行实验.与其它综述性研究不同的是,本文涉及的大规模社交网络具备先验社区知识,而且部分算法间的比较分析并未出现在其它综述文献中.

2算法概述

团过滤算法(Clique Percolation Method, CPM)作为经典的重叠社区挖掘算法之一,通过找到网络中的最大团,并利用共享节点将团进行合并,最坏情况需要指数级运行时间.本文利用CPM算法中的CFinder作为基准算法,与SLPA,TopGC,SVINET,UEOC等方法进行比较分析.

2.1SLPA

SLPA(Speaker-listener Label Propagation Algorithm)[10]作为标签传播算法(Label Propagation Algorithm, LPA)的扩展,主要应用于重叠型社区挖掘,通过传播代表社区类别归属的标签以达到社区发现的目的.首先,为所有节点指定一个唯一的标签,即在初始化状态,所有节点属于不同的社区.然后,选择一个节点作为listener,标签从listener传播到周围的speaker(邻居节点).LPA和SLPA算法的最大区别在于标签的更新方式不同.在LPA中,对当前节点以出现次数最多的标签进行更新.在SLPA中,记录每一个节点在每次迭代过程中的历史标签序列(例如迭代T次,则每个节点将保存一个长度为T的序列).当迭代停止后,对每一个节点历史标签序列中各(互异)标签出现的频率进行统计,按照某一给定的阀值r∈[0,1]过滤掉那些出现频率小的标签,剩下的即为该节点的标签.文献[7]证实当T>20时,最后的结果将趋于稳定.最终,具备相同标签的节点被划分为同个社区.如果一个节点具备多个标签,那么该节点隶属于多个社区.可见,阈值r越小,最终被发现的重叠社区个数越多.若r≥0.5,那么该算法就回归为非重叠社区挖掘.

2.2TopGC

TopGC (Top Graph Clusters)算法[11]属于基于概率聚类的社区挖掘算法，其主要思想是找到邻居节点中高度重叠的节点集合,并将这些节点组成社区结构.该算法通过MinHash技术实现.MinHash技术主要用于快速估算两个集合的相似度,也可应用于大规模聚类.为了简化计算,最初需要剪枝阶段(pruning phase)用于判定哪些节点属于最强蔟(社区).该算法中蔟的强度定义为

(1)

其中,wij表示节点vi和vj之间边的权重,|C|表示蔟C的节点个数.

首先,该算法为网络中的所有节点选取m种排列,记为π1,…,πm；其次,为每个节点生成Minhash值,记为mh1,…,mhm,其中mhi代表其邻居节点集合Nj中在πi排序末尾的节点；再次,产生l个随机数,l∈[1,…，m],每个节点的Minhash签名由一系列mhl1,…,mhll构成；最后计算两个节点具备相同Minhash的概率,记为(|Ni∩Nj|/|Ni∪Nj|)l,具备相同Minhash的节点被认定为同个社区.

2.3SVINET

SVINET[12]利用混合隶属度随机块模型(Mixed-membership Stochastic Block Model,MMSB)进行重叠社区挖掘,属于概率模型方法.MMSB为SBM(Stochastic Block Model)模型[13]的变型.SBM模型是由社会科学家提出的一种可更好拟合实际网络的随机图模型,能识别体现网络中观结构的类间链接模式,且一个节点可存在于多个社区.

在MMSB模型中,每个节点被分配长度为K的社区成员向量θ,K代表网络中的社区个数.给定一个可观察网络,该网络的社区结构可以通过计算后验概率进行估计,即p(θ,z|y),z表示社区标识向量,y表示可观察网络.由于该后验概率无法直接计算,用mean-field变分簇q(θ,z)近似后验分布,并采用随机变分进行参数估计,具体过程如下:

1)从节点对集合中抽样边集合S；

2)根据每对节点(i,j)∈S,计算S中每对节点的最优局部变分参数φi→j和φj→i；φi→j和φj→i为z变分参数.

3)根据局部变分参数更新γ.γ为θ变分参数,描述每个节点的社区成员向量θ的后验分布.

2.4UEOC

UEOC算法[7]分成UC(Unfolding Community)和EC(Extracting Community)两个阶段.在UC阶段,利用随机游走原理,首先选取目的节点,并针对每个节点计算初始节点到目的节点的l-step转移概率值.假设T代表转移矩阵,Ti→j代表从结点i出发游走到邻居节点j的概率值,则l-step概率值按照下式进行迭代计算:

(2)

然后,针对每个节点到目的结点的转移概率值从大到小进行排序,得到排序好的节点序列.

在EC阶段,根据UC阶段获得的排序好的节点序列L,为该序列设置特定的切割位置(cut position)就可获得社区结构.切割位置需要根据电导值计算获取,某一社区结构的电导值表示为社区内节点的度的总和与该社区的外连接边的个数的比值.首先,针对节点序列中的每个节点计算电导值,而切割点则对应于最小电导值.然后,将切割点之前的所有节点序列构成一个社区.如此反复,直到序列L中的所有节点都已经划分到特定社区中.

为了给上述算法作定性比较和分析,本文梳理了各算法的设计原理、复杂度以及应用范畴等记录于表1中.其中,SLPA,TopGC以及UEOC算法可以同时用于重叠社区挖掘和非重叠社区挖掘.

表1　重叠社区挖掘算法

3实验比较与分析

3.1实验数据集

本文采用SNAP(http://snap.stanford.edu/data)提供的已知先验社区结构的大规模社交网络数据集进行实验.

Facebook:节点代表用户,节点之间的边表示两个用户具备相互关注的关系.社区结构定义为用户的社交圈(Social Circles).

LiveJournal, Orkut, Youtube:节点代表用户,边代表用户之间的好友关系.社区结构通过用户创建的组进行定义.

真实社交网络往往不具备好的社区结构(除了Facebook网络外),因此需要对上述网络进行预处理.好的社区结构具备较高的内部稠密度(internal density),本文根据该值选取前5 000个社区进行实验,移除其余社区中的节点,同时移除不属于任何社区结构的节点.最终的实验数据中,Facebook网络包含4 039个节点,88 234条边；Youtube网络包含12 091个节点,29 775条边；LiveJournal网络包含44 093个节点,871 409条边；Orkut包含297 691个节点,7 747 026条边.

3.2实验结果与讨论

下面将上述算法应用到真实社交网络上验证其性能与运行效率.实验环境为:处理器 Intel i5-4430 3.0 GHz,内存16 G,操作系统为Linux.

图1　重叠社区挖掘算法性能比较Fig. 1　Performance metrics for overlapping community detection

图1给出了各算法在不同数据集上的运行效果,利用Recall、Precision、F-measure和NMI 4种性能指标进行衡量,每种算法在各数据集上运行5次.需要注意的是,如果部分算法在特定数据集上无法于规定时间内(4 h)完成,则程序终止,实验结果不作记录.从图中数据可得,TopGC相比其它算法在Recall、F-measure和 NMI上都处于劣势.根据TopGC算法中的评分(scoring)函数,该算法仅识别Top社区,造成很多节点并不处于任何社区结构中,使得识别结果中存在很多的假阴性(false negative),导致最终获得较低的Recall值和F-measure值.相比各算法,SLPA获得的结果最好,这与文献[4]中的效果相符合.

为了进一步比较各算法的社区挖掘效果,将每个算法发现的社区和先验社区结构进行相似度计算.假定两个算法A和B,则这两种算法的社区挖掘结果的相似度计算如下[3]:

(3)

上式中,SA(c)代表算法A的挖掘结果中属于社区c的节点集合.表2给出了相似度比较的实验结果.由表中数据可得,大多数算法面向Youtube网络的挖掘结果都与先验社区结构相差较大,说明该网络本身不具备很好的社区结构.TopGC针对多数网络的社区发现结果与其相应的先验社区结构差别较大,可见该算法的挖掘效果并不理想.这主要是由于TopGC算法的出发点是发现具备紧密连接的社区,使得最终发现的社区数目往往小于真实社区数目.

表2　各算法社区发现结果与先验社区结构的相似度

此外,本文测试了上述算法在大规模社交网络上的运行效率.鉴于Facebook网络规模较小,在时间运算中不作为实验数据.本文用这些算法本身提供的源码进行计算,不考虑编译环境对最终运行结果造成的影响.将每种算法运行5次,最后将均值记录于表3中.由表3数据可得,TopGC的运行速度最快,CFinder和SVINET算法在LiveJournal和Orkut数据集上无法于4 h内完成.可见,CFinder和SVINET并不适合大规模尺度的社交网络社区挖掘.SLPA虽然能取得较好的性能(表2),但面对规模较大的社交网络需要花费较长的时间.

表3　各算法运行时间比较

4总结与讨论

当前社交网络发展迅速,对网络数据进行社区挖掘可为多领域带来较高的经济效益.本文对近几年出现的大规模重叠社区挖掘算法(SLPA,TopGC,SVINET,UEOC)从理论上进行分析,并应用于多种具备先验社区结构的社交网络(Facebook,Youtube,LiveJournal,Orkut).实验结果表明:SLPA算法具备较好的挖掘性能,TopGC算法效率最优.针对大规模社交网络,目前缺乏能同时在算法性能和算法效率上都较为理想的重叠社区发现算法.未来可以着重在以下几方面展开研究:

1)针对性能较优的算法,融合大数据处理技术提高方法的运行效率，如基于云计算平台的算法改进等；

2)社交网络往往缺乏先验社区知识,未来的算法应着重面向社区个数未知的网络结构发现任务；

3)将网络的链接信息融合进社区挖掘算法中；

4)现有的大规模社交网络挖掘方法研究还停留在初步阶段,如何将这些方法和社交媒体的服务相结合,利用用户的反馈进行模型优劣的评价,是亟待解决的问题.

参考文献:

[1] FORTUNATO S. Community detection in graphs[J]. Physics Reports,2010,486(3/4/5):75-174.

[2] COSCIA M, GIANNOTTI F, PEDRESCHI D. A classification for community discovery methods in complex networks[J]. Statistical Analysis and Data Mining,2011,4(5):512-546.

[3] MALLIAROS F D, VAZIRGIANNIS M. Clustering and community detection in directed networks: a survey[J]. Physics Reports,2013,533(4):95-142.

[4] ORMAN G K, LABATUT V, CHERIFI H. Comparative evaluation of community detection algorithms: a topological approach[J]. J Stat Mech Theor Exp,2012,2012(8):P08001.

[5] 柴变芳,贾彩燕,于剑.基于概率模型的大规模网络结构发现方法[J].软件学报,2014,25(12):2753-2766.

[6] XIE J R, KELLEY S, SZYMANSKI B K. Overlapping community detection in networks: the state-of-the-art and comparative study[J]. ACM Computing Surveys,2013,45(4):43.

[7] JIN D, YANG B, BAQUERO C, et al. A markov random walk under constraint for discovering overlapping communities in complex networks[J]. J Stat Mech Thero Exp,2011,2011(5):P05031.

[8] HAVEMANN F, HEINZ M, STRUCK A, et al. Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels[J]. J Stat Mech Theor Exp,2011,2011(1):P01023.

[9] LATOUCHE P, BIRMELE E, AMBROISE C. Overlapping stochastic block models with application to the french political blogosphere[J]. The Annals of Applied Statistics,2011,5(1):309-336.

[10] XIE J, SZYMANSKI B K. Towards linear time overlapping community detection in social networks[M]//TAN P N, CHAWLA S, HO C K,et al. Advances in Knowledge Discovery and Data Mining. Berlin:Springer,2012:25-36.

[11] MACROPOL K, SINGH A. Scalable discovery of best clusters on large graphs[J]. Proceedings of the VLDB Endowment,2010,3(1/2):693-702.

[12] GOPALAN P K, BLEI D M. Efficient discovery of overlapping communities in massive networks[J]. Proc Nati Acad Sci,2013,110(36):14534-14539.

[13] CHAI B F, YU J, JIA C Y, et al. Combining a popularity-productivity stochastic block model with a discriminative-content model for general structure detection[J]. Physical Review E. Statistical, Nonlinear, and Soft Matter Physics,2013,88(1):012807.

Overlapping Community Detection in Large-scale Social Networks

WANG Lidong1, ZHANG Yun2

(1. Qianjiang College, Hangzhou Normal University, Hangzhou 310036, China； 2. Zhejiang University of Media and Communications,Hangzhou 310018, China)

Abstract:The growth of the online social websites brings up the development of massive social networks with the characteristics of large-scale and complex structure. Identifying the latent structure in large-scale networks is a difficult task in data detection domain. This review analyzes the design principles of four algorithms (SLPA, TopGC, SVINET, UEOC) that are recently published, and summarized their characteristics and fields of application. Finally, these methods are evaluated on large-scale social networks with known ground-truth communities. The results show that SLPA and TopGC obtain the best results on effectiveness and efficiency respectively, but all methods cannot achieve ideal results on both effectiveness and efficiency.

Key words:social network； overlapping community detection； SLPA； TopGC

收稿日期：2015-10-27

基金项目：浙江省自然科学基金项目(LQ14F020008,LY14F020050).

通信作者：王李冬(1982—),女,副教授,博士，主要从事数据挖掘、信息检索研究.E-mail:violet_wld@163.com

doi:10.3969/j.issn.1674-232X.2016.03.020

中图分类号:TP391

文献标志码:A

文章编号:1674-232X(2016)03-0331-06