Scale-free Networks Well Done

Abstract

We bring rigor to the vibrant activity of detecting power laws in empirical degree distributions in real-world networks. We first provide a rigorous definition of power-law distributions, equivalent to the definition of regularly varying distributions that are widely used in statistics and other fields. This definition allows the distribution to deviate from a pure power law arbitrarily but without affecting the power-law tail exponent. We then identify three estimators of these exponents that are proven to be statistically consistent -- that is, converging to the true value of the exponent for any regularly varying distribution -- and that satisfy some additional niceness requirements. In contrast to estimators that are currently popular in network science, the estimators considered here are based on fundamental results in extreme value theory, and so are the proofs of their consistency. Finally, we apply these estimators to a representative collection of synthetic and real-world data. According to their estimates, real-world scale-free networks are definitely not as rare as one would conclude based on the popular but unrealistic assumption that real-world data comes from power laws of pristine purity, void of noise and deviations.

References in corpus (30)

• Emergence of scaling in random networks
• Power-law distributions in empirical data
• Synchronization in complex networks
• Critical phenomena in complex networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks
• Hyperbolic Geometry of Complex Networks
• Scale-free networks are rare
• Organization of Growing Random Networks
• Scale-Free Networks are Ultrasmall
• Problems with Fitting to the Power-Law Distribution
• The phase transition in inhomogeneous random graphs
• Navigability of Complex Networks
• Class of correlated random networks with hidden variables
• Generating simple random graphs with prescribed degree distribution
• Cut-offs and finite size effects in scale-free networks
• Quantifying randomness in real networks
• Parameter estimation for power-law distributions by maximum likelihood methods
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Network Cosmology
• Power-law size distributions in geoscience revisited
• Quasi-Periodic Oscillations and broadband variability in short magnetar bursts
• The Workshop on Internet Topology (WIT) Report
• Testing statistical laws in complex systems
• Hyperbolic Graph Generator
• Scale-free networks as preasymptotic regimes of superlinear preferential attachment
• Non-characteristic Half-lives in Radioactive Decay
• Clustering Spectrum of scale-free networks
• Smooth tail index estimation
• How likely is an i.i.d. degree sequence to be graphical?

Cited by in corpus (62)

• Robustness and resilience of complex networks
• Network Geometry
• Modular gateway-ness connectivity and structural core organization in maritime network science
• True scale-free networks hidden by finite size effects
• Deep learning of contagion dynamics on complex networks
• Link prediction with hyperbolic geometry
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Inequality and Inequity in Network-based Ranking and Recommendation Algorithms
• Impact of the distribution of recovery rates on disease spreading in complex networks
• Avoiding the bullies: The resilience of cooperation among unequals
• The distinct flavors of Zipf's law in the rank-size and in the size-distribution representations, and its maximum-likelihood fitting
• The brevity law as a scaling law, and a possible origin of Zipf's law for word frequencies
• Tackling the subsampling problem to infer collective properties from limited data
• Heavy tails and pruning in programmable photonic circuits
• Universal transient behavior in large dynamical systems on networks
• The nature and nurture of network evolution
• Truncated lognormal distributions and scaling in the size of naturally defined population clusters
• Classical Information Theory of Networks
• Circulation of a digital community currency
• Universal patterns in egocentric communication networks
• On the emergence of Zipf's law in music
• Identifying time dependence in network growth
• Topological properties and organizing principles of semantic networks
• Random hyperbolic graphs in $d+1$ dimensions
• Classes of critical avalanche dynamics in complex networks
• Long-tailed distributions of inter-event times as mixtures of exponential distributions
• Scale-Free Networks beyond Power-Law Degree Distribution
• Weighted hypersoft configuration model
• Effect of expanding learning scope on the evolution of cooperation in scale-free networks
• Lognormals, Power Laws and Double Power Laws in the Distribution of Frequencies of Harmonic Codewords from Classical Music
• Uncovering hidden dependency in weighted networks via information entropy
• Critical Phenomena and Strategy Ordering with Hub Centrality Approach in the Aspiration-based Coordination Game
• Tail of the distribution of fatalities in epidemics
• Network science Ising states of matter
• Explaining the emergence of complex networks through log-normal fitness in a Euclidean node similarity space
• Exponential rate of epidemic spreading on complex networks
• Finite-time scaling for epidemic processes with power-law superspreading events
• Non-parametric power-law surrogates
• Connectedness matters: Construction and exact random sampling of connected graphs
• From Boltzmann to Zipf through Shannon and Jaynes
• Learning the mechanisms of network growth
• Network Cards: concise, readable summaries of network data
• War pact model of shrinking networks
• A measure for characterizing heavy-tailed networks
• Flow of temporal network properties under local aggregation and time shuffling: a tool for characterizing, comparing and classifying temporal networks
• Stochastic resetting in a networked multiparticle system with correlated transitions
• Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
• Degree distributions in networks: beyond the power law
• Degree distributions under general node removal: Power-law or Poisson?
• A Compounded Burr Probability Distribution for Fitting Heavy-Tailed Data with Applications to Biological Networks
• Emergence of Multivariate Extremes in Multilayer Inhomogeneous Random Graphs
• Asymptotics for cliques in scale-free random graphs
• Modified Lomax Model: A heavy-tailed distribution for fitting large-scale real-world complex networks
• Sharpest possible clustering bounds using robust random graph analysis
• Equivalence of inequality indices in the three-dimensional model of informetric impact
• Exploring the space of graphs with fixed discrete curvatures
• Tail Index Estimation for Discrete Heavy-Tailed Distributions
• Italian Business-to-Business Invoicing Data: A Network Analysis
• Distinguishing subsampled power laws from other heavy-tailed distributions
• Likelihood-based Inference for Random Networks with Changepoints
• Robust subgraph counting with distribution-free random graph analysis
• Poisson approximation for cycles in the generalised random graph