{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T04:41:39Z","timestamp":1689741699736},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T00:00:00Z","timestamp":1689638400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T00:00:00Z","timestamp":1689638400000},"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":["Appl Netw Sci"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Designing network systems able to sustain functionality after random failures or targeted attacks is a crucial aspect of networks. This paper investigates several strategies of link selection aiming at enhancing the robustness of a network by optimizing the effective graph resistance. In particular, we study the problem of optimizing this measure through two different strategies: the addition of a non-existing link to the network and the protection of an existing link whose removal would result in a severe network compromise. For each strategy, we exploit a genetic algorithm as optimization technique, and a computationally efficient technique based on the Moore\u2013Penrose pseudoinverse matrix of the Laplacian of a graph for approximating the effective graph resistance. We compare these strategies to other state-of-the art methods over both real-world and synthetic networks finding that our proposals provide a higher speedup, especially on large networks, and results closer to those provided by the exhaustive search.<\/jats:p>","DOI":"10.1007\/s41109-023-00569-0","type":"journal-article","created":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T14:02:02Z","timestamp":1689688922000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Comparative evaluation of strategies for improving the robustness of complex networks"],"prefix":"10.1007","volume":"8","author":[{"given":"Annalisa","family":"Socievole","sequence":"first","affiliation":[]},{"given":"Clara","family":"Pizzuti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,18]]},"reference":[{"key":"569_CR1","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 A-L (2000) Error and attack tolerance of complex networks. Nature 406:378\u2013381","journal-title":"Nature"},{"issue":"1","key":"569_CR2","first-page":"1","volume":"97","author":"T B\u00e4ck","year":"1997","unstructured":"B\u00e4ck T, Fogel DB, Michalewicz Z (1997) Handbook of evolutionary computation. Release 97(1):1","journal-title":"Release"},{"key":"569_CR3","volume-title":"Network science","author":"A-L Barab\u00e1si","year":"2016","unstructured":"Barab\u00e1si A-L, P\u00f3sfai M (2016) Network science. Cambridge University Press, Cambridge"},{"key":"569_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2020.05.004","volume":"874","author":"F Battiston","year":"2020","unstructured":"Battiston F, Cencetti G, Iacopini I, Latora V, Lucas M, Patania A, Young J, Petri G (2020) Networks beyond pairwise interactions: structure and dynamics. Phys Rep 874:1\u201392","journal-title":"Phys Rep"},{"issue":"3\u20134","key":"569_CR5","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/j.physa.2005.03.040","volume":"357","author":"A Beygelzimer","year":"2005","unstructured":"Beygelzimer A, Grinstein G, Linsker R, Rish I (2005) Improving network robustness by edge modification. Physica A Stat Mech Appl 357(3\u20134):593\u2013612","journal-title":"Physica A Stat Mech Appl"},{"key":"569_CR6","doi-asserted-by":"crossref","unstructured":"Buesser P, Daolio F, Tomassini M (2011) Optimizing the robustness of scale-free networks with simulated annealing. In: International conference on adaptive and natural computing algorithms. Springer, pp 167\u2013176","DOI":"10.1007\/978-3-642-20267-4_18"},{"key":"569_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s40649-019-0073-2","volume":"6","author":"V Carchiolo","year":"2019","unstructured":"Carchiolo V, Grassia M, Longheu A, Malgeri M, Mangioni G (2019) Network robustness improvement via long-range links. Comput Soc Netw 6:1\u201316","journal-title":"Comput Soc Netw"},{"key":"569_CR8","unstructured":"Ellens W, Kooij RE (2013) Graph measures and network robustness. arXiv preprint arXiv:1311.5064"},{"issue":"10","key":"569_CR9","doi-asserted-by":"publisher","first-page":"2491","DOI":"10.1016\/j.laa.2011.02.024","volume":"435","author":"W Ellens","year":"2011","unstructured":"Ellens W, Spieksm FM, Mieghem PV, Jamakovic A, Kooij RE (2011) Effective graph resistance. Linear Algebra Appl 435(10):2491\u20132506","journal-title":"Linear Algebra Appl"},{"issue":"2","key":"569_CR10","doi-asserted-by":"publisher","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M Fiedler","year":"1973","unstructured":"Fiedler M (1973) Algebraic connectivity of graphs. Czechoslov Math J 23(2):298\u2013305","journal-title":"Czechoslov Math J"},{"key":"569_CR11","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3163672","author":"S Freitas","year":"2022","unstructured":"Freitas S, Yang D, Kumar S, Tong H, Chau DH (2022) Graph vulnerability and robustness: a survey. IEEE Trans Knowl Data Eng. https:\/\/doi.org\/10.1109\/TKDE.2022.3163672","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"1","key":"569_CR12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1137\/050645452","volume":"50","author":"A Ghosh","year":"2008","unstructured":"Ghosh A, Boyd S, Saberi A (2008) Minimizing effective resistance of a graph. SIAM Rev 50(1):37\u201366","journal-title":"SIAM Rev"},{"key":"569_CR13","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci USA 99:7821\u20137826","journal-title":"Proc Natl Acad Sci USA"},{"key":"569_CR14","volume-title":"Genetic algorithms in search, optimization and machine learning","author":"DE Goldberg","year":"1989","unstructured":"Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley Longman Publishing Co., Inc., Boston"},{"issue":"01","key":"569_CR15","doi-asserted-by":"publisher","first-page":"01027","DOI":"10.1088\/1742-5468\/2011\/01\/P01027","volume":"2011","author":"HJ Herrmann","year":"2011","unstructured":"Herrmann HJ, Schneider CM, Moreira AA, Andrade JS Jr, Havlin S (2011) Onion-like network topology enhances robustness against malicious attacks. J Stat Mech Theory Exp 2011(01):01027","journal-title":"J Stat Mech Theory Exp"},{"key":"569_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2019.123586","volume":"545","author":"Y Kazawa","year":"2020","unstructured":"Kazawa Y, Tsugawa S (2020) Effectiveness of link-addition strategies for improving the robustness of both multiplex and interdependent networks. Physica A Stat Mech Appl 545:123586","journal-title":"Physica A Stat Mech Appl"},{"key":"569_CR17","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF01164627","volume":"12","author":"DJ Klein","year":"1993","unstructured":"Klein DJ, Randi\u0107 M (1993) Resistance distance. J Math Chem 12:81\u201395","journal-title":"J Math Chem"},{"issue":"2","key":"569_CR18","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1093\/comnet\/cnt010","volume":"1","author":"VH Louzada","year":"2013","unstructured":"Louzada VH, Daolio F, Herrmann HJ, Tomassini M (2013) Smart rewiring for network robustness. J Complex Netw 1(2):150\u2013159","journal-title":"J Complex Netw"},{"key":"569_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2016.06.007","volume":"650","author":"L Lu","year":"2016","unstructured":"Lu L, Chen D, Ren X-L, Zhang Q-M, Zhang Y-C, Zhou T (2016) Vital nodes identification in complex networks. Phys Rep 650:1\u201363","journal-title":"Phys Rep"},{"key":"569_CR20","unstructured":"Mieghem PV, Doerr C, Wang H, Hernandez JM, Hutchison D, Karaliopoulos M, Kooijt R (2010) A framework for computing topological network robustness. Delft University of Technology, Report 20101218"},{"issue":"8","key":"569_CR21","doi-asserted-by":"publisher","first-page":"895","DOI":"10.3390\/math9080895","volume":"9","author":"M Oehlers","year":"2021","unstructured":"Oehlers M, Fabian B (2021) Graph metrics for network robustness\u2014a survey. Mathematics 9(8):895","journal-title":"Mathematics"},{"key":"569_CR22","doi-asserted-by":"crossref","unstructured":"Pizzuti C, Socievole A (2018) A genetic algorithm for improving robustness of complex networks. In: Tsoukalas LH, Gr\u00e9goire \u00c9, Alamaniotis M (eds) IEEE 30th international conference on tools with artificial intelligence, ICTAI 2018, 5\u20137 November 2018. Greece, Volos, pp 514\u2013521","DOI":"10.1109\/ICTAI.2018.00085"},{"key":"569_CR23","doi-asserted-by":"crossref","unstructured":"Pizzuti C, Socievole A (2019) A genetic algorithm for enhancing the robustness of complex networks through link protection. In: Complex networks and their applications VII: Volume 1 proceedings the 7th international conference on complex networks and their applications COMPLEX NETWORKS 2018 7. Springer, pp 807\u2013819","DOI":"10.1007\/978-3-030-05411-3_64"},{"key":"569_CR24","doi-asserted-by":"crossref","unstructured":"Pizzuti C, Socievole A (2023) Incremental computation of effective graph resistance for improving robustness of complex networks: a comparative study. In: Complex networks and their applications XI: proceedings of the eleventh international conference on complex networks and their applications: COMPLEX NETWORKS 2022, vol 2. Springer, pp 419\u2013431","DOI":"10.1007\/978-3-031-21131-7_33"},{"key":"569_CR25","doi-asserted-by":"crossref","unstructured":"Ranjan G, Zhang Z, Boley D (2014) Incremental computation of pseudo-inverse of Laplacian. In: Combinatorial optimization and applications. COCOA. Springer, Switzerland, pp 730\u2013749","DOI":"10.1007\/978-3-319-12691-3_54"},{"issue":"10","key":"569_CR26","doi-asserted-by":"publisher","first-page":"3838","DOI":"10.1073\/pnas.1009440108","volume":"108","author":"CM Schneider","year":"2011","unstructured":"Schneider CM, Moreira AA, Andrade JS Jr, Havlin S, Herrmann HJ (2011) Mitigation of malicious attacks on networks. Proc Natl Acad Sci 108(10):3838\u20133841","journal-title":"Proc Natl Acad Sci"},{"key":"569_CR27","doi-asserted-by":"crossref","unstructured":"Tizghadam A, Leon-Garcia A (2008) On robust traffic engineering in core networks. In: IEEE global telecommunications conference,GLOBECOM 2008, pp 1\u20136","DOI":"10.1109\/GLOCOM.2008.ECP.456"},{"key":"569_CR28","volume-title":"Graph spectra for complex networks","author":"P Van Mieghem","year":"2011","unstructured":"Van Mieghem P (2011) Graph spectra for complex networks. Cambridge University Press, New York"},{"key":"569_CR29","doi-asserted-by":"crossref","unstructured":"Wang S, Liu J (2017) Enhancing the robustness of complex networks against edge-based-attack cascading failures. In: 2017 IEEE congress on evolutionary computation (CEC). IEEE, pp 23\u201328","DOI":"10.1109\/CEC.2017.7969291"},{"issue":"9","key":"569_CR30","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1140\/epjb\/e2014-50276-0","volume":"87","author":"X Wang","year":"2014","unstructured":"Wang X, Pournaras E, Kooij RE, Van Mieghem P (2014) Improving robustness of complex networks via the effective graph resistance. Eur Phys J B 87(9):221","journal-title":"Eur Phys J B"},{"key":"569_CR31","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.physa.2014.05.002","volume":"410","author":"M Zhou","year":"2014","unstructured":"Zhou M, Liu J (2014) A memetic algorithm for enhancing the robustness of scale-free networks against malicious attacks. Physica A Stat Mech Appl 410:131\u2013143","journal-title":"Physica A Stat Mech Appl"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00569-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-023-00569-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00569-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T14:13:27Z","timestamp":1689689607000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-023-00569-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,18]]},"references-count":31,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["569"],"URL":"https:\/\/doi.org\/10.1007\/s41109-023-00569-0","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,18]]},"assertion":[{"value":"27 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Both authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"43"}}