Spin-glass model for the C-dismantling problem

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 ${\rho }_c$ of the relative size of D with finite C on regular random graphs and Erdos-Renyi random graphs. We find ${\rho }_c$ will decrease gradually with growing C and it converges to ${\rho }_{\infty }$ as C$\to \infty$. The CD problem is called dismantling problem when C is a small finite fraction of |V|. Therefore, ${\rho }_{\infty }$ is also the lower bound of the dismantling problem when |V|$\to \infty$. 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$\to \infty$. 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 (13)

• Vital nodes identification in complex networks
• Robust network community detection using balanced propagation
• Fast and simple decycling and dismantling of networks
• Immunization and targeted destruction of networks using explosive percolation
• Message passing for vertex covers
• Minimal contagious sets in random regular graphs
• Solving the undirected feedback vertex set problem by local search
• $T\to 0$ 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

Cited by in corpus (1)

• Minimum Long-Loop Feedback Vertex Set and Network Dismantling