Power-law distributions in empirical data

Aaron Clauset; Cosma Rohilla Shalizi; M. E. J. Newman

Source-linked AI summary

Power-law distributions in empirical data

Aaron Clauset, Cosma Rohilla Shalizi, M. E. J. Newman

arXiv:0706.1062v2Jun 7, 2007physics.data-ancond-mat.dis-nnstat.APstat.ME

TL;DR

Power-law data are difficult to identify and characterize because tail fluctuations and fitting-range choices can make standard analyses unreliable and cannot establish whether a power law is plausible. The paper develops a statistically principled framework combining parameter estimation with goodness-of-fit and model-comparison tests, finding that power-law hypotheses are supported for some real-world data sets but incompatible with others.

Problem
Researchers lack reliable ways to determine whether empirical data plausibly follow a power law and to select the valid lower-bound range for fitting.
Method
The paper combines maximum-likelihood parameter estimation with Kolmogorov-Smirnov goodness-of-fit tests and likelihood-ratio comparisons of alternative models.
Results
Across many real-world data sets, power-law hypotheses were statistically reasonable for some but incompatible with the observed data for others.
Takeaways & Limitations
Straight-line behavior on doubly logarithmic plots is insufficient for validating power laws, which require statistical testing and may remain compatible with other distributions.
Takeaways & Limitations
For very small data sets, parameter-estimator biases can be significant, and reliable estimates generally require approximately n ≳50 observations.

Abstract

from arXiv · show

Power-law distributions occur in many situations of scientific interest and have significant consequences for our understanding of natural and man-made phenomena. Unfortunately, the detection and characterization of power laws is complicated by the large fluctuations that occur in the tail of the distribution -- the part of the distribution representing large but rare events -- and by the difficulty of identifying the range over which power-law behavior holds. Commonly used methods for analyzing power-law data, such as least-squares fitting, can produce substantially inaccurate estimates of parameters for power-law distributions, and even in cases where such methods return accurate answers they are still unsatisfactory because they give no indication of whether the data obey a power law at all. Here we present a principled statistical framework for discerning and quantifying power-law behavior in empirical data. Our approach combines maximum-likelihood fitting methods with goodness-of-fit tests based on the Kolmogorov-Smirnov statistic and likelihood ratios. We evaluate the effectiveness of the approach with tests on synthetic data and give critical comparisons to previous approaches. We also apply the proposed methods to twenty-four real-world data sets from a range of different disciplines, each of which has been conjectured to follow a power-law distribution. In some cases we find these conjectures to be consistent with the data while in others the power law is ruled out.

1. Introduction.

Power laws arise across diverse natural and man-made phenomena, but empirical power-law behavior usually applies only in distribution tails and cannot be established with certainty. The paper develops methods for recognizing such behavior and applies them to real-world data sets, finding that some claims are supported while others are ruled out.

Motivation: Power laws have attracted attention because of their mathematical properties and occurrence in diverse natural and man-made phenomena.Examples include city populations, earthquake intensities, and power-outage sizes.
Interpretation: Power-law data can be poorly represented by typical or average values because a significant fraction of observations may lie several orders of magnitude above them.The discussion uses city populations and the average U.S. village population as an example.
Power-law behavior: In practice, power-law behavior usually applies only above a minimum value xmin, so only the distribution tail follows a power law.Few empirical phenomena obey power laws for all values of x.
Methodological challenge: Observed data rarely establish a power law with certainty; they can instead be shown to be consistent with the hypothesis or used to rule out competing hypotheses.The paper frames power-law recognition as a recurring issue in the scientific literature.
Empirical evaluation: The authors apply their methods to many real-world data sets previously claimed to follow power laws, finding that several are ruled out while others remain plausible.For some data sets, the power-law hypothesis appears good or is not firmly ruled out.

2. Definitions.

Power-law distributions are defined in continuous and discrete forms, with a lower cutoff xmin required because the distribution diverges at zero. The paper also outlines a three-step analysis recipe and cautions that continuous approximations to discrete power laws can be unreliable.

Definitions: Power-law distributions come in continuous and discrete forms, with the latter restricted here to integer-valued quantities.Continuous distributions govern real numbers, whereas discrete distributions govern quantities taking discrete values, typically positive integers.
Definitions: Both continuous and discrete power laws require a lower bound xmin > 0 because their distributions diverge at zero.For the continuous case, the model requires α > 1 for normalization; the discrete case also requires xmin > 0.
Analysis recipe: The proposed analysis estimates xmin and α, tests goodness of fit using a p-value threshold of 0.1, and compares alternatives with likelihood ratios.A p-value greater than 0.1 indicates a plausible power-law hypothesis; otherwise it is rejected, while the sign of a significant likelihood ratio identifies the favored model.
Definitions: The complementary cumulative distribution function is defined for both cases as P(x) = Pr(X ≥ x).The CDF is useful for analyzing power-law distributed variables and is denoted P(x).
Definitions: Continuous approximations to discrete power laws can be reasonable or unreliable, depending on the approximation method.The paper discusses such approximations particularly for estimating scaling parameters and generating power-law random numbers.

