Block matrix formulations for evolving networks

Caterina Fenu, Desmond J. Higham

Research output: Contribution to journalArticle

3 Citations (Scopus)

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.
LanguageEnglish
Pages343-360
Number of pages18
JournalSIAM Journal on Matrix Analysis and Applications
Volume38
Issue number2
DOIs
Publication statusPublished - 2 May 2017

Fingerprint

Block Matrix
Formulation
Centrality
Cross product
Matrix Product
Adjacency Matrix
Sparsity
Slice
Numerical Algorithms
Pairwise
Discrete-time
High-dimensional
Computing
Vertex of a graph
Interaction
Modeling

Keywords

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

Cite this

Fenu, Caterina ; Higham, Desmond J. / Block matrix formulations for evolving networks. In: SIAM Journal on Matrix Analysis and Applications. 2017 ; Vol. 38, No. 2. pp. 343-360.
@article{8e0ad59e22c548dda39cb49481289d73,
title = "Block matrix formulations for evolving networks",
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.",
keywords = "centrality, complex network, evolving network, graph, tensor, pairwise interactions",
author = "Caterina Fenu and Higham, {Desmond J.}",
year = "2017",
month = "5",
day = "2",
doi = "10.1137/16M1076988",
language = "English",
volume = "38",
pages = "343--360",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
number = "2",

}

Block matrix formulations for evolving networks. / Fenu, Caterina; Higham, Desmond J.

In: SIAM Journal on Matrix Analysis and Applications, Vol. 38, No. 2, 02.05.2017, p. 343-360.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Block matrix formulations for evolving networks

AU - Fenu, Caterina

AU - Higham, Desmond J.

PY - 2017/5/2

Y1 - 2017/5/2

N2 - 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.

AB - 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.

KW - centrality

KW - complex network

KW - evolving network

KW - graph

KW - tensor

KW - pairwise interactions

UR - https://arxiv.org/abs/1511.07305

U2 - 10.1137/16M1076988

DO - 10.1137/16M1076988

M3 - Article

VL - 38

SP - 343

EP - 360

JO - SIAM Journal on Matrix Analysis and Applications

T2 - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 2

ER -