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

赵中英+李超

摘 要：社会化媒体大数据环境下的社区发现研究，是社会网络分析与挖掘领域的一个热门研究方向，已有众多学者提出各种研究方法，但对当前研究工作的进展分析相对较少。首先从局部、全局、节点相似度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个社区中进行选择，从而导致社区结构的变化只可能是增大、缩小，而不能体现社区的分裂、合并、诞生及消亡等过程。

在真实世界的社交网络中，往往涉及多种实体（角色），并且实体间的关系具有多样性。Lei Tang等[22]提出了在动态异构网络中发现社区的方法，该方法在谱聚类框架基础上提出了一个整体模型，该模型能在动态异构网络中辨别社区的变化。针对异构网络复杂的交互关系，Tang等[23]给出了4种同构社区的集成策略，提出基于异构关系分析的社区发现方法；Shen等[24]将异构网络中的社区发现问题转化为基于主成分分析（PCA）的降维问题，提出了基于拉普拉斯矩阵及模块度矩阵分解方法；Anandkumar等[25]提出一种基于张量分解的异构社区发现方法；Lin等[26]提出一种基于关系超图分解的异构社区发现方法。近几年，有学者开始融合网络的动态性和异构性，尝试发现动态异构网络中的社区结构；Lin等[27]提出一个基于Metagraph分解的动态社区发现及演化分析方法；Sun等[28-29]利用狄利克雷过程对隐含社区数目的分布进行先验估计，结合平滑性假设，提出一种过程混合模型的生成模型来模拟社区生成，利用该模型可以在每个时间点自动发现能较好解释当前网络和历史网络特征的社区数目和结构，并设计了一个基于吉布斯采样的方法进行模型学习和推断。

3 社区发现方法总结比较与发展动态分析

以下将从采用的主要技术、数据建模方法、可处理的网络规模、网络时序特征4个方面对代表性方法进行总结与比较，如表1所示。

根据表1及对已有工作的论述，可以看出国内外学者在社区结构研究方面的学术思路及发展动态：①从社会网络的规模看，在社区结构研究的初级阶段，相关研究工作都是面向中小规模的社会网络开展的。随着信息技术的发展，网络规模越来越大，节点数量从数万迅速增长到百万规模、十亿规模，人们开始研究社区发现算法的可扩展性、并行性，或者直接从算法本身考虑，设计适用于大规模网络的社区发现算法；②从社会网络的建模看，最初的社区发现算法都是以简单图建模为基础，即将社会网络形式化表示为一个只包含节点和边的图。随着相关研究的日益成熟，人们开始考虑网络中的其它信息，例如，节点与边的异构性、节点属性、网络中蕴含的交互内容和主题等，提出了异构网络和异构社区概念，这也是人类认知和思维方式发展的必然过程；③从社会网络的时序特征看，在起步阶段，社区结构的研究对象都是一个网络快照，即只考虑了网络的静态性，而忽略了网络的时序变化性。随着静态网络的相关研究方法和技术日趋成熟，人们开始探索动态网络的社区结构发现算法及动态演化规律。

4 存在的挑战

从已有工作及其趋势分析可以看出，针对大规模、动态、异构的社会网络，研究准确、高效、可扩展性好的社区发现方法，是一个必然趋势，具有更好的应用和发展前景。虽然人们在这一方向已经取得了一些成果，但是仍然存在很多具有挑战性的问题，主要体现在：

（1）动态网络的时间片自动切分问题。在动态演化的社会网络中，能否对网络进行合理切分，将直接影响到社区发现的质量及方法的有效性评价。因此，基于自适应机器学习技术研究动态网络的时间片自动切分方法，是关键挑战之一，也是将来的一个研究方向。

（2）动态异构网络的信息集成问题。在动态演进的社会网络中，往往涉及到诸多种类的实体（用户或角色），而且实体间的关系也具有多样性，并且随着时间的推移不断变化。在动态异构网络中，如何对实体多样性、关系多样性、行为多样性以及网络的动态演进性等进行合理集成，将是关键挑战之一，也是未来的重要研究课题。

（3）动态异构社区发现模型的设计问题。在动态异构网络中，基于实体多样性、关系多样性、行为多样性以及网络的动态演进性等的合理集成，如何进行异构社区发现模型设计，如何控制模型的复杂度，如何保证方法的可扩展性等，使发现的异构社区更能够反映真实世界的群体特征，将是未来研究中非常有意义且充满挑战性的研究课题。

5 结语

作为大数据环境下复杂社会网络分析的一个热点问题，社区发现正吸引着国内外众多专家学者的关注。笔者以复杂社会网络的大规模、动态、异构3个特征为视角，对当前的研究工作进行了总结与分析，指出对大规模动态异构网络进行社区发现是一个必然趋势，但也存在着诸多困难。如何对动态网络进行时间片自动切分、如何对动态异构网络进行有机集成、如何设计动态异构社区的发现模型等都是未来研究中可能出现的挑战性问题。

参考文献：

[1] FORTUNATO S.Community detection in graphs[J]. Physics reports， 2010，486（3）：75-174.

[2] PALLA G， DERNYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature， 2005， 435（7043）： 814-818.

[3] NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E， 2004， 69（2）： 026113.

[4] FAN Y， LI M， ZHANG P， et al. Accuracy and precision of methods for community identification in weighted networks[J]. Physics， 2006， 377（1）：363-372.

[5] 杨博， 刘大有， 金弟，等. 复杂网络聚类方法[J].软件学报， 2009， 20（1）： 54-66.

[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.

（责任编辑：黄 健）