Efficient Computation of ƒ-Centralities and Nonbacktracking Centrality for Temporal Networks

We discuss efficient computation of ƒ-centralities and nonbacktracking centralities for time-evolving networks with nonnegative weights. We present a node-level formula for its combinatorially exact computation which proves to be more tractable than previously existing formulae at edge-level for dense networks. Additionally, we investigate the impact of the {online updating of} such a time-evolving network, analyzing its effect on the resulting nonbacktracking Katz centrality. Finally, we demonstrate by means of computational experiments that the node-level formula presented is much more efficient for dense networks than the previously known edge-level formula. As a tool for our goals, in an appendix of the paper, we develop a spectral theory of matrices whose elements are vectors.