Shortest-path percolation on scale-free networks

Technical Summary: Shortest-Path Percolation on Scale-Free Networks

Problem Statement
Percolation theory traditionally investigates the relationship between a network's microscopic structure and its macroscopic connectivity, often revealing distinct behaviors between Erdős-Rényi networks (ERNs) and scale-free networks (SFNs). In SFNs, characterized by power-law degree distributions $P(k) \sim k^{-\lambda}$, ordinary percolation exhibits anomalous behaviors, such as vanishing critical thresholds for $\lambda < 3$ and critical exponents that depend on $\lambda$.

The Shortest-Path Percolation (SPP) model was previously introduced to describe the consumption and exhaustion of network resources. In this model, agents sequentially request paths between random origin-destination pairs. If the geodesic distance is within a tunable budget $C$, all edges along the shortest path are removed. Previous studies on ERNs established that for finite $C$, the SPP transition belongs to the ordinary percolation universality class, whereas for unbounded $C$, the transition becomes more abrupt with distinct critical exponents. However, the behavior of SPP on SFNs remained unexplored, specifically whether the inherent heterogeneity of SFNs preserves its anomalous percolation properties under the SPP process.

Methodology
The authors employed large-scale Monte Carlo simulations and finite-size scaling (FSS) analysis to study the SPP transition on uncorrelated scale-free networks generated via the Configuration Model (UCM).

• Network Generation: SFNs were generated with degree exponents $\lambda \in \{2.1, 2.7, 3.5, 4.5\}$ and a minimum degree $k_{min}=4$ to ensure a single connected component. Structural cutoffs were applied to minimize degree-degree correlations.
• SPP Process: The process iteratively removes edges along shortest paths connecting random node pairs, provided the path length $Q_t \leq C$. The study examined finite budgets ($C=1, 2, 3$) and an unbounded budget ($C \geq N-1$, denoted as $C=N$). Note that $C=1$ corresponds to ordinary bond percolation.
• Observables and Analysis: The fraction of removed edges $r$ served as the control parameter. Key observables included the percolation strength $P$ (order parameter) and the average cluster size $S$ (response function).
• Scaling Approach: The study utilized the "event-based ensemble," sampling observables at the single-instance pseudocritical point $r^*_c(N)$ (defined by the largest drop in $P$) rather than a fixed $r$. This method accounts for non-self-averaging effects. The authors analyzed the scaling of $P_c(N)$ and $S_c(N)$ to estimate critical exponent ratios ($\beta/\bar{\nu}$, $\gamma/\bar{\nu}$) and the convergence exponents ($1/\bar{\nu}_1$, $1/\bar{\nu}_2$) governing the pseudocritical point's behavior.

Key Contributions and Results

1. Universality Class Independence from $\lambda$:
   Contrary to ordinary percolation on SFNs, where critical exponents depend on $\lambda$ (for $\lambda < 4$), the SPP transition on SFNs with $C > 1$ exhibits critical exponents identical to those on ERNs, regardless of the degree exponent $\lambda$.

   • Finite Budget ($C > 1$): The ratio $\beta/\bar{\nu} \approx 1/3$ and $\gamma/\bar{\nu} \approx 1/3$, matching the mean-field exponents of ordinary percolation on ERNs.
   • Infinite Budget ($C \to \infty$): The exponents shift to $\beta/\bar{\nu} \approx 0.22$ and $\gamma/\bar{\nu} \approx 0.55$, consistent with previous findings on ERNs for unbounded budgets.
   • Ordinary Percolation ($C=1$): The results recover known SFN anomalies, with $\beta/\bar{\nu}$ varying with $\lambda$ (e.g., $\approx 0.54$ for $\lambda=2.1$).

2. Homogenization Mechanism:
   The authors propose and validate that the SPP process with $C > 1$ drastically homogenizes the heterogeneous structure of SFNs before the percolation transition occurs.

   • Evidence: The study analyzed the scaling of the maximum degree $k_{max}$. In ordinary percolation, the ratio of the maximum degree at a pre-critical point to the initial maximum degree remains non-zero asymptotically. However, for $C > 1$, this ratio decays to zero as $N \to \infty$.
   • Interpretation: Since SPP preferentially removes edges belonging to shortest paths (which heavily involve high-degree hubs), the process effectively dismantles the hub structure, rendering the network topologically similar to a homogeneous ERN prior to the critical point.

3. Complex Finite-Size Scaling Behavior:
   While the structural exponents ($\beta, \gamma$) align with ERN universality classes, the exponents governing the convergence and fluctuation of the pseudocritical point ($1/\bar{\nu}_1$ and $1/\bar{\nu}_2$) display rich, parameter-dependent behavior:

   • For $\lambda = 2.7$ and finite $C$, $1/\bar{\nu}_1 \approx 1/\bar{\nu}_2$, typical of ordinary percolation.
   • For $\lambda > 3$ and finite $C$, $1/\bar{\nu}_1 > 1/\bar{\nu}_2$, a behavior previously associated with explosive percolation.
   • For $\lambda = 2.1$, $1/\bar{\nu}_1 < 1/\bar{\nu}_2$, a scenario observed in bond percolation on high-dimensional lattices with free boundary conditions.
   • Data collapse plots confirmed these scaling relations, though the quality of collapse varied depending on the specific $\lambda$ and $C$ values.

Significance and Claims
The paper claims that the SPP model acts as a mechanism that "washes out" the anomalous, network-dependent properties of scale-free networks. The primary significance lies in the finding that the SPP transition on SFNs is identical to that on ERNs for $C > 1$, denoting a fundamental independence from the degree exponent $\lambda$. This challenges the assumption that network heterogeneity always dictates percolation universality classes.

The authors attribute this phenomenon to the topological correlation introduced by the SPP rule: by targeting shortest paths, the process systematically removes the edges connecting hubs, thereby homogenizing the network structure before the macroscopic disintegration occurs.

The authors remain modest regarding analytical explanations, noting that current frameworks (e.g., generating functions, message passing) assume edge independence and thus fail to capture the topological correlations inherent in SPP. They identify the development of an analytical framework for "path-based" and "long-range" connectivity as a necessary future direction. The work suggests that these findings are applicable to real-world supply-and-demand networks (e.g., transportation, communication, supply chains) where resources are consumed along optimal paths, potentially exhibiting similar homogenization and transition behaviors.