Europhys. Lett.
Volume 74, Number 4, May 2006
Page(s) 740 - 746
Section Interdisciplinary physics and related areas of science and technology
Published online 14 April 2006
Europhys. Lett., 74 (4), pp. 740-746 (2006)
DOI: 10.1209/epl/i2005-10574-3

Emergence of large cliques in random scale-free networks

Ginestra Bianconi and Matteo Marsili

The Abdus Salam International Center for Theoretical Physics Strada Costiera 11, 34014 Trieste, Italy

received 19 December 2005; accepted in final form 21 March 2006
published online 14 April 2006

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. Interestingly, 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 $\gamma \in (2,3)$. Moreover, as long as $\gamma<3$, scale-free networks have a maximal clique which diverges with the system size.

89.75.Hc - Networks and genealogical trees.
89.75.Fb - Structures and organization in complex systems.
89.75.Da - Systems obeying scaling laws.

© EDP Sciences 2006