An effective community detection method based on one-dimensional 'attraction' in network science
| Autor: | Chuan-Yun Xu, Ke-Fei Cao, Yi-Yang Yu |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Theoretical computer science
business.industry Computer science Big data General Physics and Astronomy Statistical and Nonlinear Physics Graph theory Network science 01 natural sciences Attraction 010305 fluids & plasmas Computer Science Applications Computational Theory and Mathematics 0103 physical sciences 010306 general physics business Mathematical Physics |
| Zdroj: | International Journal of Modern Physics C. 31:2050071 |
| ISSN: | 1793-6586 0129-1831 |
| DOI: | 10.1142/s0129183120500710 |
| Popis: | 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 ([Formula: see text], where [Formula: see text] 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|