EUVIMEDEUVIMED entdecken
Crossref

Efficient Continuous Network Dismantling

Yang Liu, Xiaoqi Chen, Xi Wang, Zhen Su, Shiqi Fan, Zhen Wang

IEEE Transactions on Systems, Man, and Cybernetics: Systems · 2025-02 · 55 (2) · 976-989

DOI: 10.1109/tsmc.2024.3496694 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2025-02. Verfasst von Yang Liu und 5 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 76 Literaturangaben. Gefördert von: National Natural Science Foundation of China, National Science Fund for Distinguished Young Scholars, Fundamental Research Funds for the Central Universities.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 ${\mathcal {O}}(m\log _{\vartheta } m)$ and space complexity ${\mathcal {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 $\vartheta \gt 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.

Förderung

  • National Natural Science Foundation of China
  • National Science Fund for Distinguished Young Scholars
  • Fundamental Research Funds for the Central Universities
  • Tencent Foundation and XPLORER PRIZE

Zitieren

APA

Liu, Y., Chen, X., Wang, X., Su, Z., Fan, S., & Wang, Z. (2025). Efficient Continuous Network Dismantling. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 55(2), 976-989. https://doi.org/10.1109/tsmc.2024.3496694

Vancouver

Liu Y, Chen X, Wang X, Su Z, Fan S, Wang Z. Efficient Continuous Network Dismantling. IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2025;55(2):976-989. doi:10.1109/tsmc.2024.3496694

BibTeX
@article{Liu2025,
  author = {Liu, Yang and Chen, Xiaoqi and Wang, Xi and Su, Zhen and Fan, Shiqi and Wang, Zhen},
  title = {Efficient Continuous Network Dismantling},
  journal = {IEEE Transactions on Systems, Man, and Cybernetics: Systems},
  year = {2025},
  volume = {55},
  number = {2},
  pages = {976--989},
  doi = {10.1109/tsmc.2024.3496694}
}
Kostenlos starten →