计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (23): 54-59.DOI: 10.3778/j.issn.1002-8331.1606-0130

• 网络、通信与安全 • 上一篇    下一篇

可探测社区稳定结构的局部社区发现算法

李  辉,降爱莲   

  1. 太原理工大学 计算机科学与技术学院,山西 晋中 030600
  • 出版日期:2017-12-01 发布日期:2017-12-14

Local community detection method based on finding constant structure

LI Hui, JIANG Ailian   

  1. School of Computer Science and Technology, Taiyuan University of Technology, Jinzhong, Shanxi 030600, China
  • Online:2017-12-01 Published:2017-12-14

摘要: 社交网络的动态变化使社区发现的精确度面临更高挑战。目前提出的大部分算法都是以寻求模块度最优解来发现社区,但往往会忽略所发现的社区结构是否稳定。根据力学平衡原理即当一个物体所受内部力和外部力平衡的条件下可达稳定状态,因此基于点的稳定性机制,判断节点来自社区内部连边数量与来自外部社区连边数量的最大值是否保持平衡,提出一种可探测稳定结构的局部社区发现算法。网络的稳定性大小与社区的结构有很大的关系,因此将网络的稳定性作为一种新的评价社区结构优良的标准。通过在真实网络和人工集成网络上进行实验对比发现提出的算法的社区结构稳定度比其他算法高,同时能发现精确度高的社区。

关键词: 局部社区, 社区发现, 稳定度, 社区评价

Abstract: Community detection is facing greater challenges with the dynamic change in social network. Recently, most community detection algorithms are based on optimizing a function score and in order to require a higher result. However, less work has been done on understanding whether a network is indeed constant and if it could not be affected by other influence factors. As mechanics balance principle says, when an object under same internal power and external power, it is called equilibrium. Based on vertex-based metric, that is by judgement the distribution of the max external connectivity of the vertex to individual communities and the strength of its internal connectivity, it proposes a local community detection which could find constant structure. Also the constant value could be a new community quality evaluation standard because of a good correlation between constant value and the quality of community structure. The comparison with other local community algorithm in real networks and LFR benchmark mode network, finds that the algorithm has higher constant value than other algorithms and could reflect the ground-truth structure of higher quality accurately.

Key words: local community, community detection, constant value, community evaluation