基于引力作用的重叠社区检测算法
Overlapping Community Detection Algorithm Based on Gravitational Inter-action
赵洋洋 1刘士虎 1杨春生1
作者信息
- 1. 云南民族大学 数学与计算机科学学院,云南 昆明 650504
- 折叠
摘要
社区结构是复杂网络的一个重要特征,通过社区检测来分析和理解复杂网络的结构和功能具有重要意义.基于局部社区检测的算法因其高效性和有效性而被广泛应用于解决这一问题.然而,大多数算法对局部信息的利用率较低、扩展过程中的适应度函数无法动态度量节点间的连接方式,使得社区检测结果存在质量和稳定性方面的不足.基于此,提出一种基于引力作用的重叠社区检测算法,将网络中的拓扑信息带入万有引力公式,来衡量两个节点间的相互作用力;并应用引力作用公式改进局部扩展过程中的适应度函数,来获取高质量的可重叠的社区.通过真实网络和合成网络中的实验表明,该算法具有良好的性能.
Abstract
Community structure is an important feature of complex networks,and it is important to ana-lyze 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 re-quire 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 dynam-ically 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 gravita-tional action is proposed in this paper,which brings the topological information in the network into the univer-sal 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 com-munities.Finally,the experiments in real and synthetic networks showed that the proposed algorithm has good performance.
关键词
社区检测/重叠社区/引力作用/适应度函数Key words
community detection/overlapping community/gravitational interaction/fitness function引用本文复制引用
基金项目
国家自然科学基金(61966039)
兴滇英才支持计划青年人才专项(XDYC-QNRC-2022-0518)
出版年
2024
NETL
NSTL
万方数据