Comparative evaluation of strategies for improving the robustness of complex networks
Abstract 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 pa...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2023-07-01
|
| Series: | Applied Network Science |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s41109-023-00569-0 |
| _version_ | 1797774374381551616 |
|---|---|
| author | Annalisa Socievole Clara Pizzuti |
| author_facet | Annalisa Socievole Clara Pizzuti |
| author_sort | Annalisa Socievole |
| collection | DOAJ |
| description | Abstract 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–Penrose 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. |
| first_indexed | 2024-03-12T22:19:08Z |
| format | Article |
| id | doaj.art-bb2544b66dc74008afc423a012dba778 |
| institution | Directory Open Access Journal |
| issn | 2364-8228 |
| language | English |
| last_indexed | 2024-03-12T22:19:08Z |
| publishDate | 2023-07-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Applied Network Science |
| spelling | doaj.art-bb2544b66dc74008afc423a012dba7782023-07-23T11:09:21ZengSpringerOpenApplied Network Science2364-82282023-07-018112210.1007/s41109-023-00569-0Comparative evaluation of strategies for improving the robustness of complex networksAnnalisa Socievole0Clara Pizzuti1Institute for High Performance Computing and Networking (ICAR), National Research Council of Italy (CNR)Institute for High Performance Computing and Networking (ICAR), National Research Council of Italy (CNR)Abstract 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–Penrose 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.https://doi.org/10.1007/s41109-023-00569-0Effective graph resistanceRobustnessoptimisationMoore–Penrose pseudoinverseGraph spectrumGenetic algorithms |
| spellingShingle | Annalisa Socievole Clara Pizzuti Comparative evaluation of strategies for improving the robustness of complex networks Applied Network Science Effective graph resistance Robustness optimisation Moore–Penrose pseudoinverse Graph spectrum Genetic algorithms |
| title | Comparative evaluation of strategies for improving the robustness of complex networks |
| title_full | Comparative evaluation of strategies for improving the robustness of complex networks |
| title_fullStr | Comparative evaluation of strategies for improving the robustness of complex networks |
| title_full_unstemmed | Comparative evaluation of strategies for improving the robustness of complex networks |
| title_short | Comparative evaluation of strategies for improving the robustness of complex networks |
| title_sort | comparative evaluation of strategies for improving the robustness of complex networks |
| topic | Effective graph resistance Robustness optimisation Moore–Penrose pseudoinverse Graph spectrum Genetic algorithms |
| url | https://doi.org/10.1007/s41109-023-00569-0 |
| work_keys_str_mv | AT annalisasocievole comparativeevaluationofstrategiesforimprovingtherobustnessofcomplexnetworks AT clarapizzuti comparativeevaluationofstrategiesforimprovingtherobustnessofcomplexnetworks |