Block matrix formulations for evolving networks

Fenu, Caterina and Higham, Desmond J. (2017) Block matrix formulations for evolving networks. SIAM Journal on Matrix Analysis and Applications, 38 (2). pp. 343-360. ISSN 0895-4798

[img]
Preview
Text (Fenu-Higham-SIAM-JMAA-2017-BLock-matrix-formulations-for-evolving)
Fenu_Higham_SIAM_JMAA_2017_BLock_matrix_formulations_for_evolving.pdf
Accepted Author Manuscript

Download (659kB)| Preview

    Abstract

    Many types of pairwise interactions take the form of a fixed set of nodes with edges that appear and disappear over time. In the case of discrete-time evolution, the resulting evolving network may be represented by a time-ordered sequence of adjacency matrices. We consider here the issue of representing the system as a single, higher-dimensional block matrix, built from the individual time slices. We focus on the task of computing network centrality measures. From a modeling perspective, we show that there is a suitable block formulation that allows us to recover dynamic centrality measures respecting time's arrow. From a computational perspective, we show that the new block formulation leads to the design of more effective numerical algorithms. In particular, we describe matrix-vector product based algorithms that exploit sparsity. Results are given on realistic data sets.