Asymptotics for cliques in scale-free random graphs

Abstract

In this paper we establish asymptotics (as the size of the graph grows to infinity) for the expected number of cliques in the Chung--Lu inhomogeneous random graph model in which vertices are assigned independent weights which have tail probabilities $h^{1-\alpha }l(h)$, where $\alpha >2$ and $l$ is a slowly varying function. Each pair of vertices is connected by an edge with a probability proportional to the product of the weights of those vertices. We present a complete set of asymptotics for all clique sizes and for all non-integer $\alpha >2$. We also explain why the case of an integer $\alpha$ is different, and present partial results for the asymptotics in that case.

References in corpus (9)

• The statistical mechanics of networks
• The phase transition in inhomogeneous random graphs
• Class of correlated random networks with hidden variables
• Generating simple random graphs with prescribed degree distribution
• Scale-free Networks Well Done
• Emergence of large cliques in random scale-free network
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Clustering Spectrum of scale-free networks
• Degree correlations in scale-free null models