In complex network analysis it is essential to investigate the alteration of network structures that results from the targeted removal of vertices or edges, ranked by centrality measures. Unfortunately, a sequential recalculation of centralities after each node elimination is often impractical for large networks, and computing rankings only at the beginning often does not accurately reflect the actual scenario. Here we propose a first result on the computational complexity of the sequential approach when nodes are removed from a network according to some centrality measures based on matrix functions. Moreover, we present two strategies that aim to reduce the computational impact of the sequential computation of centralities and provide theoretical results in support. Finally, we provide an application of our claims to the robustness of some synthetic and real-world networks.

Bertaccini, D., Filippo, A. (2023). A proposal for ranking through selective computation of centrality measures. PLOS ONE, 18(9) [10.1371/journal.pone.0289488].

A proposal for ranking through selective computation of centrality measures

Daniele Bertaccini
Methodology
;
Alessandro Filippo
Formal Analysis
2023-01-01

Abstract

In complex network analysis it is essential to investigate the alteration of network structures that results from the targeted removal of vertices or edges, ranked by centrality measures. Unfortunately, a sequential recalculation of centralities after each node elimination is often impractical for large networks, and computing rankings only at the beginning often does not accurately reflect the actual scenario. Here we propose a first result on the computational complexity of the sequential approach when nodes are removed from a network according to some centrality measures based on matrix functions. Moreover, we present two strategies that aim to reduce the computational impact of the sequential computation of centralities and provide theoretical results in support. Finally, we provide an application of our claims to the robustness of some synthetic and real-world networks.
2023
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore MAT/08
English
Con Impact Factor ISI
Other grants (D.B.) Indam-GNCS grant, https://www.altamatematica.it/gncs/, 824158, EU under the Horizon 2020 Project “Energy oriented Centre of Excellence: toward exascale for energy” (EoCoE–II)
Bertaccini, D., Filippo, A. (2023). A proposal for ranking through selective computation of centrality measures. PLOS ONE, 18(9) [10.1371/journal.pone.0289488].
Bertaccini, D; Filippo, A
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/345824
Citazioni
  • ???jsp.display-item.citation.pmc??? 0
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact