PaperlayerView exact revision on arXiv

Source-linked AI summary

Criticality and universality in network dismantling

Lorenzo Cirigliano, Claudio Castellano, Minsuk Kim, Filippo Radicchi, Hanlin Sun

arXiv:2608.27613v1physics.soc-phcond-mat.stat-mechcs.SI

TL;DR

Network dismantling has largely been studied through algorithms for finite networks, while its critical behavior in the thermodynamic limit remains less explored. The paper introduces adaptive biased percolation based on edge centrality and finds topology-insensitive critical behavior across network models and real networks. These results support the possibility of a topology-independent theory of network dismantling transitions.

  • Problem

    The paper addresses the limited understanding of how network connectivity changes during dismantling in the thermodynamic limit, beyond algorithmic studies of finite networks.

  • Method

    The paper introduces an adaptive biased percolation process that sequentially removes edges using non-backtracking edge centrality and develops a lower-cost 2-core-degree-centrality surrogate.

  • Results

    The giant component and largest 2-core exhibit universal, largely topology-independent critical behavior across Poisson, power-law, and real networks.

  • Takeaways & Limitations

    The findings suggest that network dismantling transitions may belong to a robust universality class and could admit a relatively simple topology-independent theory.

Abstract

from arXiv · show

Identifying the smallest set of elements whose removal dismantle a complex network, known as the network dismantling problem, is a fundamental task with many practical applications. Whereas network dismantling has been extensively studied over the past decade, most work has focused on developing efficient algorithms for large but finite networks. By contrast, the physics of the network dismantling process, namely how the network structural connectivity is affected by the removal of nodes or edges, remains largely unexplored in the thermodynamic limit. Here, we shed light on this understudied aspect of network dismantling by introducing an adaptive biased percolation process able to optimally dismantle a network. Through a systematic analysis of synthetic network models, we find that the proposed percolation process displays a universal phase transition, characterized by the abrupt and simultaneous disappearance of both the giant connected component and the largest 2-core, across networks with markedly different degree distributions. Simulations on real networks further support this universality, indicating that the physics of network dismantling is insensitive to a broad range of topological properties. Together, these results suggest that a topology-agnostic theory could be developed to explain the critical behavior of network dismantling.

I. INTRODUCTION

The paper reframes network dismantling as an adaptive biased percolation process and shifts attention from finite-network algorithms to critical behavior. It introduces NBC-based edge removal and studies the simultaneous behavior of the giant component and largest 2-core.

  • Motivation: Network dismantling seeks the smallest set of nodes or edges whose removal destroys or sufficiently reduces a network’s giant component.The problem includes minimum-cost formulations and related robustness objectives.
  • Motivation: Existing dismantling methods sequentially remove elements using heuristics evaluated on the current partially dismantled network, but mainly target effective solutions for large finite networks.The thermodynamic-limit physics of the dismantling process remains comparatively unexplored.
  • Model: The proposed adaptive percolation process removes edges according to non-backtracking edge centrality, which depends on the left and right principal eigenvectors of the non-backtracking operator.The framework assigns topology-dependent scores to edges and updates them as the remnant graph changes.
  • Model: Removing the edge with the largest NBC gives the largest single-edge reduction in network robustness, making max-NBC removal a proven greedy-optimal dismantling protocol.The protocol corresponds to setting the bias parameter to a = +∞.
  • Critical behavior: For Poisson and power-law random graphs, the giant component disappears discontinuously while the largest 2-core vanishes continuously at the same critical point, where the network becomes a forest.The critical exponents for max-NBC 2-core disappearance do not depend on the degree distribution.
  • Model: The study uses the giant-component fraction and largest-2-core fraction as non-increasing order parameters during sequential edge removal.These observables are measured on the remnant graph at each percolation stage.

B. Numerical simulations

The numerical analysis averages order parameters over percolation realizations and uses pseudo-critical points, finite-size scaling, and data collapse to characterize transitions across network sizes. Figure 1 illustrates the adaptive max-NBC removal rule.

  • Simulation measurements: Numerical simulations average the giant-component and largest-2-core observables over independent realizations of the percolation process.Pseudo-critical points are identified from the largest drop in the corresponding order parameter.
  • Simulation measurements: Results are reported against p, the fraction of edges removed, enabling comparisons across networks with different numbers of edges.The stage variable t is converted through p = t/E.
  • Adaptive removal: The max-NBC process is illustrated by deleting the highest-scoring edge at each stage, then removing edges uniformly once all scores become zero.Scores are adaptive because they change after each deletion, and only 2-core edges receive positive scores in the example.
  • Finite-size scaling: Finite-size scaling replaces the graph label with network size N and averages over distinct network and percolation instances.The analysis tests scaling relations for pseudo-critical points, pseudo-critical order parameters, and data collapse.
  • Finite-size scaling: Critical exponents are estimated by linear regression on log-transformed variables, generally using network sizes N ≥ 10^3 and reporting Pearson R^2 for fit quality.Exponent uncertainty is derived from the residual standard deviation.

D. Connection to network dismantling

The percolation formulation connects directly to finite-network bond dismantling by defining when a removed-edge sequence reduces the giant component below a size threshold. The exact optimum requires searching all edge permutations, motivating heuristic protocols.

  • Dismantling criterion: A finite network is considered dismantled when its giant component falls below the prescribed threshold, typically the square root of the network size.For a fixed edge sequence, the dismantling point is the smallest removed-edge fraction meeting this condition.
  • Optimization: The optimal unit-cost bond-dismantling problem seeks the edge sequence minimizing the dismantling point, but exact optimization requires testing all E! permutations.This brute-force approach is feasible only for ultra-small networks.

III. NON-BACKTRACKING CENTRALITY

The paper defines non-backtracking centrality (NBC) from the principal eigenvectors of the non-backtracking matrix and uses it to guide adaptive edge removal. The resulting process connects greedy eigenvalue reduction with network dismantling and exhibits a critical transition whose properties depend on bias and network structure in specific ways.

  • Non-backtracking matrix: The non-backtracking matrix is defined on directed edges, and its principal eigenvalue indicates network robustness.The associated left and right Perron eigenvectors are used in the analysis.
  • Non-backtracking centrality: NBC estimates an edge’s leading-order effect on the principal non-backtracking eigenvalue when removed.It is constructed from the left and right principal eigenvector components associated with the edge’s directed representations.
  • Non-backtracking centrality: Removing the edge with the largest NBC produces the strongest leading-order reduction in the principal non-backtracking eigenvalue.The max-NBC protocol therefore provides a greedy-optimal edge-removal strategy for dismantling.
  • Non-backtracking centrality: NBC is positive only for edges in the 2-core and increases with the edge’s participation in loopy structures.Edges outside the 2-core have zero NBC under the stated characterization.
  • NBC-biased percolation: NBC-biased percolation sequentially removes edges according to their NBC score, while its critical point is linked to the number of edges needed to eliminate all cycles.The cyclomatic number gives the minimum removals required to make a graph a forest, although finite graphs may require more because 2-core bridges can be removed.

V. 2-CORE-DEGREE-BIASED (2CDC-BIASED) PERCOLATION

The 2CDC-biased model uses a local edge score based on endpoint degrees within the graph’s 2-core, while retaining a nonlocal dependence through 2-core determination. Its giant-component transition is discontinuous, and its 2-core critical exponents depend on the bias parameter.

  • Model definition: 2CDC assigns each edge a score equal to the sum of its endpoints’ degrees within the graph’s 2-core.The model removes edges using this score within the general biased-percolation framework.
  • Model definition: Although the score is local, computing it requires the whole network topology to determine the 2-core, making the model genuinely nonlocal.
  • Critical behavior: For every bias value, the giant-component transition is discontinuous and has critical exponent β(2CDC,GC) equal to zero.
  • Critical behavior: All critical exponents of the 2-core transition depend on the bias parameter, including ν̄(2CDC,2C).

VI. CRITICAL TREE STRUCTURE

At criticality, NBC- and 2CDC-biased percolation reduce the network to a forest whose largest tree retains essentially the original network size. The tree’s detailed structure can nevertheless differ substantially between biased processes.

  • Critical forest: At criticality, both biased processes produce a forest in which the largest tree is essentially as large as the original network.The processes remove links from loopy structures while disconnecting almost no nodes.
  • Critical forest: The detailed structure of the largest critical tree may differ substantially across biased percolation processes.

A. Synthetic networks

Synthetic-network tests examine critical-tree size and diameter across network models and biased processes. Max-NBC and max-2CDC show universal scaling across different degree distributions, whereas weak bias loses this universality.

  • Scaling analysis: The pseudo-critical tree is characterized by its diameter and size, averaged over independent realizations for NBC and 2CDC processes.
  • Universal scaling: α(NBC) ≃0.88 and α(2CDC) ≃0.66 for max-NBC- and max-2CDC-biased percolation, respectively.These compatible exponent values are observed across synthetic networks with different degree distributions.
  • Universal scaling: Universality is lost for small bias, including a = 0, with different configurations acquiring different critical-exponent values.
  • Hyperscaling: The critical exponent α(x) is related to the 2-core transition exponents β(x,2C) and ν̄(x,2C) through a hyperscaling relation.The relation holds for both NBC- and 2CDC-biased percolation for every bias value.
  • Hyperscaling: The pseudo-critical network consists of a quasi-one-dimensional 2-core with dangling trees, with the trees carrying almost all network mass.This geometry underlies the relation between critical exponents and tree diameter.
  • Scaling analysis: Table II reports best-fit α estimates, their uncertainties, and Pearson R2 values for each network-model and percolation-process combination.

B. Real-world networks

Tests on real networks support topology-robust critical behavior for biased dismantling, while 2CDC offers a cheaper but less effective surrogate for NBC. The max-NBC strategy can preserve macroscopic observables until abrupt collapse, limiting their value as early-warning signals.

  • Real-world scaling: Real-network tests recover power-law scaling similar to synthetic graphs despite broad topological diversity.Most points are compatible with α(NBC,2C) ≃ 0.88; max-2CDC gives α(2CDC,2C) ≃ 0.65.
  • Universality: The optimal-percolation transition appears robust beyond degree distribution, extending across several real-network topological properties.The authors describe this universality as supported, though the real-network scaling is weaker than for synthetic graphs.
  • Surrogate process: 2CDC reproduces the qualitative NBC behavior while reducing computational cost, but it is less effective at reducing network robustness.Its lower cost enables analysis of much larger networks.
  • Dataset: The study analyzes a diverse corpus of 217 monopartite real networks with N < 10^4 nodes and E < 10^5 links.Directed networks are symmetrized, while self-loops and multilinks are removed.
  • Practical implication: Max-NBC removal causes little damage to the GC or 2C before their abrupt collapse, so their sizes provide no early-warning signal.The authors state that new indicators are needed to monitor silently eroded robustness.

Appendix A: Notation

The appendix establishes the non-backtracking matrix notation and its leading spectral objects, then formulates edge removal as a perturbation. The resulting approximation relies on neglecting eigenvector changes, which may fail near the percolation threshold.

  • Basis and notation: The directed-edge basis has dimension 2E and is complete and orthogonal, with identity resolution and Kronecker-delta inner products.This basis represents both orientations of every undirected edge.
  • Spectral objects: The leading NB eigenvalue Λ has nonnegative left and right eigenvectors normalized by ⟨ℓ|r⟩ = 1.For connected networks containing at least two cycles, Λ > 1.
  • Edge perturbation: Removing edge (x,y) is represented as a rank-2 perturbation that zeros the matrix entries associated with both directed orientations.The perturbation uses Q = |x→y⟩⟨x→y| + |y→x⟩⟨y→x|.
  • Perturbative approximation: The eigenvalue-shift approximation assumes the principal eigenvector is unchanged by edge removal.Under this assumption, the perturbation equations yield the relation used for Eq. (14).
  • Limitation: Near the transition, where Λ approaches 1, neglected eigenvector changes can make δΛ depart from the Eq. (14) expression.The numerical experiment tests this approximation across ER, scale-free, clustered, and real-world graphs.

