Journal article

Parallel heuristic community detection method based on node similarity

  • Zhou, Qiang School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China
  • Cai, Shi-Min School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China - Institute of Fundamental and Frontier Science, University of Electronic Science and Technology of China, Chengdu, China
  • Zhang, Yi-Cheng Institute of Fundamental and Frontier Science, University of Electronic Science and Technology of China, Chengdu, China - Department of Physics, University of Fribourg, Switzerland
    2019
Published in:
  • IEEE Access. - 2019, vol. 7, p. 184145–184159
English Community structure discovery can help us better understand the capabilities and functions of the network. However, many existing methods have failed to identify nodes in communities accurately. In this paper, we proposed a heuristic community detection method based on node similarities that are computed by assigning different edge weight influence factors based on different neighbor types of nodes. Concretely, by arbitrarily choosing a pair of nodes, we firstly found out the common neighbor nodes of the node pair and their corresponding neighbor nodes. Then, different edge weight influence factors are assigned according to the impact of different types of neighbor nodes on node similarity. Finally, the similarities between a pair of nodes are calculated by the proportion of various edge weight influence factors related to the node pair. Along the direction, a hash table based data storage and retrieval strategy with a lower conflict rate is introduced to hash the edge information into a ternary bucket structure that can be merged according to the same starting node. This operation can reduce the time complexity of the data query to a constant level, and realize the parallel computing of node similarity. When obtaining similarity of node pair, we merged nodes into communities by a heuristic hierarchical clustering. And, the resulting community structure is detected until all node similarities are calculated. With the help of the comparison tests of different methods based on the benchmark networks that have ground-truth communities, the proposed method for community detection provides better performance in both identification accuracy and time efficiency.
Faculty
Faculté des sciences et de médecine
Department
Département de Physique
Language
  • English
Classification
Physics
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/308395
Statistics

Document views: 8 File downloads:
  • zha_phc.pdf: 1