基于集体影响力的重叠社区检测算法

Overlapping community detection algorithm based on collective influence

关键词:  社区检测  重叠社区  集体影响力  标签传播  节点重要性

Key words:  community detection  overlapping community  collective influence  label propagation  node importance

摘要:

随着大数据时代的到来,网络结构日益复杂,探索复杂网络的社区结构对理解其功能和组织机制具有重要意义。关于社区检测已有大量研究,其中标签传播算法(LPA)具有接近线性的时间复杂度,适用于大规模复杂网络,但其随机性较强,准确性不高。提出基于集体影响力的标签传播算法(CILPA),用于发现重叠社区结构。CILPA引入集体影响力这一全局指标,融合节点自身信息和网络全局信息重新定义节点重要性,并依此固定节点更新顺序以提升算法稳定性；在标签传播过程中,设计一种标签选择策略,并设置自适应过滤因子,防止错误标签的干扰,从而提高算法的准确性和鲁棒性。最后在不同规模、复杂度及重叠率的人工网络和真实网络上进行实验,结果表明,CILPA的模块度和标准化互信息均优于COPRA、SLPA等主流算法,且标准差更小。说明本方法在重叠社区检测中兼具有效性和稳定性,为大规模复杂网络的重叠社区分析提供了可靠方法。

Abstract:

With the advent of the era of big data, network structures are becoming more and more complex, and exploring the community structure of complex networks holds great significance in understanding their function and organization mechanisms. Many studies have been conducted for community detection, among which the label propagation algorithm (LPA) has a near linear time complexity and is applicable for large-scale complex networks. However, it has excessive randomness and relatively low accuracy. This paper proposed a collective influence-based label propagation algorithm (CILPA) for discovering overlapping community structures. CILPA introduced collective influence as a global indicator, redefined the node importance by integrating the node’s own information and global network information, and fixed node update order according to node importance to improve the algorithm’s stability. In the label propagation process, a label selection strategy was designed, and the adaptive filtering factor were set to prevent the interference of wrong labels, thereby improving the accuracy and robustness of the algorithm. Finally, experiments were conducted on artificial and real networks with different scales, complexities, and overlap rates. The results show that the modularity and normalized mutual information of CILPA are superior to those of mainstream algorithms such as COPRA and SLPA, with a smaller standard deviation. This indicates that the proposed method possesses both effectiveness and stability in overlapping community detection, providing a reliable method for the analysis of overlapping communities in large-scale complex networks.