Emergence of large cliques in random scale-free networksGinestra 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 . Moreover, as long as , 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