PaperlayerView exact revision on arXiv

Source-linked AI summary

True scale-free networks hidden by finite size effects

Matteo Serafino, Giulio Cimini, Amos Maritan, Andrea Rinaldo, Samir Suweis, Jayanth R. Banavar, Guido Caldarelli

arXiv:1905.09512v2physics.soc-phcond-mat.stat-mechcs.SI

TL;DR

The paper asks whether apparent departures from power-law degree distributions reflect genuine non-scale-free structure or finite-size effects. It applies finite-size scaling and related tests to model and empirical networks, finding that many satisfy the scaling hypothesis without fine-tuning. The authors conclude that scale invariance is common in naturally occurring networks, although important deviations remain and the rescaling procedure has intrinsic limitations.

  • Problem

    The study addresses whether scale-free structure is generally viable in real networks despite statistical claims that such networks are rare.

  • Method

    The authors analyze model and empirical networks with finite-size scaling, collapse plots, moment tests, and randomly sampled subnetworks.

  • Results

    Many networks satisfy the finite-size scaling hypothesis without fine-tuning, while log-normal and Weibull realizations show poor collapse and are classified as non-scale-free.

  • Takeaways & Limitations

    Scale invariance appears to be an extant feature of many naturally occurring networks, often obscured by finite-size effects.

  • Takeaways & Limitations

    The rescaling method cannot span network sizes across orders of magnitude, and general network coarse-graining remains an open problem.

Abstract

from arXiv · show

We analyze about two hundred naturally occurring networks with distinct dynamical origins to formally test whether the commonly assumed hypothesis of an underlying scale-free structure is generally viable. This has recently been questioned on the basis of statistical testing of the validity of power law distributions of network degrees by contrasting real data. Specifically, we analyze by finite-size scaling analysis the datasets of real networks to check whether purported departures from the power law behavior are due to the finiteness of the sample size. In this case, power laws would be recovered in the case of progressively larger cutoffs induced by the size of the sample. We find that a large number of the networks studied follow a finite size scaling hypothesis without any self-tuning. This is the case of biological protein interaction networks, technological computer and hyperlink networks, and informational networks in general. Marked deviations appear in other cases, especially infrastructure and transportation but also social networks. We conclude that underlying scale invariance properties of many naturally occurring networks are extant features often clouded by finite-size effects due to the nature of the sample data.

A. Finite Size Scaling of networks

Finite-size scaling models how a network’s cumulative degree distribution crosses over from power-law behavior to a size-dependent cutoff. Collapse plots across randomly generated subnetworks test whether this scaling form and its exponents are consistent with scale invariance.

  • A. Finite Size Scaling of networks: Scale-free networks are expected to follow a power law below a size-dependent crossover degree and decay more rapidly beyond it.The cumulative distribution uses exponent γ, while the finite-size exponent d is negative so the infinite-size limit recovers a pure power law.
  • A. Finite Size Scaling of networks: Small subnetworks should preserve the degree distribution of a scale-free network apart from low-degree deviations.This illustrates scale invariance: changing the sample size alters the cutoff rather than the underlying degree structure.
  • A. Finite Size Scaling of networks: Collapse plots estimate γ and d by aligning P(k,N)k^γ against kN^d across network sizes, with collapse quality measuring self-similarity.The collapsed curve represents the scaling function f, and the fitting parameters are selected to make curves from different N overlap.
  • A. Finite Size Scaling of networks: Network size can be measured by nodes N or links E, and scale-free networks require the corresponding finite-size exponents d and d_E to agree.The supplied formulation states that d_E < 0 and that d_E should equal d for networks satisfying finite-size scaling.

B. Ratio of moments test

