Spin-glass model for the C-dismantling problem
arXiv:1811.11394 · doi:10.1103/PhysRevE.98.062309
Abstract
C-dismantling (CD) problem aims at finding the minimum vertex set D of a graph G(V,E) after removing which the remaining graph will break into connected components with the size not larger than C. In this paper, we introduce a spin-glass model with C+1 integer-value states into the CD problem and then study the properties of this spin-glass model by the belief-propagation (BP) equations under the replica-symmetry ansatz. We give the lower bound of the relative size of D with finite C on regular random graphs and Erdos-Renyi random graphs. We find will decrease gradually with growing C and it converges to as C. The CD problem is called dismantling problem when C is a small finite fraction of |V|. Therefore, is also the lower bound of the dismantling problem when |V|. To reduce the computation complexity of the BP equations, taking the knowledge of the probability of a random selected vertex belonging to a remaining connected component with the size A, the original BP equations can be simplified to one with only three states when C. The simplified BP equations are very similar to the BP equations of the feedback vertex set spin-glass model [H.-J.~Zhou, Eur. Phys. J. B 86, 455 (2013)]. At last, we develop two practical belief-propagation-guide decimation algorithms based on the original BP equations (CD-BPD) and the simplified BP equations (SCD-BPD) to solve the CD problem on a certain graph. Our BPD algorithms and two other state-of-art heuristic algorithms are applied on various random graphs and some real world networks. Computation results show that the CD-BPD is the best in all tested algorithms in the case of small C. But considering the performance and computation consumption, we recommend using SCD-BPD for the network with small clustering coefficient when C is large.
References in corpus (32)
- Error and attack tolerance of complex networks
- Epidemic spreading in scale-free networks
- Network robustness and fragility: Percolation on random graphs
- Attack vulnerability of complex networks
- Breakdown of the Internet under intentional attack
- Influence maximization in complex networks through optimal percolation
- Universal Behavior of Load Distribution in Scale-free Networks
- Vital nodes identification in complex networks
- The Bethe lattice spin glass revisited
- The structural glass transition and the entropy of the metastable states
- Network dismantling
- Robust network community detection using balanced propagation
- Identifying optimal targets of network attack by belief propagation
- Fast and simple decycling and dismantling of networks
- Containing epidemic outbreaks by message-passing techniques
- Immunization and targeted destruction of networks using explosive percolation
- Loops of any size and Hamilton cycles in random scale-free networks
- Spin glass approach to the feedback vertex set problem
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Message passing for vertex covers
- Inverse targeting -- an effective immunization strategy
- Minimal contagious sets in random regular graphs
- Circuits in random graphs: from local trees to global loops
- An algorithm for counting circuits: application to real-world and random graphs
- Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
- Solving the undirected feedback vertex set problem by local search
- mean-field population dynamics approach for the random 3-satisfiability problem
- Statistical physics of hard combinatorial optimization: The vertex cover problem
- Spectral estimation of the percolation transition in clustered networks
- Spin glass phase transitions in the random feedback vertex set problem
- A spin glass approach to the directed feedback vertex set problem
- Typical Approximation Performance for Maximum Coverage Problem