Block matrix formulations for evolving networks

Caterina Fenu, Desmond J. Higham

Research output: Contribution to journalArticle

4 Citations (Scopus)
38 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)343-360
Number of pages18
JournalSIAM Journal on Matrix Analysis and Applications
Volume38
Issue number2
DOIs
Publication statusPublished - 2 May 2017

Keywords

  • centrality
  • complex network
  • evolving network
  • graph
  • tensor
  • pairwise interactions

Cite this