Triadic closure in configuration models with unbounded degree fluctuations

Abstract

The configuration model generates random graphs with any given degree distribution, and thus serves as a null model for scale-free networks with power-law degrees and unbounded degree fluctuations. For this setting, we study the local clustering $c(k)$, i.e., the probability that two neighbors of a degree-$k$ node are neighbors themselves. We show that $c(k)$ progressively falls off with $k$ and eventually for $k=\Omega (\sqrt{n})$ settles on a power law $c(k)\sim k^{-2(3-\tau )}$ with $\tau \in (2,3)$ the power-law exponent of the degree distribution. This fall-off has been observed in the majority of real-world networks and signals the presence of modular or hierarchical structure. Our results agree with recent results for the hidden-variable model and also give the expected number of triangles in the configuration model when counting triangles only once despite the presence of multi-edges. We show that only triangles consisting of triplets with uniquely specified degrees contribute to the triangle counting.

References in corpus (10)

• The diameter of the world wide web
• The large-scale organization of metabolic networks
• Hierarchical Organization in Complex Networks
• Large-scale topological and dynamical properties of Internet
• Pseudofractal Scale-free Web
• Class of correlated random networks with hidden variables
• Generating simple random graphs with prescribed degree distribution
• Clustering in complex networks. I. General formalism
• Assortative model for social networks
• Clustering Spectrum of scale-free networks

Cited by in corpus (5)

• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Structural measures of similarity and complementarity in complex networks
• Scale-free network clustering in hyperbolic and other random graphs
• Strongly clustered random graphs via triadic closure: An exactly solvable model
• Switch chain mixing times through triangle counts