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 (https://doi.org/10.1137/16M1076988)

[thumbnail of Fenu-Higham-SIAM-JMAA-2017-BLock-matrix-formulations-for-evolving]
Preview
 Text. Filename: 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.

ORCID iDs

Fenu, Caterina and Higham, Desmond J. ORCID logoORCID: https://orcid.org/0000-0002-6635-3461;
CORE (COnnecting REpositories)