The ratio-of-moments test provides an independent check of scale-free behavior by examining how consecutive moment ratios vary with network size. For scale-free networks, these ratios follow a common power-law dependence whose slope identifies the finite-size exponent.

  • B. Ratio of moments test: For scale-free networks, log-log plots of consecutive moment ratios versus N are straight lines with slope −d.When i − 1 > γ, the size dependence becomes independent of i.
  • B. Ratio of moments test: The analogous moment-ratio relation using links E has the same asymptotic structure and supports an independent size-based test.The ratio approaches a constant as E grows, under the stated condition i − 1 > γ.
  • B. Ratio of moments test: Agreement between d and d_E is expected because constant mean degree implies d = d_E for scale-free networks with γ > 1.Their difference, assessed through a Z-score, supplies an independent quality measure of scale-free attributes.

C. Sub-sampling and scaling region

The analysis generates subnetworks by randomly selecting nodes and adjusts the lower scaling bound to reduce subsampling distortions. It excludes cases where too few nodes remain in the scaling region for a stable collapse.

  • C. Sub-sampling and scaling region: Randomly selecting n < N nodes and removing the rest creates subnetworks while altering the observed degree-distribution shape.The lower bound k_min is chosen by matching the original empirical distribution to its maximum-likelihood power-law fit above that threshold.
  • C. Sub-sampling and scaling region: The scaling analysis becomes unstable when deviations from a power law push k_min high and leave too few nodes with k ≥ k_min.Feasibility requires n* ≥ ln N for every network and subnetwork.

RESULTS

The study classifies empirical networks using two independent tests: collapse quality and compatibility between node- and link-based finite-size exponents. The resulting nested categories distinguish strong, weak, and non-scale-free degree distributions.

  • RESULTS: Scale-free classification combines collapse quality S with the Z-score measuring compatibility between d and d_E.These tests jointly assess whether the degree distribution follows the finite-size scaling hypothesis.
  • RESULTS: A network is classified as non-scale-free when it fails the scale-free criteria or when n* < ln N for the original network or any subnetwork.The feasibility condition makes insufficient scaling-region data an explicit basis for NSF classification.
  • RESULTS: The classification is nested: every strong scale-free network is also classified as weak scale-free.

Power law and Poisson distribution

Finite-size scaling recovers the expected scale-free behavior of the Barabási-Albert model, while the Erdős-Rényi model is classified as non-scale-free because its estimated cutoff prevents sufficiently large subnetworks.

  • Barabási-Albert model: The Barabási-Albert degree distributions collapse with high quality, and the finite-size-scaling exponent γ agrees with the maximum-likelihood exponent Γ.For the shown realization, γ = 1.89 ± 0.06 and Γ = 1.89 ± 0.02.
  • Barabási-Albert model: The moment-ratio tests produce parallel scaling behavior for the Barabási-Albert realization, supporting the finite-size-scaling hypothesis.Using nodes gives d = −0.358 ± 0.035; using links gives dE = −0.351 ± 0.031.
  • Barabási-Albert model: The collapse quality S is consistently high across node- and link-based analyses, with S = 0.67 and S = 0.66, respectively.The corresponding best-collapse exponents are γ = 1.89 ± 0.06 and γ = 1.89 ± 0.05.
  • Barabási-Albert model: Across 1000 Barabási-Albert realizations, the collapse-quality distribution S is well fitted by a log-normal distribution.The fit parameters are µ = −0.70 ± 0.1 and σ = 0.414 ± 0.009.
  • Erdős-Rényi model: The Erdős-Rényi model is classified as NSF because its estimated kmin is too large to permit subnetworks with n* ≥ ln N.The same outcome was obtained across an ensemble of 1000 realizations.

Alternative fat tail distributions

