Natural Emergence of a Core Structure in Networks via Clique Percolation

Authors: A. Melka, N. Slater, A. Mualem, Y. Louzoun

Abstract:

Networks are often presented as containing a “core” and a “periphery.” The existence of a core suggests that some vertices are central and form the skeleton of the network, to which all other vertices are connected. An alternative view of graphs is through communities. Multiple measures have been proposed for dense communities in graphs, the most classical being k-cliques, k-cores, and k-plexes, all presenting groups of tightly connected vertices. We here show that the edge number thresholds for such communities to emerge and for their percolation into a single dense connectivity component are very close, in all networks studied. These percolating cliques produce a natural core and periphery structure. This result is generic and is tested in configuration models and in real-world networks. This is also true for k-cores and k-plexes. Thus, the emergence of this connectedness among communities leading to a core is not dependent on some specific mechanism but a direct result of the natural percolation of dense communities.

Keywords: Networks, cliques, percolation, core structure, phase transition.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.3607830

References:

[1] P. Erd˝os and Al. R´enyi, Publ. Math. 6, 290 (1959).
[2] P. Erd˝os and A. R´enyi, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
[3] M. Porter, J. Onnela, and P. Mucha, Not. Am. Math. Soc. 56, 1082 (2009).
[4] R. Mokken, Qual. Quant. 13, 161 (1979).
[5] J. Duch and A. Arenas. Phys. Rev. E. 72, 027104 (2005).
[6] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, Proc. Nat. Acad. Sci USA. 101, 2658 (2004).
[7] M. E. J. Newman, SIAM Rev. 45, 167 (2003).
[8] M. E. J. Newman and Michelle Girvan, Phys. Rev. E. 69, 026113 (2004).
[9] A. Clauset, M. E. J Newman, and C. Moore, Phys. Rev. E. 70, 066111 (2004).
[10] M. E. J. Newman, Proc. Nat. Acad. Sci. 103, 8577 (2006).
[11] R. Luce, Psychometrika. 15, 169 (1950).
[12] S. Seidman and B. Foster, J. Math. Soc. 6, 139 (1978).
[13] S. Dorogovtsev, A. Goltsev, and J. Mendes, Phys. Rev. Lett. 96, 040601 (2006).
[14] I. Der´enyi, G. Palla, and T. Vicsek, Phys. Rev. Lett. 94, 160202 (2005).
[15] G. Palla, I. Der´enyi, and T. Vicsek, J. Stat. Phys. 128, 219 (2007).
[16] J. Fan and X. Chen, Europhys. Lett. 107, 28005 (2014).
[17] M. Li, Y. Deng, and B. Wang, Phys. Rev. E. 92, 042116 (2015).
[18] S. Borgatti and M. Everett, Soc. Networks, 21, 375 (2000).
[19] P. Holme, Phys. Rev. E. 72, 046111 (2005).
[20] P. Csermely, A. London, L. Wu, and B. Uzzi, J. Comp. Net. 1, 93 (2013).
[21] P. Rombach, M. Porter, J. Fowler, and P. Mucha, SIAM Rev. 59, 619 (2017).
[22] M. Catanzaro, M. Bogun´a and R. Pastor-Satorras, Phys. Rev. E. 71, 027103 (2005).
[23] C. Bron and J. Kerbosch, Commun. ACM, 16, 575 (1973).
[24] J. Scott, Soc. Networks (2017).
[25] S. Wasserman and K. Faust, Camb. Univ. Press, 8 (1994).
[26] M. Piraveenan, M. Prokopenko, and A. Zomaya, Euro. Phys. J. B. 70, 275 (2009).
[27] J. Wang, M. Li, H. Wang, and Y. Pan, IEEE T. Comp. Bio. 9,1070 (2012).
[28] C. Lin, H. Juan, J. Hsiang, Y. Hwang, H. Mori, and H. Huang, J. Proteome Res. 8, 1925 (2009).
[29] M. Kitsak, L. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H.Stanley, and H. Makse, Nat. Phys. 6, 888 (2010).
[30] D. Zhou, H. Stanley, G. DAgostino, and A. Scala, Phys. Rev. E. 86, 066103 (2012).
[31] S. Xiao, G. Xiao, T. Cheng, S. Ma, X. Fu, and H. Son, Europhys. Lett. 89, 38002 (2010).
[32] L. Adamic, N. Glance, Proceedings of the 3rd International Workshop on Link Discovery (2005).
[33] N. Du, B. Wu, L. Xu, B. Wang, X. Pei, Proceedings of the Data Mining Workshops (2006).
[34] S. Maslov, K. Sneppen, A. Zaliznyak, Physica A, 333, 529 (2004).