PaperlayerView exact revision on arXiv

Source-linked AI summary

Network dismantling

Alfredo Braunstein, Luca Dall'Asta, Guilhem Semerjian, Lenka Zdeborová

arXiv:1603.08883v2physics.soc-phcond-mat.stat-mechcs.DS

TL;DR

The paper asks how to remove a minimal node set that breaks a network into small components, and studies this through decycling theory and statistical mechanics. It develops a three-stage Min-Sum algorithm and finds near-optimal or substantially improved dismantling on random and real-world networks. The results also indicate that effective dismantling sets are collective rather than collections of individually important nodes.

  • Problem

    The paper addresses how to determine dismantling numbers, compare heuristic algorithms with optimal solutions, and evaluate them on random and real-world graphs despite NP-complete worst-case complexity.

  • Method

    The paper combines a decycling connection, statistical-mechanics analysis, and a three-stage algorithm consisting of Min-Sum decycling, tree breaking, and greedy cycle reintroduction.

  • Results

    The algorithm outperforms prior heuristics, removing 13% fewer nodes than collective influence on an ER graph and achieving a 60% improvement on the studied Twitter network.

  • Takeaways & Limitations

    Dismantling is intrinsically collective, so effective dismantling sets cannot be understood as collections of individually well-performing nodes.

Abstract

from arXiv · show

We study the network dismantling problem, which consists in determining a minimal set of vertices whose removal leaves the network broken into connected components of sub-extensive size. For a large class of random graphs, this problem is tightly connected to the decycling problem (the removal of vertices leaving the graph acyclic). Exploiting this connection and recent works on epidemic spreading we present precise predictions for the minimal size of a dismantling set in a large random graph with a prescribed (light-tailed) degree distribution. Building on the statistical mechanics perspective we propose a three-stage Min-Sum algorithm for efficiently dismantling networks, including heavy-tailed ones for which the dismantling and decycling problems are not equivalent. We also provide further insights into the dismantling problem concluding that it is an intrinsically collective problem and that optimal dismantling sets cannot be viewed as a collection of individually well performing nodes.

I. INTRODUCTION

The paper frames network dismantling as an optimization problem: remove as few nodes as possible while breaking a giant component into sufficiently small components. It formalizes dismantling sets and positions the work around optimal attacks, defenses, and representative random-graph instances.

  • A network is modeled as nodes connected by edges, and removing a selected node set changes connectivity, cycles, and epidemic spreading.
  • Optimal node selection creates a combinatorial optimization problem that minimizes the cost of S subject to a constraint on its graph-level effect.
  • A giant component is the largest component containing a positive fraction of vertices in the N →∞ limit.
  • A C-dismantling set is a node set whose removal leaves every component at most C nodes, while the dismantling number is the minimum size of such a set.
  • The paper asks how dismantling numbers behave on random graphs and how heuristic algorithms compare with optima and real-world benchmarks, given NP-complete worst-case decision complexity.

II. OUR MAIN CONTRIBUTION

The paper combines statistical-mechanics analysis with a three-stage dismantling algorithm. It reports near-optimal results on random graphs, substantial improvements over prior heuristics on real networks, and evidence that dismantling depends on collective node choices.

  • Theoretical estimates for large random networks use the connection between dismantling and decycling together with optimal-spreading results and a one-step replica-symmetry-broken ground-state calculation.
  • The algorithm uses Min-Sum decycling, greedy tree breaking below threshold C, and greedy reintroduction of cycles for graphs with many short cycles.
  • The decycling-first strategy is optimal for graphs with few short cycles, while greedy cycle reintroduction improves efficiency when short cycles are numerous.
  • Dismantling is intrinsically collective: selecting the most frequently appearing nodes required 20.1% removal, versus 17.8% for systematic Min-Sum optimization.
  • 17.8% of nodes dismantled an ER graph versus 20.2% for adaptive eigenvalue centrality and 20.6% for collective influence, a 13% improvement over the state of the art.
  • 3.4% of nodes dismantled a 532,000-node Twitter network into components smaller than C = 1000, compared with 5.6% for collective influence, a 60% improvement.
  • The core algorithm runs in linear time over the number of edges, enabling dismantling of networks with tens of millions of nodes.

III. THE RELATION BETWEEN DISMANTLING AND DECYCLING

For random graphs, dismantling is no harder than decycling, and the two asymptotic parameters coincide for light-tailed degree distributions. The equivalence follows from efficiently dismantling forests and controlling short cycles.

  • The dismantling parameter allows remaining components to be sub-extensive, including components with vanishing intensive size under an equivalent order of limits.The alternative formulation uses limϵ→0 limN→∞E[θdis(G, ϵN)].
  • θdis(q) ≤ θdec(q) for any degree distribution, while θdis(q) = θdec(q) when q has a finite second moment.The paper calls distributions with a finite second moment light-tailed.
  • A decycling set can be extended to a C-dismantling set with additional cost at most 1/(C + 1).This bound vanishes as C grows after taking the large-network limit.
  • A C-dismantling set can be converted into a decycling set by removing at most one additional vertex per remaining cycle of length at most C.The resulting bound is θdec(G) ≤ θdis(G, C) + nC(G)/N.

IV. NETWORK DECYCLING

This section connects the paper’s decycling analysis to an efficient heuristic algorithm for arbitrary graphs.

  • Statistical-mechanics results for random-graph decycling are used to construct an efficient heuristic algorithm for decycling arbitrary graphs.

A. Testing the presence of cycles in a graph

Cycle testing is reduced to leaf removal: after deleting a candidate set, the remaining graph is acyclic exactly when its 2-core disappears. The dynamics can also be viewed as threshold spreading.

  • A graph contains cycles if and only if its 2-core is non-empty after iteratively removing isolated vertices and leaves.The 2-core is the largest subgraph of minimum degree 2.
  • The leaf-removal dynamics mark initially removed vertices at t = 0 and evolve binary vertex states using local neighborhood information.The variables are initialized with x0_i(S) = 1 for i ∈ S and 0 otherwise.
  • A set S is decycling exactly when every vertex eventually reaches the removed state, equivalently when the remaining graph has no 2-core.At the fixed point, x*_i(S) = 0 precisely for vertices in the 2-core of G \ S.
  • Leaf removal is equivalent to a threshold-spreading process in which a vertex activates when all but one of its neighbors are infected or informed.This connection lets the analysis draw on minimal contagious sets and influence maximization.

B. Optimizing the size of decycling sets

The paper converts leaf-removal dynamics into a local statistical-mechanics model over removal times, then applies cavity methods and Min-Sum optimization to estimate small decycling sets.

  • B. Optimizing the size of decycling sets: The statistical-mechanics measure assigns positive probability only to decycling sets, whose minimum size is obtained from the zero-temperature ground-state limit.The parameter µ acts as a chemical potential or inverse temperature.
  • B. Optimizing the size of decycling sets: The exact partition-function computation remains NP-hard on arbitrary graphs because the fixed-point variables depend non-locally on the selected set.
  • B. Optimizing the size of decycling sets: Removal times transform the non-equilibrium leaf-removal process into an equilibrium model with locally interacting static variables.The resulting partition function exactly counts decycling sets according to their size.
  • B. Optimizing the size of decycling sets: For sparse random graphs, the cavity method computes the large-size free-energy density using messages exchanged between neighboring nodes.Its exactness is established for relevant locally tree-like light-tailed random graphs.
  • B. Optimizing the size of decycling sets: Table I compares 1RSB cavity predictions with decycling numbers reached by Min-Sum on Erdős–Rényi graphs of size N = 10^7.Rows correspond to average degree d.

C. Min-Sum algorithm for the decycling problem

The Min-Sum algorithm approximates minimum-cost decycling by optimizing vertex removal times through message passing, then constructs a decycling set from the resulting assignments. Its iterative computation is efficient and supports finite removal-time cutoffs and constraints on marked vertices.

  • Min-Sum formulation: The heuristic assigns each vertex a removal time and includes it in the decycling set exactly when its optimal time is zero.A perturbed cost function makes the minimum unique with probability 1, enabling construction of a minimal decycling set.
  • Message passing: Min-Sum approximates the minimum feasible cost by exchanging cost-valued messages between neighboring vertices.The message fields represent minimal costs under prescribed removal-time conditions.
  • Computational cost: Each iteration requires O(|E| T) elementary operations, where |E| is the number of edges and T is the removal-time cutoff.Relatively few iterations usually suffice for convergence.
  • Computational cost: Using a finite cutoff T constrains the diameter of tree components after removal, yet did not extensively increase decycling-set size in the reported simulations.The simulations used T = 35, although solving decycling exactly would in principle require T greater than N.
  • Algorithm flexibility: The algorithm is flexible enough to forbid removal of marked vertices by assigning infinite cost to their removal-time-zero state.This constraint is implemented through ψ_i(t_i = 0) = ∞.

A. Results on random graphs

On Erdős-Rényi graphs, Min-Sum followed by greedy tree breaking achieves near-optimal dismantling with strong finite-size scaling. The diversity and overlap of near-optimal sets further show that dismantling depends on collective node selection rather than individually influential vertices.

  • Algorithm performance: 17.81% node removal leaves an acyclic graph whose largest components contain 3.2% of the vertices on an Erdős-Rényi graph with average degree 3.5.The second algorithmic stage then greedily breaks the remaining trees.
  • Algorithm performance: 13% fewer nodes than Collective Influence are required by Min-Sum to dismantle the graph, while Simulated Annealing performs well but is considerably slower.The comparison includes random removal, adaptive degree, eigenvector centrality, Collective Influence, and Simulated Annealing.
  • Finite-size scaling: The collapse of scaling curves indicates that reducing the largest component to a fixed size C requires removing S = sN nodes, with s independent of N.This scaling behavior is shown for Min-Sum followed by greedy tree breaking on ER graphs of average degree 3.5.
  • Structure of solutions: Pairs of 1000 near-optimal decycling sets overlap by 82% on average, although about 60% of nodes appear in none of the sets.All sets had sizes within 40 nodes of one another, while other nodes appeared in only a fraction of sets.
  • Collective structure: Selecting the most frequently recurring nodes requires 20.1% removal, versus 17.8% for systematic Min-Sum dismantling.This comparison supports the conclusion that dismantling sets are intrinsically collective rather than collections of individually influential spreaders.
  • Node selection: Restricting removals to degree-at-least-five nodes increases decycling-set size by only 0.2%, indicating that low-degree nodes are not indispensable.In an ER graph with average degree 6 and size 57, a typical Min-Sum decycling set contained around 460 nodes of degree 4 or lower.

B. More general graphs

For graphs with many short cycles, decycling can remove substantially more nodes than necessary for dismantling. A reverse-greedy reinsertion step substantially improves Min-Sum solutions on real-world networks, including Twitter and YouTube.

  • B. More general graphs: Decycling and dismantling are asymptotically equivalent for light-tailed random graphs but can differ greatly in arbitrary graphs with many small cycles.In such graphs, decycling may remove nodes solely to destroy short cycles even when those nodes can later be restored without enlarging the largest component.
  • B. More general graphs: The reverse-greedy procedure reinserts removed nodes while targeting a chosen upper bound on the largest component.At each step, it selects the removed node whose reinsertion produces the smallest connected component; its update cost is bounded by kmaxC′ log(kmaxC′).
  • B. More general graphs: 32% fewer nodes were needed for CI and 20% fewer for MS on the Twitter network after reverse-greedy reinsertion.The MS solution dismantled the network into components smaller than C = 1000 using only 3.4% of nodes.
  • B. More general graphs: 4.0% of nodes formed the best MS+RG dismantling set found for the 1.13-million-node YouTube network, a 22% improvement over CI.The procedure reached or improved the best result obtained with simulated annealing on the Twitter network.
  • B. More general graphs: The theoretical results apply only to graph classes without many small cycles and do not provide a principled analysis of reverse-greedy reinsertion.Dismantling methods for networks where decycling is not a reasonable starting point remain an open direction.

