PaperlayerView exact revision on arXiv

Source-linked AI summary

Extended Scale-Free Networks

Arthur Charpentier, Emmanuel Flachaire

arXiv:1905.10267v2cs.SIphysics.soc-phstat.ME

TL;DR

Strict scale-free networks are rare in observed networks, and sub-networks of scale-free networks need not remain strictly scale-free. The paper introduces an extended scale-free property based on second-order Pareto behavior and relates it to network structure and real-network examples.

  • Problem

    Strict scale-free behavior may be rare in real networks, while sub-networks of scale-free networks are not necessarily strictly scale-free.

  • Method

    The paper extends scale-free modeling with an extended Pareto formulation that captures second-order deviations from a power law.

  • Results

    Extended Pareto fits yield τ = −1 for Twitter and Google+, consistent with the result reported by Stumpf, Wiuf & May (2005).

  • Takeaways & Limitations

    Sub-networks can be asymptotically scale-free while exhibiting extended scale-free deviations rather than strict scale-free behavior.

  • Takeaways & Limitations

    Continuous extreme-value approximations may not be valid for discrete supports without additional long-tailed and rounding conditions.

Abstract

from arXiv · show

Recently, Broido & Clauset (2019) mentioned that (strict) Scale-Free networks were rare, in real life. This might be related to the statement of Stumpf, Wiuf & May (2005), that sub-networks of scale-free networks are not scale-free. In the later, those sub-networks are asymptotically scale-free, but one should not forget about second-order deviation (possibly also third order actually). In this article, we introduce a concept of extended scale-free network, inspired by the extended Pareto distribution, that actually is maybe more realistic to describe real network than the strict scale free property. This property is consistent with Stumpf, Wiuf & May (2005): sub-network of scale-free larger networks are not strictly scale-free, but extended scale-free.

1 From Strict Scale-Free to Scale-Free Types

The paper distinguishes strict scale-free networks, defined by power-law degree distributions, from broader Pareto-type behavior and proposes an extended scale-free perspective that incorporates second-order deviations. It connects this perspective to discrete extreme-value models, regular variation, and the behavior of network subgraphs.

  • 1.1 Strict Scale-Free: Strict scale-free networks require a power-law degree distribution above a cutoff, with a linear log-log representation whose slope gives the scaling exponent.
  • 1 From Strict Scale-Free to Scale-Free Types: The paper motivates extended scale-free behavior because strict Pareto behavior often appears only above high thresholds, while real distributions can exhibit second-order deviations.The proposed extension is inspired by the extended Pareto distribution and is related to sub-networks of larger scale-free networks.
  • 1.2 Discrete PD with Cumulative Probabilities: Complementary cumulative probabilities preserve power-law form, but their exponent is α −1 rather than the probability distribution's exponent α.
  • 1.3 Discrete GPD and Second Law of Extremes: Discrete generalized Pareto modeling requires care because continuous extreme-value approximations may fail for discrete supports unless additional long-tailed and rounding conditions hold.The paper states that a discrete variable belongs to the relevant max-domain of attraction if its tail is long-tailed and it is the ceiling of a suitable continuous variable.
  • 1.4 Regular Variation and Power-Law Type: The paper uses probability-generating functions as an alternative representation, especially when analyzing network sub-networks.The representation includes the polylogarithm for power-law or scale-free distributions.

2 Extended Scale-Free

The paper extends Pareto and scale-free models by incorporating second-order tail behavior rather than assuming a strict power law. The resulting extended Pareto formulation motivates extended scale-free networks and distinguishes them from strict scale-free behavior in finite or shifted distributions.

  • 2 Extended Scale-Free: The Extended Pareto Distribution incorporates a second-order approximation whose leading and correction terms are both power-law-like, with a smaller tail index.This formulation was introduced by Beirlant, Joossens & Segers (2009).
  • 2 Extended Scale-Free: A Pareto-type tail can be represented as a power law multiplied by a second-order correction, and in one formulation this correction corresponds to a mixture of two strict Pareto distributions.
  • 2 Extended Scale-Free: Figures 2 and 3 compare strict, mixed-Pareto, and extended-Pareto degree distributions on log-log scales, while Figure 4 contrasts Hill plots for strict and extended scale-free distributions.
  • 2 Extended Scale-Free: The extended Pareto model is parameterized by τ ≤0 and δ > max(−1,1/τ).
  • 2 Extended Scale-Free: For discrete degrees, shifted Pareto distributions apply when D−u has a Pareto distribution, while strict Pareto complementary cumulative probabilities form a log-log straight line with slope −1/ξ.

3 Inference & Estimation of α or ξ

