Number of cliques in random scale-free network ensembles

DOI10.1016/J.PHYSD.2006.09.013zbMATH Open1130.94023arXivcond-mat/0606088OpenAlexW2110877664WikidataQ60575128 ScholiaQ60575128MaRDI QIDQ858491FDOQ858491

Authors: Ginestra Bianconi, Matteo Marsili 

Publication date: 9 January 2007

Published in: Physica D (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Statistical mechanics of complex networks
• Metric structure of random networks
• A critical point for random graphs with a given degree sequence
• Title not available (Why is that?)
• Circuits in random graphs: from local trees to global loops
• Loops of any size and Hamilton cycles in random scale-free networks

Cited In (16)

• 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
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Large cliques in sparse random intersection 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
• On the distances within cliques in a soft random geometric graph
• Large communities in a scale-free network

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)