Research PaperNo Access

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

Center for Nonlinear Complex Systems, Department of Physics, School of Physics and Astronomy, Yunnan University, Kunming, Yunnan 650091, P. R. China

Search for more papers by this author

Chuan-Yun Xu

Center for Nonlinear Complex Systems, Department of Physics, School of Physics and Astronomy, Yunnan University, Kunming, Yunnan 650091, P. R. China

Search for more papers by this author

, and

Ke-Fei Cao

Center for Nonlinear Complex Systems, Department of Physics, School of Physics and Astronomy, Yunnan University, Kunming, Yunnan 650091, P. R. China

E-mail Address: kfcao163@163.com

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0129183120500710Cited by:1 (Source: Crossref)

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 ( $\sim 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:

PACS: 89.75.Hc, 89.75.Fb, 05.10.

$-$ a, 02.10.Ox

You currently do not have access to the full text article.
Recommend the journal to your library today!

References

1. M. C. González, P. G. Lind and H. J. Herrmann , Phys. Rev. Lett. 96, 088702 (2006). Web of Science, ADS, Google Scholar
2. M. C. González, H. J. Herrmann, J. Kertész and T. Vicsek , Physica A 379, 307 (2007). Web of Science, ADS, Google Scholar
3. M. Ferrary and M. Granovetter , Econom. Soc. 38, 326 (2009). Web of Science, Google Scholar
4. J. Ortega , Physica A 530, 121553 (2019). Web of Science, Google Scholar
5. J. Sheng, J. Hu, Z. Sun, B. Wang, A. Ullah, K. Wang and J. Zhang , Physica A 531, 121765 (2019). Web of Science, Google Scholar
6. M. Rubinov and O. Sporns , NeuroImage 52, 1059 (2010). Web of Science, Google Scholar
7. E. E. Schadt and J. L. M. Björkegren , Sci. Transl. Med. 4, 115rv1 (2012). Web of Science, Google Scholar
8. D. Krioukov, M. Kitsak, R. S. Sinkovits, D. Rideout, D. Meyer and M. Boguñá , Sci. Rep. 2, 793 (2012). Web of Science, Google Scholar
9. S. Hong and A. Dey , Mon. Not. R. Astron. Soc. 450, 1999 (2015). Web of Science, ADS, Google Scholar
10. U. Kang and C. Faloutsos , Beyond ‘caveman communities’: Hubs and spokes for graph compression and mining, in Proc. 2011 11th IEEE Int. Conf. Data Mining (ICDM 2011), Vancouver, Canada, December 11–14, 2011, eds. D. Cook, J. Pei, W. Wang, O. Zaïane and X. Wu (IEEE, Los Alamitos, CA, 2011), pp. 300–309. Google Scholar
11. C. Gan, X. Yang, W. Liu, Q. Zhu, J. Jin and L. He , Commun. Nonlinear Sci. Numer. Simul. 19, 2785 (2014). Web of Science, ADS, Google Scholar
12. P. Goyal and E. Ferrara , Knowl.-Based Syst. 151, 78 (2018). Web of Science, Google Scholar
13. D. J. Watts and S. H. Strogatz , Nature 393, 440 (1998). Web of Science, ADS, Google Scholar
14. A.-L. Barabási and R. Albert , Science 286, 509 (1999). Web of Science, ADS, Google Scholar
15. S. Fortunato , Phys. Rep. 486, 75 (2010). Web of Science, ADS, Google Scholar
16. S. Fortunato and D. Hric , Phys. Rep. 659, 1 (2016). Web of Science, ADS, Google Scholar
17. F. D. Malliaros and M. Vazirgiannis , Phys. Rep. 533, 95 (2013). Web of Science, ADS, Google Scholar
18. F. Radicchi, C. Castellano, F. Cecconi, V. Loreto and D. Parisi , Proc. Natl. Acad. Sci. USA 101, 2658 (2004). Web of Science, ADS, Google Scholar
19. F. Luccio and M. Sami , IEEE Trans. Circuit Theory 16, 184 (1969). Web of Science, Google Scholar
20. J. Leskovec, K. J. Lang, A. Dasgupta and M. W. Mahoney , Statistical properties of community structure in large social and information networks, in Proc. 17th Int. Conf. World Wide Web (WWW 2008), Beijing, China, April 21–25, 2008 (ACM, New York, NY, 2008), pp. 695–704. Google Scholar
21. C. Gao, Z. Ma, A. Y. Zhang and H. H. Zhou , J. Mach. Learn. Res. 18, 1980 (2017). Google Scholar
22. U. von Luxburg , Stat. Comput. 17, 395 (2007). Web of Science, Google Scholar
23. J. MacQueen , Some methods for classification and analysis of multivariate observations, in Proc. Fifth Berkeley Symp. Mathematical Statistics and Probability, Vol. 1, eds. L. M. Le Cam and J. Neyman (University of California Press, Berkeley and Los Angeles, CA, 1967), pp. 281–297. Google Scholar
24. T. S. Evans and R. Lambiotte , Phys. Rev. E 80, 016105 (2009). Web of Science, ADS, Google Scholar
25. B. Karrer and M. E. J. Newman , Phys. Rev. E 83, 016107 (2011). Web of Science, ADS, Google Scholar
26. A. Arenas, A. Díaz-Guilera and C. J. Pérez-Vicente , Phys. Rev. Lett. 96, 114102 (2006). Web of Science, ADS, Google Scholar
27. P. Pons and M. Latapy , Computing communities in large networks using random walks, in Proc. 20th Int. Symp. Computer and Information Sciences (ISCIS 2005), Istanbul, Turkey, October 26–28, 2005, Lecture Notes in Computer Science, Vol. 3733, eds. P. Yolum, T. Güngör, F. Gürgen and C. Özturan (Springer, Berlin, 2005), pp. 284–293. Google Scholar
28. M. Rosvall and C. T. Bergstrom , Proc. Natl. Acad. Sci. USA 105, 1118 (2008). Web of Science, ADS, Google Scholar
29. M. Rosvall, A. V. Esquivel, A. Lancichinetti, J. D. West and R. Lambiotte , Nat. Commun. 5, 4630 (2014). Web of Science, ADS, Google Scholar
30. L. G. S. Jeub, P. Balachandran, M. A. Porter, P. J. Mucha and M. W. Mahoney , Phys. Rev. E 91, 012821 (2015). Web of Science, ADS, Google Scholar
31. G. Yin, K. Chi, Y. Dong and H. Dong , Phys. Lett. A 381, 1349 (2017). Web of Science, ADS, Google Scholar
32. W. W. Zachary , J. Anthropol. Res. 33, 452 (1977). Web of Science, Google Scholar
33. T. M. J. Fruchterman and E. M. Reingold , Software Pract. Exper. 21, 1129 (1991). Web of Science, Google Scholar
34. V. Krebs, unpublished, http://www.orgnet.com. Google Scholar
35. D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten and S. M. Dawson , Behav. Ecol. Sociobiol. 54, 396 (2003). Web of Science, Google Scholar
36. M. Girvan and M. E. J. Newman , Proc. Natl. Acad. Sci. USA 99, 7821 (2002). Web of Science, ADS, Google Scholar
37. A. Lancichinetti, S. Fortunato and F. Radicchi , Phys. Rev. E 78, 046110 (2008). Web of Science, ADS, Google Scholar
38. A. A. Hagberg, D. A. Schult and P. J. Swart , Exploring network structure, dynamics, and function using networkX, in Proc. 7th Python in Science Conf. (SciPy 2008), Pasadena, CA, August 19–24, 2008, eds. G. Varoquaux, T. Vaught and J. Millman (2008), pp. 11–15. Google Scholar
39. T. E. Oliphant , Comput. Sci. Eng. 9, 10 (2007). Web of Science, Google Scholar
40. K. J. Millman and M. Aivazis , Comput. Sci. Eng. 13, 9 (2011). Web of Science, Google Scholar
41. F. Pérez and B. E. Granger , Comput. Sci. Eng. 9, 21 (2007). Web of Science, Google Scholar
42. J. D. Hunter , Comput. Sci. Eng. 9, 90 (2007). Web of Science, ADS, Google Scholar
43. M. E. J. Newman and M. Girvan , Phys. Rev. E 69, 026113 (2004). Web of Science, ADS, Google Scholar
44. M. E. J. Newman , Phys. Rev. E 69, 066133 (2004). Web of Science, ADS, Google Scholar
45. M. E. J. Newman , Proc. Natl. Acad. Sci. USA 103, 8577 (2006). Web of Science, ADS, Google Scholar
46. T. M. Cover and J. A. Thomas , Elements of Information Theory (John Wiley & Sons, New York, NY, 1991). Google Scholar
47. M. Hutter , Distribution of mutual information, in Proc. 14th Int. Conf. Neural Information Processing Systems: Natural and Synthetic (NIPS’01), Vancouver, British Columbia, Canada, December 3–8, 2001 (MIT Press, Cambridge, MA, 2001), pp. 399–406. Google Scholar
48. C. D. Manning, P. Raghavan and H. Schütze , An Introduction to Information Retrieval (Cambridge University Press, Cambridge, England, 2009). Google Scholar
49. U. N. Raghavan, R. Albert and S. Kumara , Phys. Rev. E 76, 036106 (2007). Web of Science, ADS, Google Scholar
50. G. Cordasco and L. Gargano , Community detection via semi-synchronous label propagation algorithms, in 2010 IEEE Int. Workshop on Business Applications of Social Network Analysis (BASNA 2010), Bangalore, India, December 15, 2010 (IEEE, 2010), pp. 1–8. Google Scholar
51. G. Cordasco and L. Gargano , Int. J. Social Network Mining 1, 3 (2012). Google Scholar
52. F. Parés, D. Garcia Gasulla, A. Vilalta, J. Moreno, E. Ayguadé, J. Labarta, U. Cortés and T. Suzumura , Fluid communities: A competitive, scalable and diverse community detection algorithm, in Complex Networks and Their Applications VI, Proc. Complex Networks 2017 (The Sixth Int. Conf. Complex Networks and Their Applications), Studies in Computational Intelligence, Vol. 689, eds. C. Cherifi, H. Cherifi, M. Karsai and M. Musolesi (Springer, Cham, 2018), pp. 229–240. Google Scholar