An effective community detection method based on one-dimensional “attraction” in network science

Yi-Yang Yu, Chuan-Yun Xu and Ke-Fei Cao
Additional contact information
Yi-Yang Yu: Center for Nonlinear Complex Systems, Department of Physics, School of Physics and Astronomy, Yunnan University, Kunming, Yunnan 650091, P. R. China
Chuan-Yun Xu: Center for Nonlinear Complex Systems, Department of Physics, School of Physics and Astronomy, Yunnan University, Kunming, Yunnan 650091, P. R. China
Ke-Fei Cao: Center for Nonlinear Complex Systems, Department of Physics, School of Physics and Astronomy, Yunnan University, Kunming, Yunnan 650091, P. R. China

International Journal of Modern Physics C (IJMPC), 2020, vol. 31, issue 05, 1-24

Abstract: Community detection has always been one of the most important issues in network science. With the arrival of the era of big data, it is necessary to develop new accurate and fast community detection methods for the study of many real complex networks (especially large networks). Based on the concept of strong community and the analogy between the edge and the attraction, this paper proposes an effective one-dimensional “attraction” (1DA) method for community detection. The 1DA method uses the number of edges as the measure of the “attraction”. The specific 1DA algorithm is also presented using two effective ways of vertex moving (i.e. the nearest moving and the median moving). After being randomly initialized at different positions on the (one-dimensional) number axis, all vertices will move under the action of the “attraction”; eventually, the vertices of the same community will naturally gather at the same position, while the vertices of different communities will gather at different positions, thus realizing the community division naturally. This method is tested in five typical real networks and one popular benchmark, and compared with several other popular community detection methods. Theoretical analysis and numerical experiments show that the 1DA method can accurately estimate the number of communities, with low (almost linear) time complexity (∼O(n), where n is the network size) and good performance in modularity and normalized mutual information in various networks (especially in the tests in large networks, the 1DA method has the best performance). The 1DA method in this paper provides a simple and practical solution to the problem of community detection.

Keywords: Network; community detection; attraction; algorithm (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.worldscientific.com/doi/abs/10.1142/S0129183120500710
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:31:y:2020:i:05:n:s0129183120500710

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183120500710

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().