Statistical properties of random clique networks

Abstract

In this paper, a random clique network model to mimic the large clustering coefficient and the modular structure that exist in many real complex networks, such as social networks, artificial networks, and protein interaction networks, is introduced by combining the random selection rule of the Erdös and Rényi (ER) model and the concept of cliques. We find that random clique networks having a small average degree differ from the ER network in that they have a large clustering coefficient and a power law clustering spectrum, while networks having a high average degree have similar properties as the ER model. In addition, we find that the relation between the clustering coefficient and the average degree shows a non-monotonic behavior and that the degree distributions can be fit by multiple Poisson curves; we explain the origin of such novel behaviors and degree distributions.

Keywords

complex networks / random clique networks / motifs / communicability

References

[1] P.Erdös and A.Rényi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960)

[2] D. J.Wattsand S. H.Strogatz, Collective dynamics of small-world networks, Nature393(6684), 440(1998)

[3] A. L.Barabásiand R.Albert, Emergence of scaling in random networks, Science286(5439), 509(1999)

[4] A. L.Barabási, R.Albert, and H.Jeong, Mean-field theory for scale-free random networks, Physica A272(1–2), 173(1999)

[5] S. H.Strogatz, Exploring complex networks, Nature410(6825), 268(2001)

[6] R.Albertand A. L.Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74(1), 47(2002)

[7] M. E. J.Newman, The structure and function of complex networks, SIAM Rev. 45(2), 167(2003)

[8] S.Boccaletti, V.Latora, Y.Moreno, M.Chavez, and D.Hwang, Complex networks: Structure and dynamics, Phys. Rep. 424(4–5), 175(2006)

[9] R.Milo, S.Shen-Orr, S.Itzkovitz, N.Kashtan, D.Chklovskii, and U.Alon, Network motifs: Simple building blocks of complex networks, Science298(5594), 824(2002)

[10] E.Ravaszand A. L.Barabási, Hierarchical organization in complex networks, Phys. Rev. E67(2), 026112(2003)

[11] R.Milo, S.Itzkovitz, N.Kashtan, R.Levitt, S.Shen Orr, I.Ayzenshtat, M.Sheffer, and U.Alon, Superfamilies of evolved and designed networks, Science303(5663), 1538(2004)

[12] A.Clauset, C.Moore, and M. E. J.Newman, Hierarchical structure and the prediction of missing links in network s, Nature453(7191), 98(2008)

[13] M. E. J.Newman, Communities, modules and largescale structure in networks, Nat. Phys. 8, 25(2012)

[14] Bollobás, B.Random Graphs, Academic Press, London, 1985

[15] G.Palla, I.Derenyi, I.Farkas, and T.Vicsek, Uncovering the overlapping community structure of complexnet works in nature and society, Nature435(7043), 814(2005)

[16] I.Derényi, G.Palla, and T.Vicsek, Clique percolation in random networks, Phys. Rev. Lett. 94(16), 160202(2005)

[17] K.Takemotoand C.Oosawa, Evolving networks by merging cliques, Phys. Rev. E72(4), 046116(2005)

[18] W. K.Xiao, J.Ren, F.Qi, Z. W.Song, M. X.Zhu, H. F.Yang, H. Y.Jin, and B. H.Wang, Empirical study on clique-degree distribution of networks, Phys. Rev. E76, 037102(2007)

[19] R.Lambiotteand M.Ausloos, Collaborative tagging as a tripartite network, Lect. Notes Comput. Sci. 3993, 1114(2006)

[20] G.Ghoshal, V.Zlatić, G.Caldarelli, and M. E. J.Newman, Random hypergraphs and their applications, Phys. Rev. E79(6), 066118(2009)

[21] V.Zlatić, G.Ghoshal, and G.Caldarelli, Hypergraph topological quantities for tagged social networks, Phys. Rev. E80(3), 036118(2009)

[22] M. E. J.Newman, Random graphs with clustering, Phys. Rev. Lett. 103(5), 058701(2009)

[23] B.Karrerand M. E. J.Newman, Random graphs containing arbitrary distributions of subgraphs, Phys. Rev. E82(6), 066118(2010)

[24] Y.Ding, B.Zhou, and X.Chen, Hybrid evolving clique networks and their communicability, Physica A407, 198(2014)

[25] N.Slater, R.Itzchack, and Y.Louzoun, Mid size cliques are more common in real world networks than triangles, Netw. Sci. 2(03), 387(2014)

[26] F.Fangand X.Chen, General clique percolation in random networks, Europhys. Lett. 107(2), 28005(2014)

[27] H.Shen, X.Cheng, K.Cai, and M. B.Hu, Detect overlapping and hierarchical community structure in networks, Physica A338(8), 1706(2009)

[28] M. E. J.Newman, Scientific collaboration networks (I): Network construction and fundamental results, Phys. Rev. E64(1), 016131(2001)

[29] A. L.Barabási, H.Jeong,Z.Neda, E.Ravasz, A.Schubert, and T.Vicsek, Evolution of the social network of scientific collaborations, Physica A311(3–4), 590(2002)

[30] S.Mei, R.Quax, D. A. M. C.van de Vijver, Y.Zhu, and P. M. A.Sloot, Increasing risk behaviour can outweigh the benefits of antiretroviral drug treatment on the HIV incidence among men-having-sex-with-men in Amsterdam, BMC Infect. Dis. 11(1), 118(2011)

[31] P.Colomer-de-Simón, M. Á.Serrano, M. G.Beiró, J. I.Alvarez-Hamelin, and M.Boguñá, Deciphering the global organization of clustering in real complex networks, Sci. Rep. 3(1), 2517(2013)

[32] Y.Ding, Z.Ding, and C.Yang, The network model of urban subway networks with community structure, Acta Phys. Sin. 62(9), 098901(2013)

[33] H.Jeong,S.Mason, A. L.Barabasi, and Z. N.Oltvai, Lethality and centrality in protein networks, Nature411(6833), 41(2001)

[34] D.van Dijk, G.Ertaylan, C. A. B.Boucher, and P. M. A.Sloot, Identifyingpotential survival strategies of HIV-1 through virus-host protein interaction networks, BMC Syst. Biol. 4(1), 96(2010)

[35] A.Czaplicka, J. A.Holyst, and P. M. A.Sloot, Noise enhances information transfer in hierarchical networks, Sci. Rep. 3, 1223(2013)

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg