Updating Katz centrality by counting walks

Tools

Arrigo, Francesca and Bertaccini, Daniele and Filippo, Alessandro (2025) Updating Katz centrality by counting walks. SIAM Journal on Matrix Analysis and Applications, 46 (4). 2449 - 2474. ISSN 0895-4798 (https://doi.org/10.1137/24M1713995)

[thumbnail of Arrigo-etal-SIAM-JMAA-2025-Updating-Katz-centrality-by-counting-walks]
Preview
 Text. Filename: Arrigo-etal-SIAM-JMAA-2025-Updating-Katz-centrality-by-counting-walks.pdf
Accepted Author Manuscript
License: Creative Commons Attribution 4.0 logo
Download (2MB)| Preview

Abstract

We develop efficient and effective strategies for the update of Katz centralities after node and edge removal in simple graphs. We provide explicit formulas for the “loss of walks” a network suffers when nodes/edges are removed, and use these to inform our algorithms. The theory builds on the newly introduced concept of F-avoiding first-passage walks. Further, bounds on the change of total network communicability are also derived. Extensive numerical experiments on synthetic and real-world networks complement our theoretical results.

ORCID iDs

Arrigo, Francesca ORCID logoORCID: https://orcid.org/0000-0001-5473-7284, Bertaccini, Daniele and Filippo, Alessandro;
CORE (COnnecting REpositories)