大数据环境下复杂社会网络的社区发现方法研究综述

摘 要：社会化媒体大数据环境下的社区发现研究，是社会网络分析与挖掘领域的一个热门研究方向，已有众多学者提出各种研究方法，但对当前研究工作的进展分析相对较少。首先从局部、全局、节点相似度3个角度讨论社区的定义，然后针对网络的大规模、动态、异构3个特性，分别调研与梳理国内外相关文献，并从采取的主要技术、数据建模方法、可处理的网络规模、网络时序特征4个方面比较与总结其中的代表性方法，分析当前的学术思路与发展动态，最后指出该研究领域存在的挑战及未来可能的研究方向。

关键词：大数据；社区发现；复杂社会网络

DOIDOI：10.11907/rjdk.162505

中图分类号：TP301

文献标识码：A文章编号：1672-7800（2016）012-0164-04

0 引言

社区发现旨在探测复杂社会网络中具有共性特征或紧密关系的群体。该研究能帮助人们从介观（Mesoscopic）的视角分析网络的拓扑结构，理解网络功能，揭示网络中的隐含模式，以及分析预测网络行为。同时，还可以应用在智能推荐、精准营销、个性化服务等诸多领域。因此，社区发现研究具有重要的理论意义和较高的应用价值。社区发现的重要性，吸引了国内外学者的广泛关注。斯坦福大学、康奈尔大学、卡内基梅隆大学、亚利桑那州立大学、清华大学、中科院等国内外许多大学和研究机构都围绕此课题开展了深入研究，取得了一系列重要的研究成果。当前，对社区发现研究的分析与综述工作较少，不利于把握整体脉络及发展趋势。

本文对大数据环境下复杂社会网络的社区发现方法进行综述。首先从三个层面讨论社区定义，然后针对网络的大规模、动态、异构3个特性，阐述与比较已有的社区发现方法，分析现有工作的学术思路与发展动态，最后指出存在的挑战及可能的发展方向。

1 社区定义

社区本身只是一个定性的概念，自提出之日起，关于社区的定量定义就引起了来自不同领域学者们的争议与广泛讨论，直至目前，仍然没有一个被广为接受的定量定义。直观上讲，社区通常被认为是复杂网络中的一些节点组（团），同一组内的节点之间连接相对紧密，组与组之间连边相对稀疏。

当前对社区的定义，可以分为3类：基于局部的社区定义、基于全局的社区定义与基于结构相似度的社区定义[1]：①基于局部的社区定义，只考虑社区内部节点及社区内部节点与外部节点间的联系，而不考虑社区外部节点之间的联系信息。局部社区定义一般会给出一种社区应满足的条件或约束，据此找出网络中能够满足该条件的极大子网络，这些子网络则被称为社区。例如：Palla等[2]提出k-clique（大小为k的clique）社区定义，通过k-clique的滚动得到最终的社区；②基于全局的社区定义，则从网络整体出发，通过网络中的某个性质间接给出社区定义。全局定义方式中最有代表性的社区定义是基于模块度的定义（modularity）[3]。基于模块度的社区定义，以随机网络（代表性的有E-R网络）为参照，依据当前网络与参照网络的偏差来定义社区。即在保证两种网络节点度分布相同的情况下，随机放置节点间的边，若某一个子网络内部的连边数高于其在参照网络中的期望连边数，则认为该子网络为一个社区。基于模块度的社区定义，是当前广为接受的一种社区定义方法；③基于节点相似度的社区定义，以同一社区内的节点相似度较高为指导思想，其基本框架为：首先根据网络拓扑信息计算任意两对节点间的相似度；然后根据节点间的相似度采用层次聚类的方式把节点分成各个组，每个节点归属于与其最相似的组；最终，每个组被视为一个社区[4]。

2 复杂社会网络的社区发现研究进展

在社区发现方面，研究者们提出了许多网络社区发现算法。根据其采取的基本求解策略不同，可以划分为两类[5]：基于优化的方法（Optimization Based Method）和启发式方法（Heuristic Method）。前者将社区发现问题转化为优化问题，通过最优化预定义的目标函数计算网络的簇结构。例如，谱方法（Spectral Method）[6]将网络聚类问题转化为二次型优化问题，通过计算矩阵的特征向量来优化预定义的“cut”函数，文献[7]中也描述了类似工作；启发式方法则是将网络社区发现问题转化为预定义启发式规则的设计问题，已经成功地应用在各种社会网络或交互网络中，如Email网、人类社交网、科学家协作网等。然而，这些算法都具有较大的计算开销，只能应用在规模为数万节点以下的中小规模网络中。

随着互联网的发展及社交媒体的盛行，社会网络的规模不断增大，人们开始探索大规模图的快速社区发现算法。Wakita等[8]给出3种不同的社区规模度量指标，通过控制社区的平衡增长方式，提出了一种改进的CNM算法；Raghavan等[9]提出一种基于标签传播（Label Propagation）的局部社区发现方法，该方法能够将计算过程并行化，其时间复杂度近乎线性，因而能够适用于大规模的网络分析；Ghosh等[10]以“影响力”（任意两个节点之间的路径长度）作为度量，给出一种新的基于全局影响力的社区发现算法；Koutsourelakis等[11]考虑到社区的重叠性现象，提出了基于概率混合模型的社区发现算法；Rohe等[12]基于随机分块模型，给出了面向大规模社会网络的谱聚类方法；Tang等[13-14]将大规模网络的社区发现问题转化为社区核检测问题，提出了“Greedy”和“We BA”算法。

动态性是社会网络最本质的特点之一，研究社区的动态性可以帮助人们发现社区随时间变化的情况，并分析导致变化的机制和原因。Backstrom等[15]通过研究LiveJournal和DBLP数据集，发现实体是否加入社区，社区增长或收缩都取决于网络的拓扑结构；Palla等[16]第一次系统地对动态社区进行了研究，采用（CPM）方法对每个时间片的网络快照抽取社区结构，然后匹配连续时间片的社区结构，给出6种社区的动态演化形态；Tantipathananandh等[17-18]基于图染色理论，将动态网络的社区发现问题转化成颜色匹配问题，给出了社区的动态发现算法；Lin等[19]提出FacetNet框架，该框架的特点是在统一过程中发现社区及其变化过程。该算法解决了多数算法中不能同时发现社区及其变化过程的问题，同时也解决了在同一时刻某一节点只能属于一个社区的问题。但该方法过于依赖社区的数量m，而m取值范围的确定需要由相关专业领域内的知识决定；Chi等[20]利用平滑时序，给出了谱聚类方法的演化版本；Takaffoli等[21]提出通过增量分析来识别动态网络中的社区结构。但该方法的局限性在于假定社区数目是固定的，即新增的节点或边只能在固定的K个社区中进行选择，从而导致社区结构的变化只可能是增大、缩小，而不能体现社区的分裂、合并、诞生及消亡等过程。

[6] WHITE S， SMYTH P. A spectral clustering approach to finding communities in graph[C]. Proceedings of the 5th SIAM International Conference on Data Mining，2005（5）：76-84.

[7] RAVASZ E， SOMERA A L， MONGRU D A， et al. Hierarchical organization of modularity in metabolic networks[J]. Science， 2002， 297（5586）： 1551-1555.

[8] WAKITA K， TSURUMI T. Finding community structure in mega-scale social networks[C]. Proceedings of the 16th International Conference on World Wide Web， 2007： 1275-1276.

[9] RAGHAVAN U， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical review E， 2007， 76（3）： 036106.

[10] GHOSH R， LERMAN K. Community detection using a measure of global influence[M]. Advances in Social Network Mining and Analysis. Springer Berlin Heidelberg， 2010： 20-35.

[11] KOUTSOURELAKIS P， ELIASSIRAD T. Finding mixed-memberships in social networks[C]. AAAI Spring Symposium： Social Information Processing， 2008： 48-53.

[12] ROHE K， CHATTERJEE S， YU B. Spectral clustering and the high-dimensional stochastic blockmodel[J]. The Annals of Statistics， 2011： 1878-1915.

[13] WANG L， LOU T， TANG J， et al. Detecting community kernels in large social networks[C]. Proceedings of the IEEE 11th International Conference on Data mining， 2011： 784-793.

[14] TANG J， SUN J， WANG C， et al. Social influence analysis in large-scale networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2009： 807-816.

[15] BACKSTROM L， HUTTENLOCHER D， KLEINBERG J， et al. Group formation in large social networks： membership， growth， and evolution[C]. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2006： 44-54.

[16] PALLA G， BARABSI A， VICSEK T. Quantifying social group evolution[J]. Nature， 2007（446）： 664-667.

[17] TANTIPATHANANANDH C， BERGER-WOLF T， KEMPE D. A framework for community identification in dynamic social networks[C]. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2007： 717-726.

[18] TANTIPATHANANANDH C， BERGER-WOLF T. Constant-factor approximation algorithms for identifying dynamic communities[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009： 827-836.

[19] LIN Y R， CHI Y， ZHU S， et al. Analyzing communities and their evolutions in dynamic social networks[J]. ACM Transactions on Knowledge Discovery from Data， 2009， 3（2）： 1-31.

[20] CHI Y，SONG X，ZHOU D，et al.Evolutionary spectral clustering by incorporating temporal smoothness[C]. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2007： 153-162.

[21] TAKAFFOLI M， RABBANY R， ZAANE O R. Incremental local community identification in dynamic social networks[C]. Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. ACM， 2013： 90-94.

[22] TANG L， LIU H， ZHANG J， et al. Community evolution in dynamic multi-mode networks[C]. Proceeding of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2008， 677-685.

[23] TANG L， WANG X， LIU H. Community detection via heterogeneous interaction analysis[J]. Data Mining and Knowledge Discovery， 2012， 25（1）： 1-33.

[24] SHEN H， CHENG X， WANG Y， et al. A dimensionality reduction framework for detection of multiscale structure in heterogeneous networks[J]. Journal of Computer Science and Technology， 2012（2）： 341-357.

[25] ANANDKUMAR A， GE R， HSU D， et al. A tensor approach to learning mixed membership community models[J]. Journal of Machine Learning Research， 2014， 15（1）： 2239-2312.

[26] LIN Y R， SUN J， CASTRO P， et al. MetaFac： community discovery via relational hypergraph factorization[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2009：527-536.

[27] LIN Y， SUN J， SUNDARAM H， et al. Community discovery via metagraph factorization[J]. ACM Transactions on Knowledge Discovery from Data， 2011， 5（3）：1284-1310.

[28] SUN Y， TANG J， HAN J， et al. Community evolution detection in dynamic heterogeneous information networks[C]. The 8th Workshop on Mining and Learning with Graphs， 2010：137-146.

[29] SUN Y， TANG J， HAN J， et al. Co-evolution of multi-typed objects in dynamic star networks[J]. IEEE Transactions on Knowledge & Data Engineering， 2014， 26（12）： 2942-2955.