Vanni Noferini

We discuss efficient computation of [Formula: see text]-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.

We propose a versatile approach to address a large family of matrix nearness problems, possibly with additional linear constraints. Our method is based on splitting a matrix nearness problem into two nested optimization problems, of which the inner one can be solved either exactly or cheaply, while the outer one can be recast as an unconstrained optimization task over a smooth real Riemannian manifold. We observe that this paradigm applies to many matrix nearness problems of practical interest appearing in the literature, thus revealing that they are equivalent in this sense to a Riemannian optimization problem. We also show that the objective function to be minimized on the Riemannian manifold can be discontinuous, thus requiring regularization techniques, and we give conditions for this to happen. Finally, we demonstrate the practical applicability of our method by implementing it for a number of matrix nearness problems that are relevant for applications and are currently considered very demanding in practice. Extensive numerical experiments demonstrate that our method often greatly outperforms its predecessors, including algorithms specifically designed for those particular problems.