2018/11/28 by Shao-Meng Qin
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematical physics #Mathematics #Physics #Quantum mechanics #Random graph #Spin glass #Theoretical and Computational Physics #Upper and lower bounds #Vertex (graph theory) #physics.soc-ph #stat.CO
paper · pdf · doi:10.1103/physreve.98.062309
arxiv created 2018/11/28 · openalex created_date 2018/12/11 · openalex publication_date 2018/12/12 · arxiv updated 2018/12/26 · openalex updated_date 2026/08/05
The 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 with the belief-propagation (BP) equations under the replica-symmetry ansatz. We give the lower bound \ensuremathρc of the relative size of D with finite C on regular random graphs and Erd\ifmmode \mbox\Ho\else \Ho\fis-R'enyi random graphs. We find \ensuremathρc will decrease gradually with growing C, and it converges to \ensuremathρ_\ensuremath∞ as C\ensuremath→\ensuremath∞. The CD problem is called the dismantling problem when C is a small finite fraction of |V|. Therefore, \ensuremathρ_\ensuremath∞ is also the lower bound of the dismantling problem when |V|\ensuremath→\ensuremath∞. 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\ensuremath→\ensuremath∞. 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)]. Finally, 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 of 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 a small clustering coefficient when C is large.