Open Science Research Excellence

Open Science Index

Commenced in January 2007 Frequency: Monthly Edition: International Publications Count: 29734


Select areas to restrict search in scientific publication database:
10009965
Natural Emergence of a Core Structure in Networks via Clique Percolation
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.
Digital Object Identifier (DOI):

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).
Vol:13 No:06 2019Vol:13 No:05 2019Vol:13 No:04 2019Vol:13 No:03 2019Vol:13 No:02 2019Vol:13 No:01 2019
Vol:12 No:12 2018Vol:12 No:11 2018Vol:12 No:10 2018Vol:12 No:09 2018Vol:12 No:08 2018Vol:12 No:07 2018Vol:12 No:06 2018Vol:12 No:05 2018Vol:12 No:04 2018Vol:12 No:03 2018Vol:12 No:02 2018Vol:12 No:01 2018
Vol:11 No:12 2017Vol:11 No:11 2017Vol:11 No:10 2017Vol:11 No:09 2017Vol:11 No:08 2017Vol:11 No:07 2017Vol:11 No:06 2017Vol:11 No:05 2017Vol:11 No:04 2017Vol:11 No:03 2017Vol:11 No:02 2017Vol:11 No:01 2017
Vol:10 No:12 2016Vol:10 No:11 2016Vol:10 No:10 2016Vol:10 No:09 2016Vol:10 No:08 2016Vol:10 No:07 2016Vol:10 No:06 2016Vol:10 No:05 2016Vol:10 No:04 2016Vol:10 No:03 2016Vol:10 No:02 2016Vol:10 No:01 2016
Vol:9 No:12 2015Vol:9 No:11 2015Vol:9 No:10 2015Vol:9 No:09 2015Vol:9 No:08 2015Vol:9 No:07 2015Vol:9 No:06 2015Vol:9 No:05 2015Vol:9 No:04 2015Vol:9 No:03 2015Vol:9 No:02 2015Vol:9 No:01 2015
Vol:8 No:12 2014Vol:8 No:11 2014Vol:8 No:10 2014Vol:8 No:09 2014Vol:8 No:08 2014Vol:8 No:07 2014Vol:8 No:06 2014Vol:8 No:05 2014Vol:8 No:04 2014Vol:8 No:03 2014Vol:8 No:02 2014Vol:8 No:01 2014
Vol:7 No:12 2013Vol:7 No:11 2013Vol:7 No:10 2013Vol:7 No:09 2013Vol:7 No:08 2013Vol:7 No:07 2013Vol:7 No:06 2013Vol:7 No:05 2013Vol:7 No:04 2013Vol:7 No:03 2013Vol:7 No:02 2013Vol:7 No:01 2013
Vol:6 No:12 2012Vol:6 No:11 2012Vol:6 No:10 2012Vol:6 No:09 2012Vol:6 No:08 2012Vol:6 No:07 2012Vol:6 No:06 2012Vol:6 No:05 2012Vol:6 No:04 2012Vol:6 No:03 2012Vol:6 No:02 2012Vol:6 No:01 2012
Vol:5 No:12 2011Vol:5 No:11 2011Vol:5 No:10 2011Vol:5 No:09 2011Vol:5 No:08 2011Vol:5 No:07 2011Vol:5 No:06 2011Vol:5 No:05 2011Vol:5 No:04 2011Vol:5 No:03 2011Vol:5 No:02 2011Vol:5 No:01 2011
Vol:4 No:12 2010Vol:4 No:11 2010Vol:4 No:10 2010Vol:4 No:09 2010Vol:4 No:08 2010Vol:4 No:07 2010Vol:4 No:06 2010Vol:4 No:05 2010Vol:4 No:04 2010Vol:4 No:03 2010Vol:4 No:02 2010Vol:4 No:01 2010
Vol:3 No:12 2009Vol:3 No:11 2009Vol:3 No:10 2009Vol:3 No:09 2009Vol:3 No:08 2009Vol:3 No:07 2009Vol:3 No:06 2009Vol:3 No:05 2009Vol:3 No:04 2009Vol:3 No:03 2009Vol:3 No:02 2009Vol:3 No:01 2009
Vol:2 No:12 2008Vol:2 No:11 2008Vol:2 No:10 2008Vol:2 No:09 2008Vol:2 No:08 2008Vol:2 No:07 2008Vol:2 No:06 2008Vol:2 No:05 2008Vol:2 No:04 2008Vol:2 No:03 2008Vol:2 No:02 2008Vol:2 No:01 2008
Vol:1 No:12 2007Vol:1 No:11 2007Vol:1 No:10 2007Vol:1 No:09 2007Vol:1 No:08 2007Vol:1 No:07 2007Vol:1 No:06 2007Vol:1 No:05 2007Vol:1 No:04 2007Vol:1 No:03 2007Vol:1 No:02 2007Vol:1 No:01 2007