{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T20:59:25Z","timestamp":1760821165507},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,5,7]],"date-time":"2020-05-07T00:00:00Z","timestamp":1588809600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,7]],"date-time":"2020-05-07T00:00:00Z","timestamp":1588809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cloud Comp"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Understanding and improving the robustness of networks has significant applications in various areas, such as bioinformatics, transportation, critical infrastructures, and social networks. Recently, there has been a large amount of work on network dismantling, which focuses on removing an optimal set of nodes to break the network into small components with sub-extensive sizes. However, in our experiments, we found these state-of-the-art methods, although seemingly different, utilize the same refinement technique, namely reinsertion, to improve the performance. Despite being mentioned with understatement, the technique essentially plays the key role in the final performance. Without reinsertion, the current best method would deteriorate worse than the simplest heuristic ones; while with reinsertion, even the random removal strategy achieves on par with the best results. As a consequence, we, for the first time, systematically revisit the power of reinsertion in network dismantling problems. We re-implemented and compared 10 heuristic and approximate competing methods on both synthetic networks generated by four classical network models, and 18 real-world networks which cover seven different domains with varying scales. The comprehensive ablation results show that: i) HBA (High Betweenness Adaption, no reinsertion) is the most effective network dismantling strategy, however, it can only be applicable in small scale networks; ii) HDA (High Degree Adaption, with reinsertion) achieves the best balance between effectiveness and efficiency; iii) The reinsertion techniques help improve the performance for most current methods; iv) The one, which adds back the node based on that it joins the clusters minimizing the multiply of both numbers and sizes, is the most effective reinsertion strategy for most methods. Our results can be a survey reference to help further understand the current methods and thereafter design the better ones.<\/jats:p>","DOI":"10.1186\/s13677-020-00169-8","type":"journal-article","created":{"date-parts":[[2020,5,7]],"date-time":"2020-05-07T10:02:57Z","timestamp":1588845777000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Revisiting the power of reinsertion for optimal targets of network attack"],"prefix":"10.1186","volume":"9","author":[{"given":"Changjun","family":"Fan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li","family":"Zeng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanghe","family":"Feng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baoxin","family":"Xiu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jincai","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhong","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,5,7]]},"reference":[{"issue":"1","key":"169_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert R, Barab\u00e1si AL (2002) Statistical mechanics of complex networks. Rev Mod Phys 74(1):47.","journal-title":"Rev Mod Phys"},{"issue":"6794","key":"169_CR2","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1038\/35019019","volume":"406","author":"R Albert","year":"2000","unstructured":"Albert R, Jeong H, Barab\u00e1si AL (2000) Error and attack tolerance of complex networks. Nature 406(6794):378.","journal-title":"Nature"},{"issue":"5439","key":"169_CR3","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509\u2013512.","journal-title":"Science"},{"issue":"6","key":"169_CR4","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1121\/1.1906679","volume":"22","author":"A Bavelas","year":"1950","unstructured":"Bavelas A (1950) Communication patterns in task-oriented groups. J Acoust Soc Am 22(6):725\u2013730.","journal-title":"J Acoust Soc Am"},{"issue":"44","key":"169_CR5","doi-asserted-by":"publisher","first-page":"12,368","DOI":"10.1073\/pnas.1605083113","volume":"113","author":"A Braunstein","year":"2016","unstructured":"Braunstein A, Dall\u2019Asta L, Semerjian G, Zdeborov\u00e1 L (2016) Network dismantling. Proc Natl Acad Sci 113(44):12,368\u201312,373.","journal-title":"Proc Natl Acad Sci"},{"issue":"1-7","key":"169_CR6","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","volume":"30","author":"S Brin","year":"1998","unstructured":"Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw ISDN Syst 30(1-7):107\u2013117.","journal-title":"Comput Netw ISDN Syst"},{"issue":"16","key":"169_CR7","doi-asserted-by":"publisher","first-page":"3682","DOI":"10.1103\/PhysRevLett.86.3682","volume":"86","author":"R Cohen","year":"2001","unstructured":"Cohen R, Erez K, Ben-Avraham D, Havlin S (2001) Breakdown of the internet under intentional attack. Phys Rev Lett 86(16):3682.","journal-title":"Phys Rev Lett"},{"key":"169_CR8","doi-asserted-by":"crossref","unstructured":"ERDdS P R&wi (1959) On random graphs i. Publ Math Debrecen 6:290\u2013297.","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"169_CR9","doi-asserted-by":"crossref","unstructured":"Fan C, Xiao K, Xiu B, Lv G (2014) A fuzzy clustering algorithm to detect criminals without prior information In: Proceedings of the 2014 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, 238\u2013243.. IEEE Press.","DOI":"10.1109\/ASONAM.2014.6921590"},{"key":"169_CR10","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1016\/j.physa.2016.11.097","volume":"469","author":"C Fan","year":"2017","unstructured":"Fan C, Liu Z, Lu X, Xiu B, Chen Q (2017) An efficient link prediction index for complex military organization. Phys A Stat Mech Appl 469:572\u2013587.","journal-title":"Phys A Stat Mech Appl"},{"key":"169_CR11","doi-asserted-by":"crossref","unstructured":"Fan C, Zeng L, Ding Y, Chen M, Sun Y, Liu Z (2019) Learning to identify high betweenness centrality nodes from scratch: A novel graph neural network approach In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management, 559\u2013568.","DOI":"10.1145\/3357384.3357979"},{"key":"169_CR12","doi-asserted-by":"crossref","unstructured":"Freeman LC (1977) A set of measures of centrality based on betweenness. Sociometry: 35\u201341.","DOI":"10.2307\/3033543"},{"issue":"2","key":"169_CR13","doi-asserted-by":"publisher","first-page":"026,107","DOI":"10.1103\/PhysRevE.65.026107","volume":"65","author":"P Holme","year":"2002","unstructured":"Holme P, Kim BJ (2002) Growing scale-free networks with tunable clustering. Phys Rev E 65(2):026,107.","journal-title":"Phys Rev E"},{"issue":"5","key":"169_CR14","doi-asserted-by":"publisher","first-page":"056,109","DOI":"10.1103\/PhysRevE.65.056109","volume":"65","author":"P Holme","year":"2002","unstructured":"Holme P, Kim BJ, Yoon CN, Han SK (2002) Attack vulnerability of complex networks. Phys Rev E 65(5):056,109.","journal-title":"Phys Rev E"},{"key":"169_CR15","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg J, Tardos \u00c9 (2003) Maximizing the spread of influence through a social network In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 137\u2013146.. ACM.","DOI":"10.1145\/956750.956769"},{"key":"169_CR16","doi-asserted-by":"crossref","unstructured":"Kunegis J (2013) Konect: the koblenz network collection In: Proceedings of the 22nd International Conference on World Wide Web, 1343\u20131350.. ACM.","DOI":"10.1145\/2487788.2488173"},{"key":"169_CR17","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.cosrev.2018.02.002","volume":"28","author":"M Lalou","year":"2018","unstructured":"Lalou M, Tahraoui MA, Kheddouci H (2018) The critical node detection problem in networks: a survey. Comput Sci Rev 28:92\u2013117.","journal-title":"Comput Sci Rev"},{"key":"169_CR18","unstructured":"Leskovec J, Krevl A (2014) SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data."},{"issue":"1","key":"169_CR19","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1217299.1217301","volume":"1","author":"J Leskovec","year":"2007","unstructured":"Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: Densification and shrinking diameters. ACM Trans Knowl Discov Data (TKDD) 1(1):2.","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"issue":"1","key":"169_CR20","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J Leskovec","year":"2009","unstructured":"Leskovec J, Lang KJ, Dasgupta A, Mahoney MW (2009) Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29\u2013123.","journal-title":"Internet Math"},{"issue":"7563","key":"169_CR21","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1038\/nature14604","volume":"524","author":"F Morone","year":"2015","unstructured":"Morone F, Makse HA (2015) Influence maximization in complex networks through optimal percolation. Nature 524(7563):65.","journal-title":"Nature"},{"issue":"1","key":"169_CR22","doi-asserted-by":"publisher","first-page":"012,305","DOI":"10.1103\/PhysRevE.94.012305","volume":"94","author":"S Mugisha","year":"2016","unstructured":"Mugisha S, Zhou HJ (2016) Identifying optimal targets of network attack by belief propagation. Phys Rev E 94(1):012,305.","journal-title":"Phys Rev E"},{"issue":"14","key":"169_CR23","doi-asserted-by":"publisher","first-page":"3200","DOI":"10.1103\/PhysRevLett.86.3200","volume":"86","author":"R Pastor-Satorras","year":"2001","unstructured":"Pastor-Satorras R, Vespignani A (2001) Epidemic spreading in scale-free networks. Phys Rev Lett 86(14):3200.","journal-title":"Phys Rev Lett"},{"key":"169_CR24","doi-asserted-by":"crossref","unstructured":"Ren XL, Gleinig N, Helbing D, Antulov-Fantulin N (2018) Generalized network dismantling. arXiv preprint arXiv:180101357.","DOI":"10.1155\/2018\/9826243"},{"issue":"14","key":"169_CR25","doi-asserted-by":"publisher","first-page":"6554","DOI":"10.1073\/pnas.1806108116","volume":"116","author":"XL Ren","year":"2019","unstructured":"Ren XL, Gleinig N, Helbing D, Antulov-Fantulin N (2019) Generalized network dismantling. Proc Natl Acade Sci 116(14):6554\u20136559.","journal-title":"Proc Natl Acade Sci"},{"issue":"6","key":"169_CR26","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1093\/comnet\/cny002","volume":"6","author":"HV Ribeiro","year":"2018","unstructured":"Ribeiro HV, Alves LG, Martins AF, Lenzi EK, Perc M (2018) The dynamical structure of political corruption networks. J Complex Netw 6(6):989\u20131003.","journal-title":"J Complex Netw"},{"issue":"4","key":"169_CR27","doi-asserted-by":"publisher","first-page":"46,002","DOI":"10.1209\/0295-5075\/98\/46002","volume":"98","author":"CM Schneider","year":"2012","unstructured":"Schneider CM, Mihaljev T, Herrmann HJ (2012) Inverse targeting\u2014an effective immunization strategy. EPL (Europhys Lett) 98(4):46,002.","journal-title":"EPL (Europhys Lett)"},{"issue":"4","key":"169_CR28","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","volume":"17","author":"U Von Luxburg","year":"2007","unstructured":"Von Luxburg U (2007) A tutorial on spectral clustering. Stat Comput 17(4):395\u2013416.","journal-title":"Stat Comput"},{"issue":"1","key":"169_CR29","doi-asserted-by":"publisher","first-page":"13,513","DOI":"10.1038\/s41598-018-31902-8","volume":"8","author":"S Wandelt","year":"2018","unstructured":"Wandelt S, Sun X, Feng D, Zanin M, Havlin S (2018) A comparative analysis of approaches to network-dismantling. Sci Rep 8(1):13,513.","journal-title":"Sci Rep"},{"issue":"6684","key":"169_CR30","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts DJ, Strogatz SH (1998) Collective dynamics of \u2019small-world\u2019 networks. Nature 393(6684):440.","journal-title":"Nature"},{"key":"169_CR31","doi-asserted-by":"publisher","first-page":"37,954","DOI":"10.1038\/srep37954","volume":"6","author":"L Zdeborov\u00e1","year":"2016","unstructured":"Zdeborov\u00e1 L, Zhang P, Zhou HJ (2016) Fast and simple decycling and dismantling of networks. Sci Rep 6:37,954.","journal-title":"Sci Rep"}],"container-title":["Journal of Cloud Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13677-020-00169-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13677-020-00169-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13677-020-00169-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,30]],"date-time":"2023-09-30T20:07:13Z","timestamp":1696104433000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofcloudcomputing.springeropen.com\/articles\/10.1186\/s13677-020-00169-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,7]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["169"],"URL":"https:\/\/doi.org\/10.1186\/s13677-020-00169-8","relation":{},"ISSN":["2192-113X"],"issn-type":[{"value":"2192-113X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,7]]},"assertion":[{"value":"30 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"24"}}