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
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
-
-
Classification
-
Physics
-
License
-
License undefined
-
Identifiers
-
-
Persistent URL
-
https://folia.unifr.ch/unifr/documents/308395
Statistics
Document views: 61
File downloads: