Journal of Advanced Statistics

Download PDF (834.3 KB) PP. 15 - 21 Pub. Date: June 1, 2018

DOI: 10.22606/jas.2018.32001

• Laala Zeyneb^*
  Department of Statistics and Mathematics, Central China Normal University

The community detection is one of the main problems in social network analysis. Many methods are proposed to recover the community labels of nodes by assuming the number of communities is known. There has been an increasing interest to explore the communities number. We propose a fast method based on spectral proprieties of the graph to estimate the number K of groups. The method performs well, especially when the number of groups in network is large, and we focus on when the network is unbalanced.

Stochastic block model; community detection, Bethe Hessian matrix

[1] C. J. Anderson, S. Wasserman and K. Foust , Social networks. 14,135 (1992).

[2] O. Angel, J. Friedman, and S. Hoory, The non-backtracking spectrum of the universal cover of a graph. arxiv:0712.0192, 2007.

[3] Can M. Le, Elizaveta Levina, Estimating the number of communities in networks by spectral methods. arxiv:1507.00827v1, 3 Jul 2015.

[4] Erd?s, P. Rényi, On Random Graph. I. Publicationes mathematicae. 6, 1959, 290-297.

[5] G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee, Self-organization and identification of web communities. Computer, 35(3):66-71, 2002.

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

[7] K. Foust and S. Wasserman , Social networks. 14,5(1992).

[8] M. Girvan and M.J. Newman. Community structure in social and biological networks. Proceedings of the national Academy of sciences, 99(12) : 7821-7826, 2002.

[9] A. Goldenberg, A. X. Zheng, S.E. Feinberg, and E. M. Airoldi , Foundations and Trends in machine learning.2, 1(2009).

[10] K. Hashimoto, Zeta functions of finite graphs and representations of p-adic groups. Adv.Stud. Pure Math. 15. 211-280 (1989).

[11] P. W. Holland, K. B. Laskey, and S. Leinhardth , Social networks. 5,109(1983).

[12] Jon Kleinberg and Steve Lawrence, The structure of the web. Science, 294(5548):1849U1850, 2001.

[13] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborov, and P. Zhang, Spectral redemption in clustering sparse networks. Proceedings of the National Academy of sciences, 110(52):20935- 20940, 2013.

[14] Leonhard Euler. Commentarii academiae scientirum. Petropolitanae 8, 1741, page 128-140)

[15] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A.-L. Barabàsi, Hierarchical Organization of Modularity in Metabolic Networks. Science, 297(5586):1551U 1555, 2002.

[16] A. Saade, F. Krzakala, and L. Zdeborová, Sectral clustering of graphs with the Bethe Hessian, September 9, 2014.

[17] T. A. Snijders and K. Nowicki , Journal of classification. 14, 75(1997).

[18] J. Xie, S. Kelley, and B.K Szymanski. Overlapping community detection in networks: the state of the art and comparative study. arxiv: 1110. 5813, 2011.