A proposal for ranking through selective computation of centrality measures

Daniele Bertaccini and Alessandro Filippo

PLOS ONE, 2023, vol. 18, issue 9, 1-16

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.

Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0289488 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 89488&type=printable (application/pdf)

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:plo:pone00:0289488

DOI: 10.1371/journal.pone.0289488

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().