3. Fitting power laws to empirical data.

The paper develops a principled framework for fitting power laws by estimating α and xmin, replacing fragile regression-based approaches with maximum-likelihood and goodness-of-fit methods. It recommends the KS method for estimating xmin while noting finite-sample bias and that fitting alone cannot establish whether a power law is plausible.

Motivation: Least-squares regression on log-transformed histograms is a common approach, but it can assert power-law behavior from an approximately straight line without independently testing the fit.The slope is interpreted as α, although the method provides no decisive goodness-of-fit assessment.
Estimating α: The approximate maximum-likelihood estimator gives α estimates accurate to about 1% or better when xmin ≳6, provided high accuracy is not required.The approximation is easier to evaluate than the exact discrete MLE, with its bias discussed separately.
Estimating xmin: Estimating xmin is essential because power-law behavior may begin only above a lower bound, and choosing xmin too low can bias the subsequent estimate of α.Samples below xmin should be discarded before calculating α.
Estimating xmin: The KS method generally outperforms BIC for estimating xmin, which tends to underestimate xmin, so the paper recommends KS for general applications.The KS method performs well for both discrete and continuous synthetic data and is sensitive to deviations near xmin.
Estimating xmin: Good xmin estimates can be obtained with about 1000 or more observations in the power-law tail, although the required number depends on the distribution.Performance depends principally on ntail rather than the total sample size.
Goodness of fit: Fitting a power law estimates α and xmin but does not determine whether the model plausibly matches the data, requiring a separate goodness-of-fit test.A power law can always be fitted regardless of the true generating distribution.

4. Testing the power-law hypothesis.

The section presents a Monte Carlo goodness-of-fit procedure for testing whether empirical data plausibly follow a power law, addressing the deceptive similarity of non-power-law distributions. It emphasizes conservative interpretation because large p-values do not establish correctness, especially for small samples or large xmin.

Testing the power-law hypothesis.: Visually similar CDFs from power-law, log-normal, and exponential samples show that graphical inspection alone cannot reliably identify power-law behavior.All three samples have n = 100 and appear roughly straight on logarithmic scales, although only one is a true power law.
Testing the power-law hypothesis.: The procedure compares the empirical KS statistic with statistics from many synthetic data sets generated under the fitted power-law model.Each synthetic data set is independently fit to its own power law before its KS statistic is calculated, ensuring the empirical and synthetic analyses are equivalent.
Testing the power-law hypothesis.: The power-law hypothesis is conservatively ruled out when p ≤0.1.This threshold means the model is rejected when there is a probability of 1 in 10 or less of obtaining data that agree with it as poorly by chance.
Testing the power-law hypothesis.: A large p-value does not prove that the power law is correct because alternative distributions may fit equally well or better.Additional tests are needed to rule out competing distributions over the observed range.
Testing the power-law hypothesis.: High p-values require caution when n is small, because limited data can make an incorrect power law difficult to reject.The method’s ability to distinguish models improves with sample size, while increasing xmin reduces the usable tail and raises the n needed to reach p = 0.1.

5. Alternative distributions.

The section explains how likelihood ratios and p-values compare power laws with alternative distributions, while emphasizing that statistical evidence cannot establish a power law against every possible model. Synthetic tests show that incorporating p-values improves discrimination and identifies when the data are insufficient for a firm choice.

Comparing alternative distributions: Comparing a power law with plausible alternatives using their p-values strengthens the case for a power law when its p-value is high and competitors’ are small.A high power-law p-value does not prove correctness, but small competing-distribution p-values rule out those alternatives.
Limitations: Alternative-distribution comparisons cannot cover infinitely many models, and flexible families with many parameters can fit data better than a power law.Consequently, distribution fitting should combine statistical tests with awareness of model flexibility and extrapolation consequences.
Likelihood ratio test: The likelihood ratio test compares two distributions through their data likelihoods, with the sign of log likelihood ratio R indicating which fit is better.A positive, negative, or zero R favors the first distribution, the second, or neither, respectively.
Likelihood ratio test: Because sampling fluctuations can reverse the sign of R, a Vuong-based p-value assesses whether the observed preference is statistically significant.If p < 0.1, the observed sign is unlikely to be a chance result of fluctuations.
Synthetic validation: Using p-values to classify data as power-law, log-normal, or undecided reduced misclassifications to a few parts per thousand, even for modest sample sizes.Classifying solely by the raw sign of R produced uncomfortably many errors at moderate sample sizes.

6. Applications to real-world data.

Analysis of 24 diverse real-world data sets found that 17 were consistent with power-law distributions, while seven were firmly ruled out. Only word frequencies provided a truly convincing power-law fit, and alternative distributions often remained difficult to distinguish.

Limitations: Sampling bias may affect several subsets, including protein interactions, citations and authorships, and Internet data, and the analysis does not correct for these biases.Many data sets are subsets of larger entities, and some sampling procedures are known to be biased.
Power-law fits: Power-law parameter estimates can differ substantially from ad hoc results, exemplified by the protein-interaction scaling parameter of 3.1 ± 0.3 versus a previously reported 2.44.The reported value of 2.44 is described as incompatible with the fitted value of 3.1 ± 0.3.
Power-law fits: 17 of 24 data sets are consistent with a power-law distribution, while HTTP connections, earthquakes, web links, fires, wealth, web hits, and the metabolic network are ruled out.The excluded data sets have very small probabilities of producing fits as poor as those observed by chance.
Power-law fits: Word frequencies in English text are the only data set for which the power law is truly convincing, with an excellent fit and no credible alternative.This conclusion requires both a strong fit and the absence of support for competing forms.
Alternative distributions: Log-normal and stretched-exponential comparisons are often inconclusive, leaving birds, books, cities, religions, wars, citations, papers, proteins, and terrorism plausible under all three forms.The authors emphasize that distinguishing log-normal from power-law behavior is extremely difficult.
Alternative distributions: A cut-off power law is clearly favored for almost a dozen data sets, including forest fires, solar flares, earthquakes, web hits, web links, telephone calls, the Internet, email address books, and mammal species.For surnames, the cut-off form is favored only weakly; elsewhere, large p-values provide no statistical reason to prefer it over the pure form.

7. Conclusions.

The paper rejects log-log histogram straightness as sufficient evidence of power-law behavior and presents statistically principled methods for validating and quantifying such claims. Applied across many data sets, these methods find power laws plausible in some cases but ruled out in others, often alongside alternative heavy-tailed models.

Conclusions: Log-log histogram straightness is necessary but insufficient evidence for true power-law behavior.The authors argue that identifying and quantifying power laws from approximately straight-line histograms on doubly logarithmic plots should not be trusted alone.
Conclusions: The proposed techniques provide objective evidence for or against whether a particular distribution follows a power law.The framework combines statistically principled validation and quantification methods and could, in principle, be extended to other distributions.
Conclusions: Across data sets from various fields, many are statistically compatible with power laws, while the remaining cases rule out the power-law hypothesis.Compatibility with a power law does not exclude compatibility with alternatives such as log-normal or stretched exponential distributions.
Conclusions: Heavy-tailed behavior can remain scientifically relevant even when careful analysis cannot establish an exact power-law distribution.The authors note that some questions may depend on heavy tails rather than perfect power-law adherence, including several Internet measurements that appear power-law-like visually.

Appendix A. Linear regression and power laws.

Appendix A explains that power-law exponents are often estimated by fitting histograms or cumulative distributions with least-squares linear regression. It cautions that this procedure can produce large systematic errors and unreliable uncertainty estimates.

Fitting procedure: Least-squares regression fits a histogram or cumulative distribution to a linear form, interpreting the slope as the scaling-parameter estimate α̂.Standard software can provide slope estimates and standard errors.
Problems with regression: The fitted slope can have systematic and potentially large errors, making least-squares estimates inaccurate for power-law data.The passage refers to supporting evidence from Table 3.1 and Fig. 3.2.
Problems with regression: Regression-based error estimates are difficult because usual formulas rely on assumptions that do not apply to this setting.The passage identifies this issue specifically for continuous data.

A.1. Calculation of standard errors.

Standard regression-error formulas are invalid for log-transformed power-law histograms and CDFs because their noise assumptions fail. Although CDF fits empirically estimate α more accurately, adjacent CDF values are correlated and logarithmic noise is non-Gaussian.

