Scale-free Networks Well Done

Ivan Voitalov; Pim van der Hoorn; Remco van der Hofstad; Dmitri Krioukov

Source-linked AI summary

Scale-free Networks Well Done

Ivan Voitalov, Pim van der Hoorn, Remco van der Hofstad, Dmitri Krioukov

arXiv:1811.02071v2Nov 5, 2018physics.soc-phcs.SIphysics.data-an

TL;DR

Detecting power laws in real-world network degree distributions is complicated by deviations from ideal pure power laws and estimator instability. This paper defines regularly varying distributions, establishes consistent extreme-value-based estimators, and finds that scale-free networks are not rare.

Problem
Existing power-law detection methods face estimator instability on integer-valued degree sequences, while pure power-law assumptions inadequately represent noisy real-world networks.
Method
The paper defines regularly varying distributions, identifies consistent tail-exponent estimators using extreme value theory, and applies them through a degree-sequence classification scheme.
Results
Application to representative real-world degree sequences reveals significant fractions of networks with power-law degree sequences, confirming that scale-free networks are not rare.
Takeaways & Limitations
Relaxing the requirement of pure power laws yields a broader and more realistic basis for detecting scale-free structure in empirical networks.
Takeaways & Limitations
Regularly varying distributions cannot be subjected to hypothesis testing, so finite-sequence classifications cannot receive statistical weights such as p-values.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper addresses the lack of rigorous definitions and statistically consistent methods for identifying power-law degree distributions by treating power laws as regularly varying distributions. Under this broader framework and state-of-the-art statistical analysis, it concludes that scale-free networks are not rare.

Real-world scale-free networks cannot be assessed rigorously because no widely agreed definition specifies when a degree distribution is power-law or approximately power-law, fueling ongoing controversy [18] [23] [24] [26] [27].
Allowing regularly varying rather than pure power-law degree distributions shows that scale-free networks are definitely not rare.
The paper defines a distribution as power-law when its complementary cumulative distribution function is regularly varying, allowing arbitrary finite-degree deviations while preserving the tail exponent γ.Regularly varying distributions include slowly varying functions and are substantially broader than pure power laws.
It identifies estimators that apply to any regularly varying distribution, converge to the true γ, and can be automated with a double-bootstrap method providing optimal finite-sample estimation.
Unlike methods in, these estimators remain consistent for impure power laws with nontrivial slowly varying functions, including the preferential-attachment model’s degree distribution.
The paper avoids relying on hypothesis tests and p-values, instead consulting multiple consistent γ-estimators and classifying sequences according to whether their estimates agree.

II. POWER-LAW DISTRIBUTIONS

This section defines power-law distributions rigorously as regularly varying distributions, allowing arbitrary behavior at small degrees while preserving a power-law tail. Pure power laws are the special case with a constant slowly varying function, and the definition’s asymptotic nature makes hypothesis testing impossible.

II. POWER-LAW DISTRIBUTIONS: Power-law distributions are defined as regularly varying distributions, whose tail follows a power law modulated by a slowly varying function.This definition permits deviations from a pure power law without changing the tail exponent.
II. POWER-LAW DISTRIBUTIONS: Pure power laws are the special case where the slowly varying function is constant; integer-valued cases are generalized zeta distributions, while continuous cases are Pareto distributions.Pure power laws therefore form only a small subset of regularly varying distributions.
II. POWER-LAW DISTRIBUTIONS: Regular variation constrains only the high-degree tail, so the distribution can take any form below an arbitrarily large fixed threshold.Its asymptotic character formalizes the intuition behind the traditional scale-free formula while allowing non-power-law behavior at finite degrees.
II. POWER-LAW DISTRIBUTIONS: Because regular variation is intrinsically asymptotic, hypothesis testing with regularly varying distributions is impossible.The definition concerns the limit k →∞ and leaves behavior below arbitrarily large thresholds unrestricted.

III. CONSISTENT ESTIMATORS OF THE TAIL EXPONENT

The section develops three statistically consistent extreme-value estimators—Hill, Moments, and Kernel —for the tail exponent of regularly varying distributions. Their guarantees require i.i.d. samples, while their tail-focused tuning and bootstrap selection support finite-sample application without breaking consistency.

Estimator choice: Hill, Moments, and Kernel consistently estimate the extreme value index ξ, which determines the power-law exponents for regularly varying distributions.Consistency means the estimate converges to the true ξ as sample size increases, regardless of the slowly varying component.
Assumptions and scope: The consistency results assume i.i.d. samples from a regularly varying distribution, while extending the proofs to other network models remains an open research area.The authors state that no hypothesis test can rigorously justify these assumptions for a given real-world degree sequence.
Interpretation: Negative or near-zero ξ estimates indicate that a degree sequence is unlikely to come from the Fréchet MDA, hence unlikely to be regularly varying.This diagnostic is explicitly qualitative: the authors note that its unlikeliness cannot be quantified rigorously.
Order-statistic tuning: The estimators use the κ largest order statistics, but consistency requires κ to diverge with n while remaining smaller than n to limit tail fluctuations and slowly varying-function effects.Using all n observations would allow the slowly varying function to affect the estimate.
Order-statistic tuning: The double-bootstrap method selects an optimal κ* by minimizing estimation error and is proven to preserve consistency because κ* grows sublinearly with n.The authors therefore identify Hill, Moments, and Kernel as the maximal subset of consistent, stable, and efficient estimators with a bootstrap procedure proven both optimal and consistent.

IV. EVALUATION OF ESTIMATOR PERFORMANCE

Appendix D evaluates three extreme-value estimators on synthetic distributions and network-model degree sequences, finding convergence under regular variation and even when network degrees are not i.i.d. Compared with PLFit [19, 20], the EV estimators match it on sufficiently nice distributions but substantially outperform it when distributions depart from pure power laws.

Extreme-value estimators: All three EV estimators converge to the true ξ for regularly varying distributions but fail to converge for distributions that are not regularly varying.They also converge for sequences of non-regularly-varying distributions that converge to a regularly varying distribution.
Network-model evaluation: The EV estimators converge on degree sequences from network models even though individual degrees are not i.i.d. samples from a fixed degree distribution.The evaluation covers the configuration model, preferential attachment, and random hyperbolic graphs, alongside random sequences sampled from various distributions.
PLFit comparison: The EV estimators significantly outperform PLFit [19, 20] when distributions are not sufficiently nice or are further from pure power laws.When distributions are sufficiently nice, PLFit’s estimation accuracy and convergence rates are comparable to those of the EV estimators; PLFit performs poorly when small-degree regions suggest incorrect power-law exponents.

V. POWER-LAW DEGREE SEQUENCES

For regularly varying degree distributions, hypothesis testing is impossible because the class is nonparametric and infinite-dimensional, while finite samples may conceal or mimic power-law tails. The paper therefore advocates a conservative classification based on the three exponent estimators, while noting that applying it to networks with multiple degree sequences involves judgment.

Hypothesis testing cannot rigorously establish regular variation because slowly varying functions create an infinite-dimensional, nonparametric distribution class.Testing a finite sample against this family is therefore analogous to testing whether one number came from a specified distribution, which is impossible.
Finite samples provide no guaranteed accuracy or known convergence onset, since the slowly varying function can obscure the true tail over arbitrarily large sample ranges.Unlike parametric families, the required sample size for estimators or tests to reveal convergence is unknown when ℓ(k) may be arbitrarily bad.
Adversarial examples show that samples can hide a genuine Pareto tail or falsely suggest one, with detectable behavior emerging only after sample sizes exceed the relevant tail-scale threshold.For the mixture example, signs of the tail require n sufficiently larger than 1/f; for the non-regularly-varying example, deviations appear only when n exceeds cγ^-1, as confirmed in Fig. 1.
The paper adopts a conservative power-law definition based on the ξ values returned by its three estimators rather than formal hypothesis-test probabilities.The proposed threshold for a hardly-power-law regime is explicitly arbitrary, and the authors note that all-positive ξ values could alternatively define power-law sequences.
For networks with directed, multipartite, multilayer, multiplex, or temporal structure, labeling the network power-law depends on which of its multiple degree sequences are considered.The authors characterize this choice as a matter of taste unless it is tied to a specific network question, such as disease spread.

VI. REAL-WORLD NETWORKS

Applying Hill, Moments, and Kernel estimators to filtered KONECT degree sequences, the study finds that many previously identified power-law networks are confirmed while known non-power-law examples are rejected. Across network types, power-law degree sequences are common, including substantial fractions with divergent second moments.

VI. REAL-WORLD NETWORKS: The analysis applies Hill, Moments, and Kernel estimators to 115 filtered KONECT networks, covering undirected, directed, and bipartite network types.Temporal, unavailable, duplicate, incomplete, self-loop, and multi-edge cases are excluded through the stated preprocessing steps.
VI. REAL-WORLD NETWORKS: The estimators classify many previously reported power-law networks—including Internet, WWW, protein-interaction, social-membership, citation, and recommendation networks—as power-law, while known non-power-law networks are classified otherwise.Examples classified as not power-law include the California road network and Amazon's directed out-degree sequence.
VI. REAL-WORLD NETWORKS: Because finite degree sequences can yield different exponent estimates, the study emphasizes using multiple consistent estimators that may examine different parts of a distribution.This issue is especially relevant when the slowly varying function ℓ(k) is nontrivial, motivating the maximal subset of stable and efficient estimators with a theoretically justified bootstrap choice of order statistics.
VI. REAL-WORLD NETWORKS: The resulting prevalence estimates present a substantially different picture from the earlier comparison in, although the results cannot be directly compared.The comparison is presented as a qualitative contrast rather than a direct numerical evaluation.

VII. CONCLUSION AND DISCUSSION · Appendix A: Classes of distributions with heavy tails

The paper defines power laws as regularly varying distributions and uses consistent extreme-value estimators to show that scale-free networks are not rare. The discussion identifies important limitations and open problems, while Appendix A situates regularly varying distributions within the broader heavy-tailed taxonomy.

VII. CONCLUSION AND DISCUSSION: Power laws are defined as regularly varying distributions, with Pareto and zeta distributions as a small pure-power-law subset.Regular variation provides an inclusive framework for formalizing the “straight line on log-log scale” intuition in real-world networks.
VII. CONCLUSION AND DISCUSSION: Extreme-value theory supplies consistent tail-exponent estimators and a classification scheme for degree sequences.The approach uses the connection between regularly varying distributions and the maximum domain of attraction of the Fréchet distribution.
VII. CONCLUSION AND DISCUSSION: Regular-variation classification does not address the network mechanisms that may generate power-law distributions.Mechanisms correspond to different network models approximating stochastic processes driving network evolution, making them a separate subject.
VII. CONCLUSION AND DISCUSSION: Finite-sample regular-variation claims cannot receive statistical weight such as a p-value because hypothesis testing is impossible for regularly varying distributions.The discussion therefore emphasizes improving other aspects of empirical power-law detection rather than attaching significance values to finite sequences.
VII. CONCLUSION AND DISCUSSION: Open problems include relaxing i.i.d. assumptions, establishing convergence speed, handling sequences of network snapshots, and designing reliable estimators for integer-valued degrees.Existing estimators converge in the considered experiments, but convergence proofs beyond preferential attachment are unavailable, and integer-valued data can cause instability and slow convergence.
VII. CONCLUSION AND DISCUSSION: The double-bootstrap consistency proof requires a second-order condition violated by Pareto and zeta distributions, despite convergence in experiments.Thus, empirical convergence in these cases lacks the corresponding consistency proof.
VII. CONCLUSION AND DISCUSSION: Consistent estimators applied to representative real-world degree sequences confirm that scale-free networks are not rare.The estimators represent the current state of the art in rigorous empirical power-law detection, with an implementation available in.
Appendix A: Classes of distributions with heavy tails: Heavy-tailed distributions form the broadest class in Appendix A, characterized by tails that decay more slowly than exponentially.The appendix reviews this taxonomy and introduces regularly varying distributions as the simplest frequently encountered class.

1. Heavy-tailed distributions … 1. Extreme value distributions and their maximum domains of attraction

