Spectral Synchronization Reveals Community Structure

Abstract:

Practical networks have community and hierarchical structure. These complex structures confuse the community detection algorithms and obscure the boundaries of communities. This paper proposes a delicate method which synthesizes spectral analysis and local synchronization to detect communities. Communities emerge automatically in the multi-dimension space of nontrivial eigenvectors. Its performance is compared to that of previous methods and applied to different practical networks. Our results perform better than that of other methods. Besides, it’s more robust for networks whose communities have different edge density and follow various degree distributions. This makes the algorithm a valuable tool to detect and analysis large practical networks with various community structures.

• Periodical: Applied Mechanics and Materials (Volumes 719-720)
• Pages: 1198-1202
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.719-720.1198
• Online since: January 2015
• Authors: Ming Yang Zhou, Zhong Qian Fu, Zhao Zhuo*
• Keywords: Community Detection, Complex Network, Spectral Analysis, Synchronization

References

[1] A-L Barabási, The network takeover, Nature Physics, 8(1): 14, (2011).

[2] M. E.J. Newman, Networks: an introduction, Oxford University Press, (2010).

[3] L. Donetti and M. A. Munoz, Detecting network communities: a new systematic and efficient algorithm, Journal of Statistical Mechanics: Theory and Experiment, 2004(10): P10012, (2004).

DOI: 10.1088/1742-5468/2004/10/p10012

[4] F. D. Malliaros and M. Vazirgiannis, Clustering and community detection in directed networks: A survey, Physics Reports, 533(4): 95–142, (2013).

DOI: 10.1016/j.physrep.2013.08.002

[5] L. Hong, S. M. Cai, J. Zhang, Z. Zhuo, Z. Q. Fu, and P. L. Zhou, Synchronization-based approach for detecting functional activation of brain, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(3): 033128, (2012).

DOI: 10.1063/1.4747710

[6] S. Fortunato, Community detection in graphs, Physics Reports, 486(3): 75–174, (2010).

[7] M. Coscia, F. Giannotti, and D. Pedreschi, A classification for community discovery methods in complex networks, Statistical Analysis and Data Mining, 4(5): 512–546, (2011).

DOI: 10.1002/sam.10133

[8] M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Physical review E, 69(2): 026113, (2004).

[9] Y. Y. Ahn, J. P. Bagrow and S. Lehmann, Link communities reveal multiscale complexity in networks, Nature, 466(7307): 761–764, (2010).

DOI: 10.1038/nature09182

[10] C. Böhm, C. Plant, J. Shao, and Q. Yang, Clustering by synchronization, In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 583–592, ACM, (2010).

DOI: 10.1145/1835804.1835879

[11] A. Capocci, V. D. P. Servedio, G. Caldarelli and F. Colaiori, Detecting communities in large networks, Physica A: Statistical Mechanics and its Applications, 352(2): 669–676, (2005).

DOI: 10.1016/j.physa.2004.12.050

[12] A. Arenas, A. Diaz-Guilera, J. Kurths, Y. Moreno, and C. S. Zhou, Synchronization in complex networks, Physics Reports, 469(3): 93–153, (2008).

DOI: 10.1016/j.physrep.2008.09.002

[13] J. Leskovec, K. J. Lang, A. Dasgupta, and M. W Mahoney, Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters, Internet Mathematics, 6(1): 29–123, (2009).

DOI: 10.1080/15427951.2009.10129177

[14] S. Chauhan, M. Girvan and E. Ott, Spectral properties of networks with community structure, Physical Review E, 80(5): 056114, (2009).

DOI: 10.1103/physreve.85.029906

[15] Information on http: /snap. stanford. edu/data.