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

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.