Appendix C: Non-backtracking centrality and participation to loops

Non-backtracking centrality measures edge participation in non-backtracking loops through the NB spectrum. Its loop interpretation explains why high-NBC edges lie in denser 2-core regions and supports strong empirical correlation with topological loop participation.

  • Definition: NBC is a spectral edge centrality derived from the non-backtracking matrix and its eigenstructure.The appendix connects this centrality to the number of cycles containing an edge.
  • Resolvent interpretation: The edge-local resolvent generates the number of non-backtracking loops containing a directed edge.Its leading singularity occurs at z = 1/Λ.
  • Loop participation: NBC weight increases with the number of non-backtracking loops an edge participates in.The asymptotic relation is obtained using the Hardy-Littlewood Tauberian theorem.
  • Structural meaning: Edges with high NBC lie in denser, more connected regions of the graph’s 2-core.Short-loop participation typically accompanies participation in longer loops, whereas the converse need not hold.
  • Numerical validation: NBC and topological-loop counts show strong correlation, with near-perfect correlation already for L ≃ 10.The appendix reports this comparison for small ER networks and weighted loop counts.

Appendix D: Percolation threshold for the dismantling of uncorrelated random graphs

The appendix derives the dismantling threshold as the edge fraction needed to reduce a finite graph to a forest, then estimates its thermodynamic form for uncorrelated random graphs. The estimate assumes finite clusters are tree-like.

  • Finite-network threshold: For a finite graph, Eq. (16) gives the fraction of edges in excess of a loop-less forest.In the thermodynamic limit, it defines the threshold for NBC- and 2CDC-biased percolation.
  • Thermodynamic limit: Estimating the threshold for random graphs requires the scaling of edges E and connected components nC with network size N.These quantities depend on the degree-distribution ensemble.
  • Random-graph derivation: For arbitrary degree distributions, the derivation uses generating-function quantities and the probability z that a random link does not reach the giant component.The resulting expression estimates the thermodynamic critical point.
  • Assumption: The threshold estimate assumes finite clusters are tree-like and contain a negligible number of cycles.Under this assumption, N − nC ≃ N(1 − F).
  • Scale-free examples: The critical-property analysis includes scale-free random graphs with γ = 2.5 and γ = 3.5, alongside the stated synthetic-network settings.The scale-free graphs use kmin = 3 and kmax = N.

Appendix E: max-NBC-biased percolation on

The appendix examines max-NBC-biased percolation on uncorrelated configuration-model graphs and provides supplementary critical-transition results for 2CDC-biased percolation across Erdős–Rényi and scale-free networks.

  • max-NBC-biased percolation: Max-NBC-biased percolation results are reported for graphs generated with the uncorrelated configuration model.The model samples a power-law degree sequence and then creates edges randomly while preserving that sequence.
  • max-NBC-biased percolation: Supplementary curves compare different edge-removal strategies for NBC-biased percolation.Figure S1 is presented as an extension of the main-text Figure 2.
  • 2CDC-biased percolation: Table S1 lists estimated critical exponents for 2CDC-biased percolation transitions across the two network-model families.The table organizes results by network model, monitored order parameter, bias parameter, and critical-exponent values.
  • 2CDC-biased percolation: Figures S2–S7 report giant-component and 2-core transition properties for 2CDC-biased percolation on Erdős–Rényi and scale-free graphs.The scale-free cases use degree exponents γ = 2.5 and γ = 3.5, with results averaged over Q = 10000 model instances.
Loading 2608.27613v1…