The paper narrows the broad class of heavy-tailed distributions to regularly varying distributions, which retain useful tail properties while offering a tractable representation for inference. It then connects regular variation to Fréchet extreme-value limits and uses this framework to estimate tail exponents.

1. Heavy-tailed distributions: Heavy-tailed distributions have CCDFs that decay more slowly than exponentially, but the class is broad and difficult to handle in full generality.Long-tailed and subexponential distributions are narrower subclasses; regularly varying distributions form a particularly tractable subclass of the latter.
1. Heavy-tailed distributions: Regularly varying distributions inherit subexponential behavior: sufficiently large sums are typically caused by one unusually large summand rather than many moderate terms.The regularly varying class is strictly narrower than the heavy-tailed class but has a concise representation useful for statistical inference.
2. Regularly varying distributions: Regularly varying distributions are defined by CCDFs that equal a power function times a slowly varying function, and the paper uses this class as its definition of power-law distributions.They can model high variability, but failure of regular variation does not imply that a distribution is neither heavy-tailed nor subexponential; the lognormal is a subexponential counterexample.
3. Simplest examples of regularly varying distributions: Regular variation is preserved in practical degree-distribution constructions, including flooring a Pareto variable and mixing a Poisson distribution with Pareto means.Mixed Poisson distributions have the same expected value and tail exponent as their Pareto mixing variables and arise in hidden-variable and graphon-based network models.
Appendix B: Consistent estimators for tail exponents of regularly varying distributions: The estimators used for tail exponents are designed for extreme-value indices and are consistent under the broader assumption that the distribution lies in an extreme-value maximum domain of attraction.Every regularly varying distribution satisfies this assumption, motivating the extreme-value-theory framework.
1. Extreme value distributions and their maximum domains of attraction: Extreme-value theory studies whether normalized maxima converge to a non-degenerate limit, with the limit classified by an index parameter ξ.A distribution belongs to an extreme-value maximum domain of attraction when suitable location and scale sequences make its normalized maxima converge.
1. Extreme value distributions and their maximum domains of attraction: Regular variation is exactly equivalent to belonging to the Fréchet maximum domain of attraction, and a tail exponent γ corresponds to the extreme-value index ξ = 1/(γ−1).Thus, the estimators estimate the Fréchet index associated with the regularly varying tail exponent.

2. Hill’s estimator … Appendix C: Estimating the tail exponent of an empirical degree sequence

The paper presents consistent tail-exponent estimators spanning regularly varying distributions and broader extreme-value domains, while addressing finite-sample irregularity and practical issues in empirical degree sequences. It then applies these methods to synthetic and real-world network data using technically specified procedures.

2. Hill’s estimator: Hill’s estimator is consistent for every regularly varying distribution with tail exponent γ > 1 when κ/n → 0 and κ → ∞.This follows from Theorems 4.1 and 4.2 in.
3. Moments estimator: The Moments estimator extends consistency beyond Fréchet-domain distributions to all extreme-value domains, under κ/n → 0, κ → ∞, and log(n)^δ/κ → 0.The estimator converges almost surely for any ξ ∈ R when these conditions hold for some δ > 0.
4. Kernel estimator: The Kernel estimator is consistently applicable for any ξ ∈ R when n → ∞, h → 0, and hn → ∞.It uses a user-chosen kernel φ and a parameter λ > 1/2 to avoid possible singularities.
Appendix C: Estimating the tail exponent of an empirical degree sequence: For empirical degree sequences, the Kernel estimator scans logarithmically spaced fractions h_i ∈ [1/n, 1], using s = [0.3n] values to examine the tail more densely.The implementation selects κ* = ⌊nh*⌋ after finding the optimal h* with the prescribed kernel procedure.
5. Smooth Hill estimator: The smooth Hill estimator averages Hill estimates over [κ + 1, rκ], suppressing erratic finite-sample behavior while remaining consistent for every integer r ≥ 2.This makes its stable region easier to identify than with the original Hill estimator.
6. Pickands estimator: The Pickands estimator is consistent for any ξ ∈ R and provides a practical check of whether regular variation is plausible.If its function of κ is entirely negative, the regularly varying assumption is difficult to support.
6. Pickands estimator: Pickands estimates can be undefined for tied integer-valued data and are volatile, inefficient, and high-variance, but uniform noise resolves ties consistently.The estimator’s drawbacks motivated generalized Pickands variants.

1. Finding the optimal number of order statistics

Because finite-sample estimators depend on the number of largest observations κ, the paper selects κ using an AMSE-based double bootstrap. This choice is theoretically consistent under a second-order condition, although experiments find good performance even when that condition fails.

1. Finding the optimal number of order statistics: Finite empirical degree sequences leave κ as a free parameter because estimators use only the κ largest samples, while consistency is established only as both κ and n diverge.The section therefore focuses on selecting κ∗ rather than treating the asymptotic consistency result as an automatic finite-sample prescription.
1. Finding the optimal number of order statistics: The AMSE-based double bootstrap estimates an optimal κ∗ by combining two consistent estimators across bootstrap samples, and is chosen for its consistency, stability, and applicability.It minimizes empirical asymptotic mean squared error and repeats the procedure at two bootstrap sample sizes before selecting κ for the original data.
1. Finding the optimal number of order statistics: The implementation defaults to r = 500 bootstrap samples and t = 1/2, making the second bootstrap sample size n2 = n/2.Here, r is the number of bootstrap samples and t determines the first and second bootstrap sample sizes.
1. Finding the optimal number of order statistics: The bootstrap consistency proofs require a second-order condition, so convergence is not guaranteed for distributions that lack it, although experiments find good performance in such cases.The paper notes that the condition can be difficult or impossible to verify in real-world data, while the resulting estimates nevertheless quickly converge toward the true value in experiments.

2. Working with integer data

Integer-valued degree sequences can make otherwise consistent power-law estimators unstable, so the paper adds uniform symmetric noise before estimation to improve stability without changing the tail exponent.

2. Working with integer data: Rounding continuous regularly varying samples can make consistent estimators behave erratically as functions of the sampled sequence and the number of order statistics κ.The instability arises even though the rounded sequences remain regularly varying with the same exponent.
2. Working with integer data: Uniform symmetric noise substantially improves estimator stability and convergence on integer-valued sequences without changing the tail exponent.For y_i = x_i + u_i, the noise variables u_i are i.i.d. uniform on [−1/2, 1/2].
2. Working with integer data: Without added noise, the three estimators have larger relative root mean squared error on integer samples from Zeta distributions than with noise.Figure 5 evaluates varying sequence lengths n and exponents γ.

3. Example of the estimator operation using the double bootstrap method

The double-bootstrap example shows that consistent estimators can examine different portions of finite empirical degree distributions, producing different estimates when slowly varying functions are nontrivial. Using multiple consistent estimators is therefore recommended for real-world network data.

Estimator operation: Different consistent estimators may explore different parts of a finite empirical degree distribution, explaining why they can return different estimates.This is especially relevant when the slowly varying function ℓ(k) is not trivial.
Estimator operation: The Hill estimator gives a higher α = 1/ξ estimate for Libimseti’s in-degree sequence because its optimal κ∗ is substantially smaller than those of the other estimators.Hill therefore analyzes a smaller portion of the distribution tail; its κ∗ is selected by minimizing the AMS criterion.
Estimator convergence: For small samples from regularly varying distributions, estimator convergence can differ between “nice” and “not so nice” slowly varying functions ℓ(k).The estimators converge to the true ξ for any ℓ(k) only in the infinite-sample limit n →∞, while the convergence speed may depend on unknown properties of ℓ(k).
Practical recommendation: Applying as many consistent estimators as possible is the recommended strategy for real-world network data.The recommendation follows from finite-sample differences caused by estimators examining different distribution regions and by uncertain convergence behavior.

Appendix D: Evaluation on synthetic sequences and network models

Appendix D evaluates extreme-value-theory estimators on synthetic degree sequences and network models, comparing them with PLFit.

Evaluation setup: The Hill, Moments, and Kernel estimators use extreme-value theory with a double-bootstrap procedure.The appendix uses the code in.
Evaluation setup: These estimators are evaluated on synthetic degree sequences and network models to assess whether they yield expected results.
Estimator comparison: The appendix compares their estimates with PLFit, which combines maximum-likelihood-inspired techniques with Kolmogorov-Smirnov distance minimization.

