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

大数据环境下复杂社会网络的社区发现方法研究综述 　　摘 要：社会化媒体大数据环境下的社区发现研究，是社会网络分析与挖掘领域的一个热门研究方向，已有众多学者提出各种研究方法，但对当前研究工作的进展分析相对较少。首先从局部、全局、节点相似度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种不同的社区规模度量指标，通过控制社区的平衡增长方式，提出了一种改进的