Bianconi, Ginestra and Marsili, Matteo, 1966- (2005) Emergence of large cliques in random scale-free networks. Working Paper. Warwick Business School, Financial Econometrics Research Centre, Coventry.

Preview

PDF WRAP_bianconi_fwp05-03.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (520Kb)

Abstract

In a network cliques are fully connected subgraphs that reveal which are the tight communities present in it. Cliques of size c > 3 are present in random Erdös and Renyi graphs only in the limit of diverging average connectivity. Starting from the finding that real scale free graphs have large cliques, we study the clique number in uncorrelated scale-free networks finding both upper and lower bounds. Interesting we find that in scale-free networks large cliques appear also when the average degree is finite, i.e. even for networks with power-law degree distribution exponents ! ! (2, 3). Moreover as long as ! < 3 scale-free networks have a maximal clique which diverges with the system size.

Item Type:	Working or Discussion Paper (Working Paper)
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Social Sciences > Warwick Business School > Financial Econometrics Research Centre Faculty of Social Sciences > Warwick Business School
Library of Congress Subject Headings (LCSH):	Cliques (Sociology), Subgroup growth (Mathematics), Graph theory, Maximal subgroups, Distribution (Economic theory)
Series Name:	Working papers (Warwick Business School. Financial Econometrics Research Centre)
Publisher:	Warwick Business School, Financial Econometrics Research Centre
Place of Publication:	Coventry
Date:	12 October 2005
Number:	No.05-
Number of Pages:	9
Status:	Not Peer Reviewed
Access rights to Published version:	Open Access
References:	[1] R. Albert and A.-L. Barabeási, Rev. Mod. Phys. 74, 47 (2002). [2] S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks (Oxford University Press,Oxford,2003). [3] R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet (Cambridge University Press, Cambridge, 2004). [4] S. Janson, T. Luczak, A. Rucinski, Random graphs (John Wiley & Sons,2000). [5] R. Cohen, K. Erez D. ben-Avraham and S. Havlin, Phys. Rev. Lett. 85 4626 (2000). [6] R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86, 3200 (2001). [7] E. Marinari and R. Monasson, J. Stat. Mech. P09004 (2004). [8] G. Bianconi and A. Capocci, Phys. Rev. Lett. 90 , 078701 (2003). [9] G. Bianconi and M. Marsili, JSTAT P06005 (2005). [10] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii and U. Alon, Science 298, 824 (2002). [11] R. Dobrin, Q. K. Beg, A.-L. Barabási and Z. N. Oltvai, BMC Bioinformatics 5 10 (2004). [12] A. Vazquez, R. Dobrin, D. Sergi, J.-P. Eckmann, Z. N. Oltvai, A.-L. Barabási, PNAS 101, 17940 (2004). [13] S. S. Skiena, in The Algorithm Design Manual, pp. 144 and 312-314 (New York: Springer-Verlag, 1997). [14] Let K be maximal integer such that removing iteratively all nodes with degree less than K leaves a nonempty sub-graph, the so-called K-core, and let cK be the clique number of the K-core. Then if cK > K then it is easy to show that cmax = cK. Else if cK # K then we have cK # cmax # K. Hence we derive the bounds c− = min(cK,K) # cmax # max(cK,K). [15] T. R. Jensen, B. Toft, Graph Coloring Problems (New York: Wiley, 1994). [16] I. Derenyi, G. Palla and T. Vicsek, Phys. Rev. Lett. 94 160202 (2005). [17] G. Palla, I. Derenyi, I. Farkas and T. Vicsek, Nature 435 815 (2005). [18] The Internet datasets we used are the ones collected by University of Oregon Route Views project, NLANR and the protein-protein interaction datasets are one listed in DIP database. [19] G Caldarelli, A. Capocci, P. De Los Rios and M. A. Muñoz, Phys. Rev. Lett. 89, 258702 (2002). [20] M. Boguña and R. Pastor-Satorras, Phys. Rev. E 68, 036112 (2003). [21] M. Molloy and B. Reed, Random Structures and Algorithms 6, 161 (1995). [22] K.-L. Goh, B. Kahng and D. Kim, Phys. Rev. Lett. 87 278701 (2001). [23] G. Bianconi and M. Marsili (in preparation). [24] S.Dorogotsev, A.V. Goltsev and J. F. F. Mendes, Phys. Rev. E66 016104 (2002); M. Leone, A. Vázquez, A. Vespignani and R. Zecchina,Eur. Phys. J. B 28 191 (2002). [25] Indeed Eq. (7) can be expanded in moments of Qc−1 and a direct calculation shows that the ratio of the nth term to the first is 'Q(c−1)n(e−ny" /'Qc−1(e−y" ) c−! (c−1)n−!+1 2 c(c−1) bN 3n−1 , which vanishes as N *+when c ) ¯c.
URI:	http://wrap.warwick.ac.uk/id/eprint/1778

Request changes to a record

Actions (login required)

View Item