Speaker
Description
In complex network analysis it is crucial to investigate the alteration of network structures that results from the targeted removal of vertices or edges, ranked by a centrality measure [3]. Unfortunately, a sequential recalculation of centralities after each node elimination is often impractical for large networks, and using the ranking before the removal often does not approximate accurately the actual scenario.
In [2] we propose a first result on the computational complexity of the sequential approach when considering percolation on a complex network using some centrality measures based on matrix functions [1]. 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 using the same approach as [4].
We will also present an attempt to approximate updating of some centrality measures based on matrix functions to extend our proposal in [2].
[1] M. Benzi and P. Boito, Matrix Functions in Network Analysis. GAMM-Mitteilungen, 2020.
[2] D. Bertaccini and A. Filippo, A proposal for ranking through selective computation of centrality measures, 2023, in revisione.
[3] E. Estrada, The Structure of Complex Networks: Theory and Applications, Oxford University Press, 2011.
[4] S. Iyer, T. Killingback, B. Sundaram and Z. Wang, Attack Robustness and Centrality of Complex Networks, PLOS ONE, 2013.
