Emergence of large cliques in random scale-free network

Abstract

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 Erdos 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. Interesting 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 gamma in the interval (2,3). Moreover as long as gamma<3 scale-free networks have a maximal clique which diverges with the system size.

arXiv comment(4 pages, 1 figure)

References in corpus (16)

• 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
• Loops of any size and Hamilton cycles in random scale-free networks
• Phase coexistence in a forecasting game
• Circuits in random graphs: from local trees to global loops
• Minority games with finite score memory

Cited by in corpus (21)

• Detecting rich-club ordering in complex networks
• Assessing the relevance of node features for network structure
• Structural constraints in complex networks
• Enumeration of spanning trees in a pseudofractal scale-free web
• Number of cliques in random scale-free network ensembles
• Phase coexistence in a forecasting game
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Entropy distribution and condensation in random networks with a given degree distribution
• Spectral Detection of Simplicial Communities via Hodge Laplacians
• Rich-Club Ordering and the Dyadic Effect: Two Interrelated Phenomena
• Analysing degeneracies in networks spectra
• Fluctuations analysis in complex networks modeled by hidden variable models. Necessity of a large cut-off in hidden-variable models
• Statistical mechanics of random geometric graphs: Geometry-induced first order phase transition
• Cliques in rank-1 random graphs: the role of inhomogeneity
• Changes of statistical structural fluctuations unveils an early compacted degraded stage of PNS myelin
• Large Communities in a scale-free network
• Correlated disorder in myelinated axons orientational geometry and structure
• Fluctuations of motifs and non self-averaging in complex networks. A self- vs non-self-averaging phase transition scenario
• Evolving complex networks with conserved clique distributions
• Asymptotics for cliques in scale-free random graphs
• SIS epidemic propagation on hypergraphs