佟帅 陈德运 杨海陆

摘 要：社区发现是在线社交网络研究领域中的重要内容，基于种子扩张的社区发现算法具有时间复杂度低、识别精度高以及不受社区形态限制等特点，近年来在网络局部社区发现任务中得到了广泛的应用。然而，该方法在种子选取时没有考虑种子之间的关联性，因此识别出的社区结构个数较多、结构松散。针对这一问题，提出一种基于多点种子预划分的二阶段社区发现算法。首先识别网络中的高影响力节点，利用K-means算法将高影响力节点加以聚合，得到高影响力社区簇。然后提出一种吸引力度量函数，选择性的将网络中的剩余节点合并到社区簇以完成社区识别任务。实验结果表明，二阶段社区发现方法能够发现尺寸较大，个数较少的社区结构，进而在中观层面捕捉群组之间的关联性。

关键词：复杂网络;局部社区发现;种子扩张;节点影响力;K-means算法

DOI：10.15938/j.jhust.2021.04.011

中图分类号：TP391.4

文献标志码：A

文章编号：1007-2683（2021）04-0078-09

Abstract：Community detection is an important content in the field of online social networks research. The community detection algorithm based on seed expansion has the characteristics of low time complexity， high recognition accuracy， and is not restricted by the shape of the community. In recent years， it has been widely used in local community discovery of complex networks. However， this method does not consider the correlation between seeds when selecting seeds， so the number of identified community structures is large and the structure is loose. Aiming at this problem， a two-stage community discovery algorithm for multi-point seed prepartition was proposed. First， high-impact nodes in the network are identified， and high-impact nodes are aggregated using the k-means algorithm to obtain high-impact community clusters. Next， an attractiveness measurement function is proposed to selectively merge the remaining nodes in the network into the community cluster to complete the community identification task. The experimental results show that the two-stage community discovery method can find community structures with larger sizes and fewer numbers， and then capture the association between groups at the meso level.

Keywords：complex network; local community detection; seed expansion; node influence; K-means algorithm

0 引 言

现实世界的复杂网络通常可以抽象为图模型，图中节点代表现实世界的实体，两个节点之间的链接代表实体之间的关系。社区[1]是复杂网络中的稠密子图，保证了社区内部节点之间的链接较为紧密，社区之间节点的链接较为稀疏[2-5]。探索社区结构有助于人们理解复杂网络的自组织以及群聚特性，是复杂网络中观层次最重要的属性之一。

从社区的层次化角度来看，已有的社区识别算法可分为全局优化算法和局部优化算法两种。……