基于结构紧密性的重叠社区发现算法

The Overlapping Community Discovery Algorithm Based on Compact Structure

随着网络结构的不断扩大和日益复杂,传统的重叠社区发现算法已经不能有效地处理大规模网络数据,发现合理的社区结构.本文提出了顶点引力的概念,引入顶点凝聚度和社区凝聚度作为满足社区的外部结构稀疏性和社区内部结构紧密性的判定指标,构造了基于结构紧密性的重叠社区发现算法OCSC.该算法经过预处理,核心子图划分以及核心社区的扩展三个步骤,能有效地发现重叠社区,通过对人工合成网络和真实网络结构的社区发现实验,运用NMI和F1Score等指标验证OCSC算法的合理性和优越性.

With the continuous expansion and complexity of network structure,the traditional overlapping community detection algorithm can not effectively discover reasonable community structure in large-scale network structure.Based on the concept of vertex gravity proposed in this paper,we introduce vertex cohesion and community cohesion as indexes for community structure-close internal structure and sparse external structure,and then put forward overlapping community structure algorithm OCSC.The steps of OCSC algorithm include pre-processing,core sub-mapping and core community expansion.Finally,NMI and F1Score confirm the rationality and superiority of OCSC algorithm by experimentation on synthetic and real network structures.