Dismantling networks abruptly by tree decomposition

¹ SDU-ANU Joint Science College, Shandong University - Weihai 264209, China
² School of Mathematics and Statistics, Shandong University - Weihai 264209, China

^(a) E-mail: zlouc@sdu.edu.cn (corresponding author)

Received: 29 March 2023
Accepted: 20 July 2023

Abstract

Dismantling a network by removing the minimum vertices is a challenging problem in complex networks. While most existing methods focus on efficiency, they overlook the importance of abruptness during the dismantling process. Gradual changes in the largest connected component size can alert the target and render the attack ineffective. To overcome this issue, we propose a new dismantling method based on tree decomposition and a new metric quantifying the abruptness of the dismantling process. Our method involves applying tree decomposition to the network using the min fill-in method, identifying the most critical edge in the decomposed tree, and removing the vertices contained in the edge. Experimental results on eight real networks demonstrate that our proposed method significantly outperforms classical methods in abruptness and efficiency.