基于中心团的重叠社区检测算法

Algorithm for Detecting Overlapping Communities Based on Centered Cliques

社区检测已经成为了了解复杂网络结构和网络动态的一个重要途径。针对传统的节点聚类和链接聚类在发现重叠社区方面存在的两种固有缺陷,即参数依赖和结果不稳定,文中提出了一种基于中心团的局部扩展改进算法CLEM,用于检测重叠社区。该算法通过选取中心团为核心种子,并在种子扩展过程中惩罚被多次删除的节点,改善所得结果的稳定性;通过选取不依赖参数的适应度函数,改进其迭代计算过程,避免了适应度函数的参数限制,并降低了计算复杂度。在合成网络和现实网络上测试的结果表明,与已有算法相比,所提算法在计算时间和准确度上均有很好的表现。

Community detection in complex network has become a vital way to understand its structure and dynamic characteristics.However,there are two inherent shortcomings that the parameter dependency and instability of using the traditional node clustering and link clustering to detect overlapping communities.This paper proposes an improving algorithm,that is,the local expansion method based on the centered clique(CLEM),for detecting overlapping communities.Firstly,in CLEM algorithm,the centered cliques is selected as the core seed and the nodes deleted by multiple times in the process of seed expansion are punished,so its stability of results is improved.Then,by selecting the fitness function with parameter-independent and improving its iterative calculation process,the parameter limitation of the fitness function is avoided and the computational complexity is quickly reduced.Finally,the test results on synthetic networks and real-world networks show that CLEM is good both in computing time and accuracy compared with some existing algorithms.