李维勇,孔 枫,张 伟,陈云芳
(1.南京信息职业技术学院网络与通信学院,南京210023;2.南京邮电大学计算机学院,南京210023)
近年来,社区发现成为复杂网络分析的重要任务,社区发现方法在社交网络中受到了极大的关注。社区是社交网络中的一种普遍现象,在社区中的许多成员倾向于形成紧密联系的群体。在不同的情况下,这些群体可以称为社区、集群、内聚子团或模块。社区发现是通过分析网络拓扑结构和网络节点的属性来研究出的某种集群的结构特征从而组成的一种网络节点集合,在该集群中内部节点连接紧密,而外部节点连接稀疏。显然,该集群的内部节点之间的交流比外部节点更加频繁。
如何在复杂网络中找到社区结构已经成为许多领域的热门话题,包括社会学、生物信息学和物理学等。属于同一个社区中的节点具有更大的可能性有着相同或相似的属性:例如,在同一个社交网络中的群体[1]更可能具有共同的兴趣爱好或者背景;在万维网中[2-4]形成的社区结构可能具有共同的主题和相关的页面;在细胞和遗传相关的生物或神经网络中[5-6],社区结构的形成可能暗示细胞存在相似特征。这些网络集合可以帮助简化整个网络的功能分析。
由于社区发现研究具有很重要的意义,目前已有许多社区发现方法被提出。现有的社区发现方法大致分为传统方法、分裂方法、基于模块的方法、谱方法和动态方法等[7]。分裂算法的……