Finite-size scaling distinguishes some fat-tailed alternatives from power laws, but sufficiently broad log-normal or Weibull tails can become difficult to distinguish from power laws at finite network size.

  • Empirical discrimination: Log-normal and Weibull networks show poor collapse and nonparallel moment ratios, so both are classified as NSF in the tested realizations.Their finite-size-scaling exponent γ is substantially different from the maximum-likelihood power-law exponent Γ.
  • Empirical discrimination: The quality measure S lacks a minimum near Γ for the tested log-normal and Weibull networks, indicating inconsistency between scaling and power-law fits.A minimum exists elsewhere in the γ range.
  • Parameter dependence: The NSF fraction decreases as σ increases for log-normal distributions and as h decreases for Weibull distributions.The decrease continues until the distributions become sufficiently broad that finite-size scaling can hardly distinguish them from power laws.
  • Parameter dependence: For sufficiently broad alternatives, the minimizing γ becomes compatible with Γ, showing that finite network size limits discrimination from power laws.This occurs when the variance is so large that the scaling analysis can hardly distinguish the distributions from power laws at finite N.

Real world networks

Across 185 empirical networks, finite-size scaling finds scale-free behavior in many biological, technological, and informational networks, while infrastructure and transportation networks are rarely scale-free. The analysis also finds consistent exponent relationships and controls for artificial clustering from overrepresented similar networks.

  • Scaling consistency: The moment-ratio exponents d and dE are compatible in most networks, supporting consistency between the two moment-ratio tests.Figure 7(a) compares the two exponents against the identity relation.
  • Scaling consistency: The finite-size scaling exponent γ often agrees with Γ from maximum-likelihood power-law fits of degree distributions.This agreement is summarized across the empirical datasets in Figure 7(b).
  • Scaling consistency: The exponents satisfy d ≃ −(γ + 1)−1, linking the scaling function to the degree cross-over and implying kc ∼ N^(1/(γ+1)).The same scaling is reported for the network maximum degree, while differing from the hand-waving prediction kc ∼ N^(1/γ).
  • Dataset scope: The dataset excludes very similar networks and repeated instances because they artificially cluster categories and would bias conclusions about scale-free structure.Protein-interaction networks from different species are cited as an example of this clustering effect.
  • Overall classification: 27% of the 185 networks are strong scale-free, 23% weak scale-free, and 50% non-scale-free, with substantial variation across categories.Biological, computer, hyperlink, citation, and text networks are often at least weakly scale-free, whereas infrastructure networks are rarely scale-free.

DISCUSSION

The paper revisits claims that scale-free networks are rare by applying finite-size scaling to model and empirical networks. Many networks satisfy the hypothesis without fine-tuning, but direct comparison with approaches based on different underlying hypotheses is not meaningful, and the analysis is limited by network rescaling constraints.

  • DISCUSSION: The study addresses prior claims that scale-free networks are rare and notes that correlations can cause standard maximum-likelihood methods to falsely reject statistical laws.Broido and Clauset’s claim is contrasted with replies emphasizing deviations from pure power laws and correlations in empirical observations.
  • DISCUSSION: Many analyzed networks spontaneously satisfy the finite-size scaling hypothesis without fine-tuning, supporting the claim that complex networks are inherently scale-free.The method is presented as extending statistical arguments with tools from critical-phenomena research.
  • DISCUSSION: Direct comparison with previously discussed results is considered meaningless when competing models rely on different underlying hypotheses.The authors emphasize that different hypotheses can lead to different results.
  • DISCUSSION: The methodology is offered as one tool among others for assessing whether a network is scale-free, rather than as a replacement for all existing approaches.Its hypothesis derives from statistical mechanics and critical phenomena and does not require a critical point.
  • DISCUSSION: Random-node rescaling cannot span network sizes across orders of magnitude, and general network coarse-graining remains unresolved because networks lack a Euclidean embedding.The analysis preserves the degree distribution through averaging, but the authors restrict their claims to degree-distribution self-similarity rather than overall network self-similarity.

MATERIALS AND METHODS

The procedure tests finite-size scaling and the moment-ratio relation using network sizes and edge counts, replacing the node-size exponent with an edge-size exponent when required.

  • MATERIALS AND METHODS: The edge-based tests use the number of edges E or e for each network size N or n and replace d with dE.This applies when testing the scaling relations associated with edge counts.

Finite Size Scaling analysis

The finite-size scaling analysis constructs and evaluates degree distributions across randomly sampled subnetworks of several sizes. It estimates scaling exponents after filtering low-degree regions and uses a moment-ratio test alongside collapse optimization.

  • Finite Size Scaling analysis: The workflow begins by estimating power-law parameters Γ + 1 and kmin from the original degree distribution using the Clauset–Shalizi–Newman method.These estimates define the low-degree cutoff used in subsequent filtering and renormalization.
  • Finite Size Scaling analysis: Networks with too few nodes satisfying k ≥ kmin are classified as non-scale-free before further scaling analysis.The threshold requires the average count n* of nodes with k ≥ kmin to exceed ln N.
  • Finite Size Scaling analysis: The moment-ratio test estimates d by fitting log moment ratios against log network size and averaging slopes across multiple moment choices.It uses 20 equally spaced sizes between N/4 and N with ensembles of 100 subnetworks per size.
  • Finite Size Scaling analysis: The analysis computes degree distributions for the original network and randomly sampled subnetworks, then evaluates scaling across sizes N/4, N/2, 3N/4, and N.Each smaller size is represented by an ensemble of 100 subnetworks formed by randomly selecting nodes and deleting the remaining nodes and incident links.
  • Finite Size Scaling analysis: The collapse analysis jointly estimates γ and d by selecting the exponent pair that maximizes the quality of the rescaled-distribution collapse.The resulting d is compatible with the moment-ratio estimate, so γ can in principle be varied while d is held fixed.

Quality of collapse

The collapse quality is measured by comparing rescaled subnetworks with a fitted master curve. The score is normalized so that values near one indicate a good single-curve collapse, while larger values indicate poorer agreement.

  • Quality of collapse: The master curve is fitted from rescaled cumulative degree-distribution points, with each point assigned an uncertainty from the distribution-count error.The rescaling produces xnj and ynj coordinates for each subnetwork size.
  • Quality of collapse: A collapse is considered good when all rescaled distributions overlap the master curve, with S expected to be around one after normalization.Much larger S values indicate that the data do not collapse to a single curve.
  • Quality of collapse: At each comparison location, the master-curve value and uncertainty are estimated by a linear fit through neighboring points from the other subnetwork-size datasets.Locations lacking two bracketing points in every other dataset do not contribute to S.
  • Quality of collapse: The quality score S measures the mean-square distance of rescaled datasets from the master curve in standard-error units.The score is analogous to a χ2 test and is computed from points where the curves overlap.
  • Quality of collapse: The exponents γ and d are optimized within bounded intervals around their initial estimates, and uncertainty is defined by the change producing S + 1.The reported parameter errors are therefore tied directly to the collapse-quality surface.

DATASET

The study assembles large empirical networks from ICON and KONECT, applying explicit size, representation, and completeness criteria while reducing overrepresented network instances.

  • DATASET: Networks were collected from ICON and KONECT, with duplicates removed before analysis.The full network list and finite-size scaling results are reported in a supplementary dataset table.
  • DATASET: The dataset requires N > 1000 and E > 1000, excludes networks with more than 50 million links, and omits database entries marked incomplete.Undirected, binary, and converted network representations were also included under the stated preprocessing rules.
  • DATASET: The analysis includes undirected versions of directed and bipartite networks, plus binarized versions of weighted and multi-edge networks.
  • DATASET: KONECT was restricted to English-language Wikipedia-related networks, while ICON filtering removed several heavily replicated or overrepresented network families.Excluded ICON groups included repeated interactomes, fungal growth networks, Norwegian boards, CAIDA snapshots, and selected software and circuit networks.
  • DATASET: Using the same broad data source as Broido and Clauset while avoiding overrepresented instances reduces clustering of similar networks and yields less biased category-level conclusions.
Loading 1905.09512v2…