paper

Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm

arXiv:2110.05940 · doi:10.1007/s11433-021-1845-6

Abstract

The K-core of a graph is the maximal subgraph within which each vertex is connected to at least K other vertices. It is a fundamental network concept for understanding threshold cascading processes with a discontinuous percolation transition. A minimum attack set contains the smallest number of vertices whose removal induces complete collapse of the K-core. Here we tackle this prototypical optimal initial-condition problem from the spin-glass perspective of cycle-tree maximum packing and propose a cycle-tree guided attack (CTGA) message-passing algorithm. The good performance and time efficiency of CTGA are verified on the regular random and Erdös-Rényi random graph ensembles. Our central idea of transforming a long-range correlated dynamical process to static structural patterns may also be instructive to other hard optimization and control problems.

arXiv commentA label in Figure 3(b) was corrected

References in corpus (24)

Cited by in corpus (3)