Generalized network dismantling
Open accessThe DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Abstract
Finding an optimal subset of nodes in a network that is able to efficiently disrupt the functioning of a corrupt or criminal organization or contain an epidemic or the spread of misinformation is a highly relevant problem of network science. In this paper, we address the generalized network-dismantling problem, which aims at finding a set of nodes whose removal from the network results in the fragmentation of the network into subcritical network components at minimal overall cost. Compared with previous formulations, we allow the costs of node removals to take arbitrary nonnegative real values, which may depend on topological properties such as node centrality or on nontopological features such as the price or protection level of a node. Interestingly, we show that nonunit costs imply a significantly different dismantling strategy. To solve this optimization problem, we propose a method which is based on the spectral properties of a node-weighted Laplacian operator and combine it with a fine-tuning mechanism related to the weighted vertex cover problem. The proposed method is applicable to large-scale networks with millions of nodes. It outperforms current state-of-the-art methods and opens more directions for understanding the vulnerability and robustness of complex systems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35019019 · Cited by 7,534
The spreading of misinformation online
Del Vicario, M., Bessi, A., Zollo, F., Petroni, F., Scala, A., Caldarelli, G., Stanley, H. E., & Quattrociocchi, W. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1517441113 · Cited by 2,407 · cited 5×
“Let v (1) be the eigenvector with the largest eigenvalue and v (2) be the eigenvector with the second-largest eigenvalue.”
BackgroundMethodInfluentialCritical phenomena in complex networks
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1275 · Cited by 2,220
Globally networked risks and how to respond
Helbing, D. (2013) · Nature · doi:10.1038/nature12047 · Cited by 1,281
Self-citationThe Hidden Geometry of Complex, Network-Driven Contagion Phenomena
Brockmann, D., & Helbing, D. (2013) · Science · doi:10.1126/science.1245200 · Cited by 1,253 · cited 1×
“The quick global spread of rumors and fake news may be seen as recent examples (2, 3), while the spread of epidemics (4, 5) or failure propagation (6, 7) is a problem that has been around much longer.”
BackgroundSelf-citationGilbert, E. N. (1959) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177706098 · Cited by 1,122
DebtRank: Too Central to Fail? Financial Networks, the FED and Systemic Risk
Battiston, S., Puliga, M., Kaushik, R., Tasca, P., & Caldarelli, G. (2012) · Scientific Reports · doi:10.1038/srep00541 · Cited by 919
Will Democracy Survive Big Data and Artificial Intelligence?
Helbing, D., Frey, B. S., Gigerenzer, G., Hafen, E., Hagner, M., Hofstetter, Y., van den Hoven, J., Zicari, R. V., & Zwitter, A. (2019) · Towards Digital Enlightenment · doi:10.1007/978-3-319-90869-4_7 · Cited by 355
Self-citationBig Data, Big Problems: Emerging Issues in the Ethics of Data Science and Journalism
Fairfield, J., & Shtein, H. (2014) · Journal of Mass Media Ethics · doi:10.1080/08900523.2014.863126 · Cited by 89
Research works printed but not linked: 33
- MM Waldrop, News feature: The genuine problem of fake news. Proc Natl Acad Sci USA 114, 12631–12634 (2017). · DOI
- A Vespignani, Modelling dynamical processes in complex socio-technical systems. Nat Phys 8, 32–39 (2011). · DOI · Paper page
- P Holme, BJ Kim, Vertex overload breakdown in evolving networks. Phys Rev E 65, 066109 (2002). · DOI · Paper page
- SV Buldyrev, R Parshani, G Paul, HE Stanley, S Havlin, Catastrophic cascade of failures in interdependent networks. Nature 464, 1025–1028 (2010). · DOI · Paper page
- A-L Barabási, R Albert, Emergence of scaling in random networks. Science 286, 509–512 (1999). · DOI · Paper page
- SN Dorogovtsev, JFF Mendes, AN Samukhin, Structure of growing networks with preferential linking. Phys Rev Lett 85, 4633–4636 (2000). · DOI · Paper page
- P Erdős, A Rényi, On the evolution of random graphs. Inst Hung Acad Sci 5, 17–61 (1960).
- R Cohen, K Erez, D Ben-Avraham, S Havlin, Breakdown of the internet under intentional attack. Phys Rev Lett 86, 3682–3685 (2001). · DOI · Paper page
- CM Schneider, AA Moreira, JS Andrade, S Havlin, HJ Herrmann, Mitigation of malicious attacks on networks. Proc Natl Acad Sci USA 108, 3838–3841 (2011). · DOI · Paper page
- LK Gallos, Attack Strategies on Complex Networks (Springer, Berlin), pp. 1048–1055 (2006).
- A Braunstein, L Dall’Asta, G Semerjian, L Zdeborová, Network dismantling. Proc Natl Acad Sci USA 113, 12368–12373 (2016). · DOI · Paper page
- F Morone, HA Makse, Influence maximization in complex networks through optimal percolation. Nature 524, 65–68 (2015). · DOI · Paper page
- L Zdeborová, P Zhang, H-J Zhou, Fast and simple decycling and dismantling of networks. Sci Rep 6, 37954 (2016). · DOI · Paper page
- S Mugisha, H-J Zhou, Identifying optimal targets of network attack by belief propagation. Phys Rev E 94, 012305 (2016). · DOI · Paper page
- F Morone, B Min, L Bo, R Mari, HA Makse, Collective influence algorithm to find influencers via optimal percolation in massively large social media. Sci Rep 6, 30062 (2016). · DOI · Paper page
- L Tian, A Bashan, D-N Shi, Y-Y Liu, Articulation points in complex networks. Nat Commun 8, 14223 (2017). · DOI
- H-J Zhou, Spin glass approach to the feedback vertex set problem. Eur Phys J B 86, 455 (2013). · DOI
- A Patron, R Cohen, D Li, S Havlin, Optimal cost for strengthening or destroying a given network. Phys Rev E 95, 052305 (2017). · DOI
- X-L Ren, N Gleinig, D Tolić, N Antulov-Fantulin, Underestimated cost of targeted attacks on complex networks. Complexity 2018, 1–15 (2018). · DOI
- L Lü, , Vital nodes identification in complex networks. Phys Rep 650, 1–63 (2016). · DOI · Paper page
- D Tolić, K-K Kleineberg, N Antulov-Fantulin, Simulating SIR processes on networks using weighted shortest paths. Sci Rep 8, 6562 (2018). · DOI
- R Bar-Yehuda, S Even, A linear-time approximation algorithm for the weighted vertex cover problem. J Algorithms 2, 198–203 (1981). · DOI · Paper page
- U Feige, MT Hajiaghayi, JR Lee, Improved approximation algorithms for minimum weight vertex separators. SIAM J Comput 38, 629–657 (2008). · doi:10.1137/05064299x
- M Fiedler, Algebraic connectivity of graphs. Czechoslovak Math J 23, 298–305 (1973). · DOI · Paper page
- S Guattery, GL Miller, On the quality of spectral separators. SIAM J Matrix Anal Appl 19, 701–719 (1998). · DOI
- A Buluç, H Meyerhenke, I Safro, P Sanders, C Schulz Recent Advances in Graph Partitioning (Springer International Publishing, Cham, Switzerland), pp. 117–158 (2016).
- PAC Duijn, V Kashirin, PMA Sloot, The relative ineffectiveness of criminal network disruption. Sci Rep 4, 4238 (2014). · DOI · Paper page
- S Janson, A Thomason, Dismantling sparse random graphs. Combin Probab Comput 17, 259–264 (2008). · DOI
- MA Riolo, MEJ Newman, First-principles multiway spectral partitioning of graphs. J Complex Networks 2, 121–140 (2014). · doi:10.1093/comnet/cnt021
- P Alex, HD Simon, K-P Liou, Partitioning sparse matrices with eigenvectors of graphs. SIAM J Matrix Anal Appl 11, 430–452 (1990). · DOI · Paper page
- J Kunegis, KONECT–The Koblenz network collection. Proceedings of International Conference on World Wide Web Companion, ed D Schwabe (ACM, New York), pp. 1343–1350 (2013).
- HV Ribeiro, LGA Alves, AF Martins, EK Lenzi, M Perc, The dynamical structure of political corruption networks. J Complex Networks 6, 989–1003 (2018). · DOI
- Y Chen, G Paul, S Havlin, S Liljeros, HE Stanley, Finding a better immunization strategy. Phys Rev Lett 101, 58701 (2008). · DOI · Paper page
Cited by
Robustness and resilience of complex networks
Artime, O., Grassia, M., De Domenico, M., Gleeson, J. P., Makse, H. A., Mangioni, G., Perc, M., & Radicchi, F. (2024) · Nature Reviews Physics · doi:10.1038/s42254-023-00676-y · Cited by 672
Finding key players in complex networks through deep reinforcement learning
Fan, C., Zeng, L., Sun, Y., & Liu, Y.-Y. (2020) · Nature Machine Intelligence · doi:10.1038/s42256-020-0177-2 · Cited by 425
Coordinated inauthentic behavior and information spreading on twitter
Cinelli, M., Cresci, S., Quattrociocchi, W., Tesconi, M., & Zola, P. (2022) · Decision Support Systems · doi:10.1016/j.dss.2022.113819 · Cited by 74
Mitigation of cascading failures in complex networks
Smolyak, A., Levy, O., Vodenska, I., Buldyrev, S., & Havlin, S. (2020) · Scientific Reports · doi:10.1038/s41598-020-72771-4 · Cited by 67
Metadata
- Authors
- Ren, X.-L., Gleinig, N., Helbing, D., & Antulov-Fantulin, N.
- Venue
- Proceedings of the National Academy of Sciences
- Published
- 2019-03-15
- Volume
- 116
- Issue
- 14
- Pages
- 6554-6559
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W2782195772
- Cited by
- 219
- References
- 9
- FWCI
- 9.03
- Type
- journal article
- Language
- en
- Open access
- hybrid
- Funders
- EC | Horizon 2020 Framework Programme (654024, 641191)
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Generalized network dismantling. https://app.cochat.ai/papers/10.1073/pnas.1806108116
- The paper
- Ren, X.-L., Gleinig, N., Helbing, D., & Antulov-Fantulin, N. (2019). Generalized network dismantling. Proceedings of the National Academy of Sciences. https://doi.org/10.1073/pnas.1806108116
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.