Appendix A: Proof of NP-Completeness of the dismantling problem

The dismantling decision problem is NP-complete when the allowed largest-component size grows sublinearly with graph size. The proof reduces Vertex Cover to dismantling by attaching leaves to every original vertex.

  • Appendix A: Proof of NP-Completeness of the dismantling problem: The reduction starts from the NP-complete Vertex Cover problem.A vertex cover is a vertex subset incident to every edge.
  • Appendix A: Proof of NP-Completeness of the dismantling problem: Theorem 1 establishes NP-completeness for C(N)-Dismantling when C is non-decreasing, polynomially computable, and C(N) < N^a for some a < 1.The stated cases include constant C, logarithmic C, and C(N) = N^a with 0 ≤ a < 1.
  • Appendix A: Proof of NP-Completeness of the dismantling problem: The constructed graph G′ adds C′ − 1 leaves to each vertex of an N-vertex graph, producing N′ = NC′ vertices.The construction is polynomial in N.
  • Appendix A: Proof of NP-Completeness of the dismantling problem: Any vertex cover W of the original graph becomes a C′-dismantling set of G′ because uncovered original vertices retain only their attached leaves.The reduction then relates C′ to the target component bound C(N′).
  • Appendix A: Proof of NP-Completeness of the dismantling problem: Conversely, replacing selected leaves by their attached original vertices yields a no-larger dismantling set that is also a vertex cover.Replacing leaves by originals creates isolated leaves and cannot increase other component sizes.
  • Appendix A: Proof of NP-Completeness of the dismantling problem: (N − k)-Dismantling is polynomial for every constant k.This is a separate tractable boundary from the sublinear-component regime covered by Theorem 1.

Appendix B: Analytic results

The appendix develops cavity-method estimates and graph-wide lower bounds for the decycling number, with replica-symmetry breaking tightening the predictions for light-tailed random graphs. It also gives numerical and asymptotic results for Poissonian graphs.

  • 1. Details on the cavity equations for the decycling number of random graphs: The cavity method computes the decycling number of sparse random graphs through belief-propagation message distributions and population dynamics.The message law satisfies an integral self-consistency equation, which is solved numerically by iteratively updating representative samples until convergence.
  • 1. Details on the cavity equations for the decycling number of random graphs: The replica-symmetric estimate identifies the decycling threshold where the entropy of decycling sets vanishes.Varying the chemical potential computes the entropy as a function of the selected vertex fraction.
  • 1. Details on the cavity equations for the decycling number of random graphs: 1RSB improves the lower bound relative to replica symmetry, satisfying θRS(q) ≤ θ1RSB(q) ≤ θdec(q).For some degree distributions the bounds become equalities, while for others the 1RSB estimate remains strictly below the exact value.
  • 2. A simple lower bound: Table II reports the dependence of RS and 1RSB cavity predictions on cutoff T for Erdős–Rényi graphs with average degree d = 3.5.The main-text table values are obtained by extrapolating the 1RSB results to T →∞.
  • 2. A simple lower bound: The graph-wide lower bound θlb is obtained by ordering vertices by degree and finding where an increasing piecewise-linear function intersects the bound constraint.For random graphs, the empirical degree distribution is replaced by the prescribed distribution q.
  • 2. A simple lower bound: For a Poissonian graph with average degree d = 3.5, the lower bound is θlb = 0.141084 versus the 1RSB prediction θdec = 0.175.The lower bound approaches the percolation-threshold expansion near d → 1 and reaches 1/2 as d diverges, while θdec tends to 1.

