A novel algorithm for the generalized network dismantling problem based on dynamic programming

Zhidan Feng, Huimin Song and Xingqin Qi

Chaos, Solitons & Fractals, 2024, vol. 180, issue C

Abstract: For an undirected network G=(V,E) with removal cost on each node, the generalized network dismantling problem is to find a node subset S⊆V with the minimum overall removal cost, such that the size of each connected component in G−S is not larger than a given integer K. This issue has wide applications at network destruction (e.g., combating crime network) or network defense (e.g., strengthening the infrastructure), and has gained growing attentions from various research fields. In graph theory, cut nodes play important roles in ensuring network connectivity, which could of course be regarded as potential removal candidates for this network dismantling problem. This paper is primarily dedicated to this point. Here, having the aid of an auxiliary block-cut tree, we transform the network dismantling problem into a relatively simple problem −− tree dismantling problem, and then design a bottom-up dynamic programming algorithm (abbreviated as DPA) to dismantle this auxiliary tree by removing cut nodes with minimum overall removal costs. This DPA dismantling strategy has been tested on both synthetic networks and real-world networks, and numerical experiments demonstrate the superiority of this method. Our results shed light on more explorations of network structure from the cut-node perspectives.

Keywords: Generalized network dismantling; Block; Cut node; Dynamic programming (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S096007792400136X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:180:y:2024:i:c:s096007792400136x

DOI: 10.1016/j.chaos.2024.114585

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().