Department of Mathematics, University of Rome Tor Vergata, Rome, Italy.
PLoS One. 2023 Sep 18;18(9):e0289488. doi: 10.1371/journal.pone.0289488. eCollection 2023.
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.
在复杂网络分析中，研究由于目标顶点或边的删除而导致的网络结构变化至关重要，这些变化可以通过中心性度量来排名。不幸的是，对于大型网络来说，对每个节点删除后重新计算中心性通常是不切实际的，而仅在开始时计算排名往往不能准确反映实际情况。在这里，我们提出了一个关于根据基于矩阵函数的某些中心性度量从网络中删除节点时顺序方法的计算复杂性的初步结果。此外，我们提出了两种策略，旨在减少顺序计算中心性的计算影响，并提供理论支持。最后，我们将我们的主张应用于一些合成和真实网络的鲁棒性。