A.1. Calculation of standard errors.: Ordinary slope standard errors require independent, Gaussian dependent-variable noise, assumptions violated when fitting logarithms of power-law histograms.Histogram frequencies p(x) have independent Gaussian, actually Poisson, noise, but their logarithms do not.
A.1. Calculation of standard errors.: CDF fits also violate standard regression assumptions because logarithmic noise is non-Gaussian and adjacent values are strongly correlated.P(x) = P(x+1)+p(x), so the CDF values are not independent.
A.1. Calculation of standard errors.: CDF fits empirically determine the scaling parameter α more accurately, but not because their regression assumptions hold.The individual CDF values P(x) have Gaussian noise before logarithmic transformation, yet dependence remains.

A.2. Validation. · A.3. Regression lines are not valid distributions. · Appendix B. Maximum likelihood estimators for the power law.

The validation discussion shows that straight-line regression can mislead power-law assessment and fail to produce properly normalized distributions. Appendix B derives maximum-likelihood estimators for the power-law scaling parameter.

A.2. Validation.: For large n, a low r2 from a straight-line fit can reject a true power-law hypothesis because such outcomes are unlikely.The passage limits this use of r2 to data truly drawn from a power-law distribution and large samples.
A.2. Validation.: Small samples can make distributions unlike power laws appear power-law-like in straight-line fits.The passage identifies this as a limitation of using regression-based appearance to assess power-law behavior.
A.2. Validation.: Log-normal distributions can approximate power laws over many orders of magnitude and produce high r2 values.Thus, a high r2 does not by itself establish power-law behavior.
A.3. Regression lines are not valid distributions.: The CDF must equal 1 at xmin when the probability distribution above xmin is properly normalized.This normalization condition is required at the lower cutoff of the modeled range.
A.3. Regression lines are not valid distributions.: Ordinary linear regression generally fails to enforce the CDF normalization constraint at xmin.Regression lines therefore need not satisfy the defining constraints of a valid distribution.
A.3. Regression lines are not valid distributions.: The PDF must integrate to 1 from xmin to ∞, but standard regression methods generally do not impose this constraint.The passage notes that constrained regression methods exist but are not used to any significant extent in the literature discussed.
Appendix B. Maximum likelihood estimators for the power law.: Appendix B derives maximum-likelihood estimators for the scaling parameter of a power law.The appendix is devoted to derivations of these estimators.

B.1. Continuous data.

For continuous power-law data, the scaling parameter α is estimated by maximizing the likelihood of observations above xmin. This maximum-likelihood estimator is equivalent to the Hill estimator.

Continuous data: The continuous-data maximum-likelihood estimator for α is equivalent to the well-known Hill estimator.The estimator was first derived, to the authors’ knowledge, by Muniruzzaman in 1957.
Continuous data: xmin is the minimum value at which power-law behavior holds, and the model considers observations xi ≥ xmin.The scaling parameter α is estimated for data containing n observations above this threshold.
Continuous data: The preferred α is the value that maximizes the likelihood of the observed data under the power-law model.The likelihood is proportional to the probability that the data were drawn from the model.
Continuous data: Maximizing the logarithm L of the likelihood yields the same α as maximizing the likelihood itself.The MLE is obtained by setting ∂L/∂α = 0 and solving for α.

B.2. Formal results.

The formal results establish consistency and asymptotic normality of the maximum-likelihood estimator for power-law parameters. They also quantify approximation error for discrete data and finite-sample deviations from large-sample behavior.

Consistency: The MLE converges almost surely to the true parameter under mild regularity conditions, including for the continuous power law.The general result assumes independent, identically distributed data; Proposition B.2 specializes it to the continuous power law.
Asymptotic distribution: The continuous-power-law MLE is asymptotically Gaussian with variance (α −1)2/n.This follows from the general asymptotic-normality theorem and the Fisher-information formulation.
Approximation error: The discrete-data approximate MLE has average error decaying as O(x_min^-2) and below 1% of α when x_min ≳6.The figure reports results for α = 2, 2.5, and 3 over 1000 repetitions.
Finite-sample corrections: Finite-sample corrections are O(1/n), smaller than the leading O(1/√n) terms, when estimating x_min introduces coupling with the MLE.These corrections are neglected in the main text and can generally be obtained by bootstrapping.
Finite-sample distribution: With x_min known or fixed, the estimator has mean (nα−1)/(n−1) and standard deviation n(α−1)/(n−1)√(n −2), differing from large-n values by O(1/n).This provides an explicit sampling distribution in the special case where x_min is known a priori or fixed by fiat.

B.3. Discrete data. · B.4. Approximate estimator for the scaling parameter of the discrete power law.

The paper formulates the discrete power law with the generalized zeta function and derives its maximum-likelihood estimator. For moderately large xmin, it provides a convenient approximation that agrees well with the exact estimator when xmin ≳6.

B.3. Discrete data.: The discrete power-law distribution is defined over an integer variable using the generalized, or Hurwitz, zeta function.
B.3. Discrete data.: The scaling-parameter MLE is obtained from the discrete log-likelihood equation and can be solved numerically or by directly maximizing the log-likelihood.
B.3. Discrete data.: The discrete-power-law MLE is consistent and asymptotically efficient, although the supporting calculations are omitted.
B.3. Discrete data.: For moderately large xmin, the exact discrete MLE can be replaced by a more convenient approximate formula for α.
B.4. Approximate estimator for the scaling parameter of the discrete power law.: The approximation is derived by expanding sums over integer x and approximating the zeta-function ratio for large xmin.
B.4. Approximate estimator for the scaling parameter of the discrete power law.: The resulting estimator matches the continuous-case MLE except for the −1/2 in the denominator.
B.4. Approximate estimator for the scaling parameter of the discrete power law.: xmin ≳6: numerical comparisons show that the approximate estimator is a good approximation to the exact discrete MLE.

Appendix C. Likelihood ratio tests. · C.1. Nested hypotheses.

The appendix defines likelihood-ratio tests by comparing candidate distributions through likelihoods and their log ratios. For independent data, the log-likelihood ratio is approximately normal for non-nested hypotheses, while nested hypotheses require a chi-squared treatment; p-values assess whether model preference is distinguishable from chance, not absolute fit.

Appendix C. Likelihood ratio tests.: Likelihood-ratio tests compare two candidate distributions through their data likelihoods and the ratio of those likelihoods.The candidates have probability density functions p1(x) and p2(x).
Appendix C. Likelihood ratio tests.: The log likelihood ratio is formed by summing per-measurement log-likelihood differences across the data.For measurement xi, i = ln pj(xi) represents its log-likelihood under distribution j.
Appendix C. Likelihood ratio tests.: Under independent measurements, the summed log likelihood ratio becomes normally distributed as n grows, with expected variance nσ2.The unknown single-term variance σ2 is approximated using the variance of the data.
Appendix C. Likelihood ratio tests.: If the true expected log likelihood ratio is zero, a p-value estimates how likely the observed magnitude of R is under chance fluctuations.The probability is based on the complementary Gaussian error function.
Appendix C. Likelihood ratio tests.: When p < 0.1, the sign of R can probably indicate which model fits better, but this does not establish that either model fits the data well.The test distinguishes relative preference from absolute goodness of fit.
Appendix C. Likelihood ratio tests.: Vuong’s results justify the likelihood-ratio framework for fitted distributions in the distinct, non-nested case, despite correlations introduced by fitting and testing on the same data.The appendix notes that the rigorous proof contains subtleties requiring careful treatment.
C.1. Nested hypotheses.: For nested hypotheses, when the true distribution lies in the smaller family, R follows a chi-squared distribution asymptotically rather than the simple central-limit form.The usual ratio |R|/σ tends to 0/0, so a refined analysis is needed to calculate the correct p-value.
C.1. Nested hypotheses.: The appendix also introduces the transformation method as a simple approach for generating random numbers from specified distributions.It motivates this method with simulations using independent power-law random numbers to test estimation of α and xmin.

Appendix D. Generating power-law distributed random numbers.

The appendix describes transformation-based generation of continuous power-law random numbers and numerical methods for the discrete case. It also quantifies when a continuous approximation is sufficiently accurate for generating discrete power-law integers.

Continuous power laws: Uniform random numbers are transformed through the inverse cumulative distribution function to generate continuous power-law variates, yielding a straightforward implementation.The method relates the target density to a uniform source and applies the inverse CDF; for power laws, the resulting expression follows from Eq. (2.6).
Discrete power laws: Discrete power-law variates require numerical inversion because the discrete CDF has no closed-form inverse.The procedure brackets a solution by repeatedly doubling from xmin, then uses binary search until k ≤ x < k + 1 and discards the noninteger part.
Continuous approximation: For α = 2.5, the continuous approximation causes more than 8% error at xmin = 1, less than 1% at xmin = 5, and less than 0.2% at xmin = 10.The approximation error is largest at xmin and decreases rapidly as xmin increases; the true discrete generator is recommended for very small xmin when large errors are unacceptable.
Validation: For α = 2.5 and xmin = 5, CDFs from 100 000 generated values agree well with the theoretical continuous and discrete power-law CDFs.The reported differences between exact and generated CDFs are small for both transformation-based generators and the continuous approximation.