Speaker
Description
Katz centrality is one of the most widely used indices in network science to determine the relative influence of a node within a network. Its unique feature is that it can be expressed as the solution of the (typically sparse) linear system $(I- \alpha A) \mathbf{x} = \mathbf{1}$, where $A$ is the adjacency matrix of the underlying graph and $\alpha>0$ is a dumping parameter such that $\alpha \rho(A)<1$, making it computable using broadly available and efficient linear algebra methods. However, repeated calculation of the measure can still be challenging in practical applications, in which simulating the sequential removal of a set of nodes/edges is often used to study issues related to network robustness and communication bottlenecks. For large networks, it may be unfeasible to recompute the vector of centrality scores after each elimination, so it is rather useful to devise updating strategies instead.
In this talk, we will provide explicit formulas that characterise the loss of walks that the network faces and, consequently, how Katz centrality is affected when a set of edges (resp., nodes) is removed from the network. Then, we will use these formulas to derive efficient and effective strategies for approximately updating the vector of Katz centrality, significantly reducing the computational burden of recomputing it repeatedly from scratch. We will also show bounds on the modifications of the induced total network communicability.
- F. Arrigo, D. Bertaccini, A. Filippo, Updating Katz centrality by counting walks. Submitted.
- M. Benzi, C. Klymko. Total communicability as a centrality measure. Journal of Complex Networks (2013), no. 1, 124–149.
- L. Katz, A new status index derived from sociometric analysis, Psychometrika, 18 (1953), 765 pp. 39–43.
