TY - JOUR
T1 - Efficient Continuous Network Dismantling
AU - Liu, Yang
AU - Chen, Xiaoqi
AU - Wang, Xi
AU - Su, Zhen
AU - Fan, Shiqi
AU - Wang, Zhen
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2025
Y1 - 2025
N2 - A great number of studies have demonstrated that many complex systems could benefit a lot from complex networks, through either a direct modeling on which dynamics among agents could be investigated in a global view or an indirect representation by the aid of that the leading factors could be captured more clearly. Hence, in the context of networks, this article copes with the continuous network dismantling problem which aims to find the key node set whose removal would break down a given network more thoroughly and thus is more capable of suppressing virus or misinformation. To achieve this goal effectively and efficiently, we propose the external-degree and internal-size component suppression (EDIS) framework based on the network percolation, where we constrain the search space by a well-designed local goal function and candidate selection approach such that EDIS could obtain better results than the-state-of-the-art in networks of millions of nodes in seconds. We also contribute two strategies with time complexity O(mv m) and space complexity O(m) , of networks of m edges, under such framework by well studying the evolving characteristics of the associated connected components as nodes are occupied, where v >1 is a hyperparameter. Our results on 12 empirical networks from various domains demonstrate that the proposed method has far better performance than the-state-of-the-art over both effectiveness and computing time. Our study could play important roles in many real-world scenarios, such as the containment of misinformation or epidemics, the distribution of resources or vaccine, the decision of which group of individuals set to quarantine, or the detection of the resilience of a network-based system under intentional attacks.
AB - A great number of studies have demonstrated that many complex systems could benefit a lot from complex networks, through either a direct modeling on which dynamics among agents could be investigated in a global view or an indirect representation by the aid of that the leading factors could be captured more clearly. Hence, in the context of networks, this article copes with the continuous network dismantling problem which aims to find the key node set whose removal would break down a given network more thoroughly and thus is more capable of suppressing virus or misinformation. To achieve this goal effectively and efficiently, we propose the external-degree and internal-size component suppression (EDIS) framework based on the network percolation, where we constrain the search space by a well-designed local goal function and candidate selection approach such that EDIS could obtain better results than the-state-of-the-art in networks of millions of nodes in seconds. We also contribute two strategies with time complexity O(mv m) and space complexity O(m) , of networks of m edges, under such framework by well studying the evolving characteristics of the associated connected components as nodes are occupied, where v >1 is a hyperparameter. Our results on 12 empirical networks from various domains demonstrate that the proposed method has far better performance than the-state-of-the-art over both effectiveness and computing time. Our study could play important roles in many real-world scenarios, such as the containment of misinformation or epidemics, the distribution of resources or vaccine, the decision of which group of individuals set to quarantine, or the detection of the resilience of a network-based system under intentional attacks.
KW - Complex networks
KW - diffusion containment
KW - network dismantling
KW - network percolation
KW - spreading dynamics
UR - http://www.scopus.com/inward/record.url?scp=85210979907&partnerID=8YFLogxK
U2 - 10.1109/TSMC.2024.3496694
DO - 10.1109/TSMC.2024.3496694
M3 - 文章
AN - SCOPUS:85210979907
SN - 2168-2216
VL - 55
SP - 976
EP - 989
JO - IEEE Transactions on Systems, Man, and Cybernetics: Systems
JF - IEEE Transactions on Systems, Man, and Cybernetics: Systems
IS - 2
ER -