1. The Min-Sum algorithm and its implementation

The Min-Sum algorithm formulates decycling through message passing over activation-time configurations, is exact on trees, and serves as a heuristic on general graphs. Efficient simplifications reduce its per-iteration computation to O(|E| T), while experiments characterize its behavior relative to simulated annealing and score-based methods.

  • Algorithmic formulation: Min-Sum seeks the smallest decycling set by minimizing a cost function over feasible vertex activation times.Vertices assigned activation time 0 belong to the decycling set; other activation times satisfy the neighboring-variable constraint.
  • Algorithmic formulation: The strict and relaxed leaf-removal constraints are equivalent when T ≥ N, while the relaxed optimum remains a valid decycling set for smaller T.The equivalence follows from the order-independent 2-core produced by leaf removal.
  • Implementation: Message parametrization reduces the two-time-index quantities from O(T^2) per edge to O(T) real numbers.The reduction uses the messages’ dependence on the activation-time inequality I[t_j < t_i].
  • Implementation: A complete message-passing iteration can be computed in O(|E| T) time after shared quantities are pre-computed.The implementation is linear in T and in the degree for each vertex, and computes outgoing messages efficiently.
  • Algorithmic formulation: On trees, the Min-Sum recurrence converges exactly to the unique minimum of the cost function.On graphs with few short loops, iterating the same equations provides a heuristic approximation to the optimum.
  • Empirical comparisons: For small Erdös-Rényi graphs, sufficiently slow simulated annealing can outperform Min-Sum, but its quality degrades as graph size increases.The annealing protocol must become increasingly slower to match Min-Sum on larger graphs.
  • Empirical comparisons: Collective Influence becomes computationally demanding at ℓ = 4 or 5 on expander graphs because the surrounding ball grows exponentially with ℓ.Its score combines the node’s degree with the number of edges emerging at the boundary of the distance-ℓ ball.
  • Empirical comparisons: Betweenness and non-backtracking centrality perform qualitatively and quantitatively similarly to, or worse than, Eigenvector Centrality on the considered graphs.These centrality variants were therefore not reported in the paper’s results.

Appendix D: Other real-world and scale-free graphs

The appendix evaluates dismantling methods on real-world, scale-free, and clustered small-world networks. Reverse Greedy improves heuristic solutions broadly, whereas strong short-loop structure makes decycling-based strategies less effective and gives simulated annealing an advantage.

  • Scope and limitations: Decycling-based dismantling is guaranteed optimal only for sparse random graphs with locally tree-like structure.The stated guarantee does not extend generally to networks containing many small loops.
  • Real-world and scale-free networks: Scale-free experiments used N = 10^4 nodes with P(d) ∝ d^-γ and γ = 2.5, comparing centrality, Collective Influence, Min-Sum, and simulated annealing.The figure reports largest-component size as a function of removed-node fraction S.
  • Real-world and scale-free networks: Reverse Greedy usually produces very good results on networks with many small loops when added to the dismantling algorithm.The paper cites the Twitter graph as an example and compares results against simulated annealing and other reverse-greedy heuristics.
  • Real-world and scale-free networks: 3.97% of nodes dismantled the 1.13-million-node YouTube network into components smaller than C = 1000 using MS+RG.The corresponding CI+RG and EC+RG sizes were 4.03% and 4.07%, respectively.
  • Clustered small-world networks: When short loops dominate in clustered Watts–Strogatz networks, simulated annealing performs about 30% better than the other tested algorithms.Starting simulated annealing from Min-Sum solutions improves results but remains inferior to simulated annealing alone because the solution overlap is usually small.
Loading 1603.08883v2…