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

作　　者：Hai-Jun Zhou 

机构地区：[1]CAS Key Laboratory for Theoretical Physics,Institute of Theoretical Physics,Chinese Academy of Sciences,Beijing 100190,China [2]MinJiang Innovative Center for Theoretical Physics,MinJiang University,Fuzhou 350108,China [3]School of Physical Sciences,University of Chinese Academy of Sciences,Beijing 100049,China

出　　处：《Science China(Physics,Mechanics & Astronomy)》2022年第3期33-38,共6页中国科学：物理学、力学、天文学（英文版）

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.11975295,and 12047503);and the Chinese Academy of Sciences(Grant Nos.QYZDJ-SSW-SYS018,and XDPD15)。

摘　　要：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.

关 键 词：K-core collapse spin glass model tree packing optimal initial condition random graph 

分 类 号：O157.5[理学—数学]