Random Walks-Based Node Centralities to Attack Complex Networks

Massimiliano Turchetto, Michele Bellingeri (), Roberto Alfieri, Ngoc-Kim-Khanh Nguyen, Quang Nguyen and Davide Cassi
Additional contact information
Massimiliano Turchetto: Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma, via G.P. Usberti, 7/a, 43124 Parma, Italy
Michele Bellingeri: Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma, via G.P. Usberti, 7/a, 43124 Parma, Italy
Roberto Alfieri: Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma, via G.P. Usberti, 7/a, 43124 Parma, Italy
Ngoc-Kim-Khanh Nguyen: Faculty of Basic Science, Van Lang University, Ho Chi Minh City 70000, Vietnam
Quang Nguyen: Department of Physics, International University, Linh Trung, Thu Duc, Ho Chi Minh City 720400, Vietnam
Davide Cassi: Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma, via G.P. Usberti, 7/a, 43124 Parma, Italy

Mathematics, 2023, vol. 11, issue 23, 1-20

Abstract: 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.

Keywords: real-world networks; node centrality; random walk processes; network robustness; network random walks (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/23/4827/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/23/4827/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:23:p:4827-:d:1291084

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().