On Minimal Sets to Destroy the $k$-Core in Random Networks

Abstract

We study the problem of finding the smallest set of nodes in a network whose removal results in an empty $k$-core; where the $k$-core is the sub-network obtained after the iterative removal of all nodes of degree smaller than $k$. This problem is also known in the literature as finding the minimal contagious set. The main contribution of our work is an analysis of the performance of the recently introduced corehd algorithm [Scientific Reports, 6, 37954 (2016)] on random networks taken from the configuration model via a set of deterministic differential equations. Our analyses provides upper bounds on the size of the minimal contagious set that improve over previously known bounds. Our second contribution is a new heuristic called the weak-neighbor algorithm that outperforms all currently known local methods in the regimes considered.

arXiv comment17 pages, 2 figures, 3 tables

References in corpus (9)

• Network dismantling
• Identifying optimal targets of network attack by belief propagation
• Fast and simple decycling and dismantling of networks
• Spin glass approach to the feedback vertex set problem
• Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms
• Optimizing spread dynamics on graphs by message passing
• Efficient collective influence maximization in cascading processes with first-order transitions
• Large deviations of cascade processes on graphs
• Minimal contagious sets in random regular graphs

Cited by in corpus (5)

• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Hierarchical cycle-tree packing model for $K$-core attack problem
• COREATTACK: Breaking Up the Core Structure of Graphs
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• On the Decycling Number of $4$-regular Random Graphs