Random Walks-Based Node Centralities to Attack Complex Networks
Investigating the network response to node removal and the efficacy of the node removal strategies is fundamental to network science. Different research studies have proposed many node centralities based on the network structure for ranking nodes to remove. The random walk (RW) on networks describes...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-11-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/23/4827 |
| _version_ | 1827592259173875712 |
|---|---|
| author | Massimiliano Turchetto Michele Bellingeri Roberto Alfieri Ngoc-Kim-Khanh Nguyen Quang Nguyen Davide Cassi |
| author_facet | Massimiliano Turchetto Michele Bellingeri Roberto Alfieri Ngoc-Kim-Khanh Nguyen Quang Nguyen Davide Cassi |
| author_sort | Massimiliano Turchetto |
| collection | DOAJ |
| description | Investigating the network response to node removal and the efficacy of the node removal strategies is fundamental to network science. Different research studies have proposed many node centralities based on the network structure for ranking nodes to remove. The random walk (RW) on networks describes a stochastic process in which a walker travels among nodes. RW can be a model of transport, diffusion, and search on networks and is an essential tool for studying the importance of network nodes. In this manuscript, we propose four new measures of node centrality based on RW. Then, we compare the efficacy of the new RW node centralities for network dismantling with effective node removal strategies from the literature, namely betweenness, closeness, degree, and k-shell node removal, for synthetic and real-world networks. We evaluate the dismantling of the network by using the size of the largest connected component (LCC). We find that the degree nodes attack is the best strategy overall, and the new node removal strategies based on RW show the highest efficacy in regard to peculiar network topology. Specifically, RW strategy based on covering time emerges as the most effective strategy for a synthetic lattice network and a real-world road network. Our results may help researchers select the best node attack strategies in a specific network class and build more robust network structures. |
| first_indexed | 2024-03-09T01:47:09Z |
| format | Article |
| id | doaj.art-9e654c49665e47c2827d2e0a7ce9e825 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T01:47:09Z |
| publishDate | 2023-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-9e654c49665e47c2827d2e0a7ce9e8252023-12-08T15:21:52ZengMDPI AGMathematics2227-73902023-11-011123482710.3390/math11234827Random Walks-Based Node Centralities to Attack Complex NetworksMassimiliano Turchetto0Michele Bellingeri1Roberto Alfieri2Ngoc-Kim-Khanh Nguyen3Quang Nguyen4Davide Cassi5Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma, via G.P. Usberti, 7/a, 43124 Parma, ItalyDipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma, via G.P. Usberti, 7/a, 43124 Parma, ItalyDipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma, via G.P. Usberti, 7/a, 43124 Parma, ItalyFaculty of Basic Science, Van Lang University, Ho Chi Minh City 70000, VietnamDepartment of Physics, International University, Linh Trung, Thu Duc, Ho Chi Minh City 720400, VietnamDipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma, via G.P. Usberti, 7/a, 43124 Parma, ItalyInvestigating the network response to node removal and the efficacy of the node removal strategies is fundamental to network science. Different research studies have proposed many node centralities based on the network structure for ranking nodes to remove. The random walk (RW) on networks describes a stochastic process in which a walker travels among nodes. RW can be a model of transport, diffusion, and search on networks and is an essential tool for studying the importance of network nodes. In this manuscript, we propose four new measures of node centrality based on RW. Then, we compare the efficacy of the new RW node centralities for network dismantling with effective node removal strategies from the literature, namely betweenness, closeness, degree, and k-shell node removal, for synthetic and real-world networks. We evaluate the dismantling of the network by using the size of the largest connected component (LCC). We find that the degree nodes attack is the best strategy overall, and the new node removal strategies based on RW show the highest efficacy in regard to peculiar network topology. Specifically, RW strategy based on covering time emerges as the most effective strategy for a synthetic lattice network and a real-world road network. Our results may help researchers select the best node attack strategies in a specific network class and build more robust network structures.https://www.mdpi.com/2227-7390/11/23/4827real-world networksnode centralityrandom walk processesnetwork robustnessnetwork random walks |
| spellingShingle | Massimiliano Turchetto Michele Bellingeri Roberto Alfieri Ngoc-Kim-Khanh Nguyen Quang Nguyen Davide Cassi Random Walks-Based Node Centralities to Attack Complex Networks Mathematics real-world networks node centrality random walk processes network robustness network random walks |
| title | Random Walks-Based Node Centralities to Attack Complex Networks |
| title_full | Random Walks-Based Node Centralities to Attack Complex Networks |
| title_fullStr | Random Walks-Based Node Centralities to Attack Complex Networks |
| title_full_unstemmed | Random Walks-Based Node Centralities to Attack Complex Networks |
| title_short | Random Walks-Based Node Centralities to Attack Complex Networks |
| title_sort | random walks based node centralities to attack complex networks |
| topic | real-world networks node centrality random walk processes network robustness network random walks |
| url | https://www.mdpi.com/2227-7390/11/23/4827 |
| work_keys_str_mv | AT massimilianoturchetto randomwalksbasednodecentralitiestoattackcomplexnetworks AT michelebellingeri randomwalksbasednodecentralitiestoattackcomplexnetworks AT robertoalfieri randomwalksbasednodecentralitiestoattackcomplexnetworks AT ngockimkhanhnguyen randomwalksbasednodecentralitiestoattackcomplexnetworks AT quangnguyen randomwalksbasednodecentralitiestoattackcomplexnetworks AT davidecassi randomwalksbasednodecentralitiestoattackcomplexnetworks |