Number of cliques in random scale-free network ensembles
arXiv:cond-mat/0606088 · doi:10.1016/j.physd.2006.09.013
Abstract
In this paper we calculate the average number of cliques in random scale-free networks. We consider first the hidden variable ensemble and subsequently the Molloy Reed ensemble. In both cases we find that cliques, i.e. fully connected subgraphs, appear also when the average degree is finite. This is in contrast to what happens in Erdös and Renyi graphs in which diverging average degree is required to observe cliques of size . Moreover we show that in random scale-free networks the clique number, i.e. the size of the largest clique present in the network diverges with the system size.
arXiv comment(15 pages)
References in corpus (15)
- Statistical mechanics of complex networks
- Epidemic spreading in scale-free networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Evolution of networks
- Resilience of the Internet to random breakdowns
- Universal Behavior of Load Distribution in Scale-free Networks
- Clique percolation in random networks
- Class of correlated random networks with hidden variables
- Ising Model on Networks with an Arbitrary Distribution of Connections
- The topological relationship between the large-scale attributes and local interaction patterns of complex networks
- Ferromagnetic ordering in graphs with arbitrary degree distribution
- Number of loops of size h in growing scale-free networks
- Emergence of large cliques in random scale-free network
- Loops of any size and Hamilton cycles in random scale-free networks
- Circuits in random graphs: from local trees to global loops