Block matrix formulations for evolving networks

Tools

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)