A proposal for ranking through selective computation of centrality measures

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 l...

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2023-09, Vol.18 (9), p.e0289488-e0289488
Main Authors: Bertaccini, Daniele, Filippo, Alessandro
Format: Article
Language:English
Subjects:
Analysis
Apexes
Biology and Life Sciences
Complexity
Computation
Computer and Information Sciences
Computer applications
Graph theory
Medicine and Health Sciences
Methods
Network analysis
Physical Sciences
Ranking and selection (Statistics)
Research and Analysis Methods
Social networks
Social Sciences
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0289488