The section describes estimators for the power exponent or tail index using continuous Pareto samples and degree-frequency fitting. It notes that Hill estimation is consistent under additional assumptions but performs badly when the sample is not strictly Pareto distributed.

  • 3 Inference & Estimation of α or ξ: The Hill estimator can be applied to the k largest observations rather than the full sorted sample.
  • 3 Inference & Estimation of α or ξ: Hill estimation is almost surely consistent for ξ under further assumptions, providing an estimator for the Pareto tail index.
  • 3 Inference & Estimation of α or ξ: Hill estimation performs badly when the sample is not strictly Pareto distributed, whereas maximum-likelihood techniques are suggested for the Extended Pareto Distribution.
  • 3 Inference & Estimation of α or ξ: The degree-distribution analysis uses chi-square statistics or maximum likelihood, regrouping sparse degree counts into classes with at least 10 nodes for robustness.

4 Strict and Extended Scale-Free Networks

The paper simulates extended scale-free networks and shows that stronger second-order effects lengthen average shortest paths. It also derives an extended-Pareto form for randomly sampled sub-networks of scale-free networks.

  • 4.2 Network Structures: The simulations average shortest paths over 1,000 networks with n = 1,000 nodes across varying τ values.Figure 5 varies −τ from 0, corresponding to a strict Pareto case, to 5 and reports a 90% confidence band from 500 simulated networks for each τ.
  • 4.2 Network Structures: Stronger second-order effects, represented by larger |τ|, produce longer average shortest-path distances in simulated extended scale-free networks.The averages use networks with n = 1,000 nodes and the largest connected subgraph.
  • 4.2 Network Structures: With a strict power law, large hubs connect subgraphs and support a small-world structure; stronger second-order effects reduce very large hubs and increase smaller ones.The resulting distances to other nodes therefore tend to be longer on average.
  • 4.3 Sub-network of Scale-Free Networks: For randomly sampled sub-networks, the authors construct an induced subgraph through the sampled nodes and its sub-adjacency matrix, while excluding orphaned nodes.The degree distribution is then characterized through its probability generating function and rescaled after removing zero-degree nodes.
  • 4.3 Sub-network of Scale-Free Networks: The sub-network calculation recovers an extended Pareto distribution with index τ = −1 from a simple scale-free network.This provides the paper’s analytic link between scale-free parent networks and extended scale-free sub-networks.

5 Real Internet Networks

The paper evaluates Facebook, Twitter, and Google+ network data using extended scale-free distributions. Facebook is not captured by the extended model, whereas Twitter and Google+ are fitted with τ = −1.

  • 5 Real Internet Networks: The analyzed SNAP datasets contain 4,039 Facebook nodes and 88,234 edges, 81,306 Twitter nodes and 1,768,149 edges, and 107,614 Google+ nodes and 13,673,453 edges.
  • 5 Real Internet Networks: The SNAP-Facebook sub-networks are not captured by an extended distribution because their degree distribution has strong concavity.The dataset contains 10 sub-networks.
  • 5 Real Internet Networks: Twitter and Google+ are both fitted by extended Pareto distributions with τ = −1, consistent with the sub-network result of Stumpf, Wiuf & May (2005).The fitted distributions are shown for Twitter and Google+ in Figure 8.
  • 5 Real Internet Networks: For Twitter, the extended-Pareto fit gives bξ = 0.757, corresponding to 1 + bξ^-1 = 2.32 and aligning with previously reported tail-index values.The earlier outgoing and incoming degree estimates were bλ = 2.1715 and bλ = 1.8778, respectively.

6 Appendix

The appendix describes estimation of discrete power-law, generalized Pareto, and extended Pareto models using likelihood and chi-square procedures. It compares these estimators on simulated samples from strict Pareto, generalized Pareto, and extended Pareto distributions.

  • 6.2 Fitting Discrete Distributions: The appendix introduces continuous power-law likelihood calculations before adapting the fitting procedure to discrete degree distributions.The likelihood is written logarithmically and maximized to obtain parameter estimates.
  • 6.2 Fitting Discrete Distributions: The appendix estimates unknown discrete EPD parameters by minimizing chi-square distance or maximizing the log-likelihood through numerical optimization.The robust chi-square version groups consecutive degree values so each group contains at least 10 observations.
  • 6.2 Fitting Discrete Distributions: The discrete EPD chi-square calculation compares empirical and model probabilities across degree groups using Q = sum((PEMP−PEPD)^2/PEPD).The implementation constructs the empirical table, computes model probabilities, and then optimizes the parameter vector.
  • 6.2 Fitting Discrete Distributions: The estimator comparison uses 1,000 simulated samples and evaluates strict Pareto, generalized Pareto, and extended Pareto data with both chi-square and maximum-likelihood techniques.Figure 9 summarizes the resulting estimates with boxplots of the six estimators of α.
Loading 1905.10267v2…