图重构下大规模网络的社团检测算法

Community detection algorithm for large-scale networks by graph reconstruction

对大型复杂网络进行高质量的社团检测通常依赖图的拓扑结构来划分节点集,然而现实世界的网络通常带有嘈杂且与集群无关的连接,这些链接可能会导致模型将来自不同集群的节点划分在一起。为此,提出了基于图重构的社团检测算法(graph reconstruction based community detection,GRCD),该方法能够处理大规模复杂网络的社团检测。首先,删除社团之间的相互连接的边来重新构建原始图的社团结构;然后,将网络视为一个社交系统,旨在以更直观的方式揭示社团;提出了一种高效的社团检测策略,即基于话语权的社团组织生成策略;最后,在不同规模数据集上进行实验。实验结果表明,GRCD算法不仅能够处理大规模网络,而且在保持较高稳定性的同时,其社团划分的质量对比现有的几种基准算法都有很强的竞争力。

High-quality community detection for large-scale complex networks usually depends on the topology of the graph,which used to divide the node set.However,real-world networks usually have noisy and cluster-independent links,which may cause the model to divide the nodes from different clusters together.This paper proposed a algorithm called graph reconstruction based community detection(GRCD).This method could handle community detection in large-scale complex networks.GRCD firstly deleted the connected edges between communities to reconstruct the community structure of the original graph.Subsequently,GRCD regarded the network as a social system,aiming to reveal the community in a more intuitive way.This paper proposed an efficient community detection strategy:a community organization generation strategy based on discourse power.Extensive experiments were performed on datasets of different sizes.The results show that GRCD can not only deal with large-scale networks,but also has strong competitiveness in the quality of its community division compared with several existing benchmark algorithms while maintaining high stability.