The Critical Node Detection Problem (CNDP) consists in finding the set of nodes, defined critical, whose removal maximally degrades the graph. In this work we focus on finding the set of critical nodes whose removal minimizes the pairwise connectivity of a direct graph (digraph). Such problem has been proved to be NP-hard, thus we need efficient heuristics to detect critical nodes in real-world applications. We aim at understanding which is the best heuristic we can apply to identify critical nodes in practice, i.e., taking into account time constrains and real-world networks. We present an in-depth analysis of several heuristics we ran on both real-world and on synthetic graphs. We define and evaluate two different strategies for each heuristic: standard and iterative. Our main findings show that an algorithm recently proposed to solve the CNDP and that can be used as heuristic for the general case provides the best results in real-world graphs, and it is also the fastest. However, there are few exceptions that are thoroughly analyzed and discussed. We show that among the heuristics we analyzed, few of them cannot be applied to very large graphs, when the iterative strategy is used, due to their time complexity. Finally, we suggest possible directions to further improve the heuristic providing the best results.

Seeking critical nodes in digraphs / Bernaschi, Massimo; Celestini, A.; Cianfriglia, M.; Guarino, Stefano; Italiano, Giuseppe Francesco; Mastrostefano, E.; Zastrow, L. R.. - In: JOURNAL OF COMPUTATIONAL SCIENCE. - ISSN 1877-7503. - 69:(2023), pp. 1-12. [10.1016/j.jocs.2023.102012]

Seeking critical nodes in digraphs

Bernaschi M.;Guarino S.;Italiano G. F.;
2023

Abstract

The Critical Node Detection Problem (CNDP) consists in finding the set of nodes, defined critical, whose removal maximally degrades the graph. In this work we focus on finding the set of critical nodes whose removal minimizes the pairwise connectivity of a direct graph (digraph). Such problem has been proved to be NP-hard, thus we need efficient heuristics to detect critical nodes in real-world applications. We aim at understanding which is the best heuristic we can apply to identify critical nodes in practice, i.e., taking into account time constrains and real-world networks. We present an in-depth analysis of several heuristics we ran on both real-world and on synthetic graphs. We define and evaluate two different strategies for each heuristic: standard and iterative. Our main findings show that an algorithm recently proposed to solve the CNDP and that can be used as heuristic for the general case provides the best results in real-world graphs, and it is also the fastest. However, there are few exceptions that are thoroughly analyzed and discussed. We show that among the heuristics we analyzed, few of them cannot be applied to very large graphs, when the iterative strategy is used, due to their time complexity. Finally, we suggest possible directions to further improve the heuristic providing the best results.
2023
Critical nodes, Networks connectivity, Centrality measures, Network analysis
Seeking critical nodes in digraphs / Bernaschi, Massimo; Celestini, A.; Cianfriglia, M.; Guarino, Stefano; Italiano, Giuseppe Francesco; Mastrostefano, E.; Zastrow, L. R.. - In: JOURNAL OF COMPUTATIONAL SCIENCE. - ISSN 1877-7503. - 69:(2023), pp. 1-12. [10.1016/j.jocs.2023.102012]
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S1877750323000728-main.pdf

Open Access

Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 3.33 MB
Formato Adobe PDF
3.33 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/11385/235498
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact