ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (8): 1619-1630.doi: 10.7544/issn1000-1239.2018.20180187

Special Issue: 2018数据挖掘前沿进展专题

Previous Articles     Next Articles

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

Du Hangyuan1, Wang Wenjian2,Bai Liang2   

  1. 1(College of Computer and Information Technology, Shanxi University, Taiyuan 030006);2(Key Laboratory of Computational Intelligence & Chinese Information Processing(Shanxi University), Ministry of Education, Taiyuan 030006)
  • Online:2018-08-01

Abstract: 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.

Key words: node centrality, community detection, overlapping network community, membership, density peaks clustering

CLC Number: