Journal
INFORMATION SCIENCES
Volume 551, Issue -, Pages 358-372Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2020.10.057
Keywords
Social networks; Community detection; Graph clustering; Graph compression; Community seeds
Categories
Funding
- National Key Research and Development Program of China [2020AAA0106100]
- National Natural Science Fund of China [62072293, 61876103, 61976128, 61906111, 62006145]
- Key R&D projects of Shanxi Province [201903D121162]
- Scientific and Technologial Innovation Programs of Higher Education Institutions in Shanxi [2020L0245]
- 1331 Engineering Project of Shanxi Province, China
Ask authors/readers for more resources
This paper proposes a community detection algorithm based on graph compression, which merges vertices, defines density and quality indicators, and simultaneously determines the number of communities and initial seeds, achieving analysis of community structure of social networks. Experiments demonstrate the superiority of this method over existing community detection algorithms.
Uncovering the underlying community structure of a social network is an important task in social network analysis. To solve this problem, many community detection algorithms for the full topology of an original social network have been proposed. However, these algorithms are not very effective at analyzing large-scale social networks. To overcome this deficiency, this paper proposes a community detection algorithm based on graph compression. Specifically, a compressed graph is first obtained by iteratively merging vertices with a degree of 1 or 2 into their neighbors with a higher degree. Then, two indices, i.e., the density and quality of vertices, are defined to evaluate the probability of vertices as community seeds. By considering these two measures together, in a compressed social network, the number of communities and the corresponding initial community seeds are determined simultaneously. After obtaining the community structure of the compressed social network via seed expansion, the community results are propagated to the original social network. Extensive experiments conducted on various social networks have demonstrated the superiority of our proposal compared to several existing state-of-the-art community detection algorithms. (C) 2020 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available