基于引力作用的重叠社区检测算法

Overlapping Community Detection Algorithm Based on Gravitational Interaction

社区结构是复杂网络的一个重要特征,通过社区检测来分析和理解复杂网络的结构和功能具有重要意义。基于局部社区检测的算法因其高效性和有效性而被广泛应用于解决这一问题。然而,大多数算法对局部信息的利用率较低、扩展过程中的适应度函数无法动态度量节点间的连接方式,使得社区检测结果存在质量和稳定性方面的不足。基于此,提出一种基于引力作用的重叠社区检测算法,将网络中的拓扑信息带入万有引力公式,来衡量两个节点间的相互作用力;并应用引力作用公式改进局部扩展过程中的适应度函数,来获取高质量的可重叠的社区。通过真实网络和合成网络中的实验表明,该算法具有良好的性能。

Community structure is an important feature of complex networks,and it is important to analyze and understand the structure and function of complex networks by community detection.The algorithms based on local community detection are popularly used to solve this problem because of their efficiency and validity.Compared with global community discovery methods,local community discovery methods do not require information about the overall structure of complex networks.However,most of the available algorithms have low utilization of local information,and the fitness function in the expansion process is unable to dynamically measure the connectivity between nodes,which makes the community detection results deficient in terms of quality and stability.Based on this,an overlapping community detection algorithm based on gravitational action is proposed in this paper,which brings the topological information in the network into the universal gravity formula to measure the interaction force between two nodes,and applies the gravitational action formula to improve the fitness function in the local expansion process to obtain high-quality overlapping communities.Finally,the experiments in real and synthetic networks showed that the proposed algorithm has good performance.