Number of cliques in random scale-free network ensembles

DOI10.1016/J.PHYSD.2006.09.013MaRDI QIDQ858491zbMATH OpenOpenAlexWikidataFDO

Authors Ginestra Bianconi, Matteo Marsili

Publication date 9 January 2007

Published in Physica D (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0606088

zbMATH Keywords

complex networks

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial probability (60C05) Applications of graph theory to circuits and networks (94C15)

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"os and Renyi graphs in which diverging average degree is required to observe cliques of size $c>3$. 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.

Recommendations

• About clique number estimates and exact enumeration in scale-free networks
• Structural properties of random networks of cliques
• Analyzing the cliques in scale-free random graphs
• Cliques in random graphs
• Asymptotics for cliques in scale-free random graphs
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Cliques in dense inhomogeneous random graphs
• Large cliques in a power-law random graph
• Parameterized Clique on Scale-Free Networks
• The distribution of clusters in random graphs

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• Circuits in random graphs: from local trees to global loops
• Loops of any size and Hamilton cycles in random scale-free networks
• Metric structure of random networks
• Statistical mechanics of complex networks

Cited in

(16)

• Large communities in a scale-free network
• On the distances within cliques in a soft random geometric graph
• About clique number estimates and exact enumeration in scale-free networks
• Loops of any size and Hamilton cycles in random scale-free networks
• Parameterized clique on inhomogeneous random graphs
• On the Rényi index of random graphs
• Robustness of clustering coefficients
• A new model for a scale-free hierarchical structure of isolated cliques
• A new model for a scale-free hierarchical structure of isolated cliques
• Analyzing the cliques in scale-free random graphs
• Large cliques in sparse random intersection graphs
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
• Cliques in rank-1 random graphs: the role of inhomogeneity
• Parameterized Clique on Scale-Free Networks
• Large cliques in a power-law random graph

This page was built for publication: Number of cliques in random scale-free network ensembles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q858491)