1. Synthetic sequences

Synthetic sequences spanning clean, mixed, cutoff, and double-power-law distributions test estimator accuracy across sample sizes and tail exponents. EV estimators converge for regularly varying data and fail for fixed non-regularly-varying data, while PLFit is strongest on clean zeta data but otherwise often comparable.

1. Synthetic sequences: The benchmark covers synthetic sequences from diverse network-relevant distributions, including zeta, Pareto-mixed Poisson, exponential-cutoff Pareto, and double power law families.Sequences discard zero entries when distributions include degree zero, and vary sequence length, tail exponent, and distributional form.
1. Synthetic sequences: Double power laws are regularly varying with exponent γ, but small samples may make estimators identify the lower-tail exponent γ0 instead.The experiments set γ0 = 1.5, c = 500, and r = 0.1 while varying γ.
1. Synthetic sequences: EV estimators converge on regularly varying sequences and on diverging-cutoff distributions, but no estimator converges for a fixed non-regularly-varying cutoff.The experiments use 100 sequences per distribution, exponent, and sample-size combination and evaluate relative root-mean-squared error.
1. Synthetic sequences: PLFit has lower estimation error for the clean zeta distribution, whereas EV and PLFit accuracy and convergence rates are comparable for reasonably nice regularly varying distributions.The zeta distribution has constant slowly varying function ℓ(k), while quickly converging ℓ(k) makes the estimators comparable.

2. Network models

The study evaluates EV-based tail-exponent estimators on three non-i.i.d. network-model degree sequences across multiple exponents and network sizes. All EV estimators converge, and they outperform PLFit in preferential attachment for γ = 2.1 and γ = 3.

Network models: The experiments use erased configuration, preferential attachment, and hyperbolic random graph models whose degree distributions converge to regularly varying limits.These models provide non-i.i.d. degree sequences for testing whether EV-estimator performance is affected by dependence.
Experimental design: For each model, the study varies γ ∈ {2.1, 2.5, 3.0} and network size n from 10^3 to 10^6, generating 100 random networks per combination.The resulting degree sequences are analyzed with all considered estimators using RRMSE (D7).
Results: All EV estimators converge despite the degree sequences being non-i.i.d., although convergence is slow when finite-network degree distributions approach their limiting distributions slowly.For HRGs with γ = 2.1, convergence is especially slow because the Pareto-mixed Poisson limit is approached more slowly as γ nears 2.
Results: In preferential attachment, EV estimators clearly outperform PLFit for γ = 2.1 and γ = 3, while all estimators are on par for γ = 2.5.Performance is measured by relative root mean squared error (RRMSE) across the network models, exponents, and sizes shown in Fig. 9.

3. Anatomy of the PLFit

PLFit combines likelihood maximization over candidate exponents with KS-distance minimization over degree thresholds, assuming a pure power-law tail above the selected threshold. Its errors arise because KS minimization selects overly small thresholds, after which MLE estimates a local PDF slope rather than the asymptotic tail exponent.

Algorithm: PLFit selects the exponent and threshold jointly by maximizing a generalized-zeta likelihood over candidate γ values and minimizing the KS distance across observed degree thresholds.The returned estimates are the γ and k_min associated with the smallest KS distance.
Consequences: For double power laws and preferential attachment, PLFit converges more slowly than the considered extreme-value estimators, and its estimates can be substantially wrong when the local slope differs from the true tail exponent.Applying KS testing with such inaccurate estimates can then reject the pure-power-law hypothesis because the estimated and true exponents differ.
KS distance minimization: KS minimization drives PLFit toward erroneously low k_min values because regularly varying distributions contain more observations near smaller degrees, reducing local empirical-CDF deviations.Figure 10 illustrates this mechanism on a double power-law sample.
Likelihood maximization: With small k_min, PLFit’s MLE component mainly fits the log-log PDF slope near that threshold rather than the asymptotic tail exponent.This explains why PLFit can be accurate in some cases but substantially off when the local and tail slopes differ.