Clustering Spectrum of scale-free networks

Abstract

Real-world networks often have power-law degrees and scale-free properties such as ultra-small distances and ultra-fast information spreading. In this paper, we study a third universal property: three-point correlations that suppress the creation of triangles and signal the presence of hierarchy. We quantify this property in terms of $\bar{c}(k)$, the probability that two neighbors of a degree-$k$ node are neighbors themselves. We investigate how the clustering spectrum $k\mapsto \bar{c}(k)$ scales with $k$ in the hidden variable model and show that $c(k)$ follows a {\it universal curve} that consists of three $k$-ranges where $\bar{c}(k)$ remains flat, starts declining, and eventually settles on a power law $\bar{c}(k)\sim k^{-\alpha }$ with $\alpha$ depending on the power law of the degree distribution. We test these results against ten contemporary real-world networks and explain analytically why the universal curve properties only reveal themselves in large networks.

References in corpus (32)

• The structure and function of complex networks
• Power-law distributions in empirical data
• Epidemic spreading in scale-free networks
• Assortative mixing in networks
• The diameter of the world wide web
• The large-scale organization of metabolic networks
• Random graphs with arbitrary degree distributions and their applications
• Mixing patterns in networks
• Hierarchical Organization in Complex Networks
• Dynamical and correlation properties of the Internet
• Large-scale topological and dynamical properties of Internet
• The statistical mechanics of networks
• The phase transition in inhomogeneous random graphs
• Class of correlated random networks with hidden variables
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Self-similarity of complex networks and hidden metric spaces
• Generating simple random graphs with prescribed degree distribution
• The origin of degree correlations in the Internet and other networks
• Percolation and Epidemic Thresholds in Clustered Networks
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Clustering in complex networks. I. General formalism
• Assortative model for social networks
• Langevin approach for the dynamics of the contact process on annealed scale-free networks
• Network Cosmology
• Structural transitions in scale-free networks
• Clustering of correlated networks
• Deciphering the global organization of clustering in real complex networks
• Critical window for the configuration model: finite third moment degrees
• Clustering of random scale-free networks
• Local clustering in scale-free networks with hidden variables
• Power-law relations in random networks with communities
• Giant component sizes in scale-free networks with power-law degrees and cutoffs

Cited by in corpus (11)

• Scale-free Networks Well Done
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Variational principle for scale-free network motifs
• Triadic closure in configuration models with unbounded degree fluctuations
• Scale-free network clustering in hyperbolic and other random graphs
• Emergence of Long-Range Correlations in Random Networks
• Degree correlations in scale-free null models
• Asymptotics for cliques in scale-free random graphs
• Sharpest possible clustering bounds using robust random graph analysis
• Localized geometry detection in scale-free random graphs
• The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights