基于网络节点中心性度量的重叠社区发现算法

An Overlapping Community Detection Algorithm Based on Centrality Measurement of Network Node

基于搜索密度峰值的聚类思想,设计了一种网络节点的中心性度量模型,并提出了一种重叠社区发现算法.首先,定义了网络节点的内聚度和分离度,分别用于描述网络社区内部连接稠密和外部连接稀疏的结构特征,在此基础上计算节点的中心性度量表达节点对社区结构的影响力.接着,利用3δ法则选择中心度异常大的节点作为社区中心.以隶属度表达社区间的重叠特性,并给出了非中心节点的隶属度迭代计算方法,将各节点分配到其可能隶属的网络社区,以实现重叠社区划分.最后,利用人工网络和真实网络对提出的重叠社区发现算法进行验证,实验结果表明:该算法在社区发现质量和计算效率方面都优于许多已有重叠社区发现算法.

Based on the idea of density peak clustering method, a centrality measurement model for network nodes is designed, and a new community detection algorithm for overlapping network is also proposed. In the algorithm, the cohesion and separation of network nodes are defined at first, to describe the structural feature of community that the intra links inside one community are dense while the inter links between communities are sparse. Depend on that, centrality measurement is calculated for each node to express its influence on network community structure. Then the nodes with tremendous centralities are selected by the 3δ principle as community centers. The overlapping features between communities are represented by memberships, and the iterative calculation methods for the memberships of non-central nodes are put forward. After that, according to their memberships, all the nodes in network can be allocated to their possible communities to accomplish the overlapping community detection. At last, the proposed algorithm is verified by the simulation on both synthetic networks and social networks. The simulation results reflect that our algorithm outperforms other competitive overlapping community detection algorithms in respect of both detection quality and computational efficiency.