Sparse matrix computations for dynamic network centrality

Francesca Arrigo, Desmond J. Higham

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Time sliced networks describing human-human digital interactions are typically large and sparse. This is the case, for example, with pairwise connectivity describing social media, voice call or physical proximity, when measured over seconds, minutes or hours. However, if we wish to quantify and compare the overall time-dependent centrality of the network nodes, then we should account for the global flow of information through time. Because the time-dependent edge structure typically allows information to diffuse widely around the network, a natural summary of sparse but dynamic pairwise interactions will generally take the form of a large dense matrix. For this reason, computing nodal centralities for a timedependent network can be extremely expensive in terms of both computation and storage; much more so than for a single, static network. In this work, we focus on the case of dynamic communicability, which leads to broadcast and receive centrality measures. We derive a new algorithm for computing time-dependent centrality that works with a sparsified version of the dynamic communicability matrix. In this way, the computation and storage requirements are reduced to those of a sparse, static network at each time point. The new algorithm is justified from first principles and then tested on a large scale data set. We find that even with very stringent sparsity requirements (retaining no more than ten times the number of nonzeros in the individual time slices), the algorithm accurately reproduces the list of highly central nodes given by the underlying full system. This allows us to capture centrality over time with a minimal level of storage and with a cost that scales only linearly with the number of time points. We also describe and test three variants of the proposed algorithm that require fewer parameters and achieve a further reduction in the computational cost.
LanguageEnglish
Article number17
Number of pages19
JournalApplied Network Science
Volume2
DOIs
Publication statusPublished - 24 Jun 2017

Fingerprint

Matrix Computation
Centrality
Dynamic Networks
Sparse matrix
Pairwise
Social Media
Computing
Requirements
First-principles
Vertex of a graph
Sparsity
Interaction
Slice
Broadcast
Proximity
Computational Cost
Connectivity
Quantify
Linearly
Costs

Keywords

  • dynamic networks
  • sparsification
  • centrality
  • Katz centrality
  • social network analysis
  • dynamic communicability
  • time-dependent centrality
  • sparsity requirements

Cite this

@article{387090366068423aa7ba6b359f28240f,
title = "Sparse matrix computations for dynamic network centrality",
abstract = "Time sliced networks describing human-human digital interactions are typically large and sparse. This is the case, for example, with pairwise connectivity describing social media, voice call or physical proximity, when measured over seconds, minutes or hours. However, if we wish to quantify and compare the overall time-dependent centrality of the network nodes, then we should account for the global flow of information through time. Because the time-dependent edge structure typically allows information to diffuse widely around the network, a natural summary of sparse but dynamic pairwise interactions will generally take the form of a large dense matrix. For this reason, computing nodal centralities for a timedependent network can be extremely expensive in terms of both computation and storage; much more so than for a single, static network. In this work, we focus on the case of dynamic communicability, which leads to broadcast and receive centrality measures. We derive a new algorithm for computing time-dependent centrality that works with a sparsified version of the dynamic communicability matrix. In this way, the computation and storage requirements are reduced to those of a sparse, static network at each time point. The new algorithm is justified from first principles and then tested on a large scale data set. We find that even with very stringent sparsity requirements (retaining no more than ten times the number of nonzeros in the individual time slices), the algorithm accurately reproduces the list of highly central nodes given by the underlying full system. This allows us to capture centrality over time with a minimal level of storage and with a cost that scales only linearly with the number of time points. We also describe and test three variants of the proposed algorithm that require fewer parameters and achieve a further reduction in the computational cost.",
keywords = "dynamic networks, sparsification, centrality, Katz centrality, social network analysis, dynamic communicability, time-dependent centrality, sparsity requirements",
author = "Francesca Arrigo and Higham, {Desmond J.}",
year = "2017",
month = "6",
day = "24",
doi = "10.1007/s41109-017-0038-z",
language = "English",
volume = "2",
journal = "Applied Network Science",
issn = "2364-8228",

}

Sparse matrix computations for dynamic network centrality. / Arrigo, Francesca; Higham, Desmond J.

In: Applied Network Science, Vol. 2, 17, 24.06.2017.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Sparse matrix computations for dynamic network centrality

AU - Arrigo, Francesca

AU - Higham, Desmond J.

PY - 2017/6/24

Y1 - 2017/6/24

N2 - Time sliced networks describing human-human digital interactions are typically large and sparse. This is the case, for example, with pairwise connectivity describing social media, voice call or physical proximity, when measured over seconds, minutes or hours. However, if we wish to quantify and compare the overall time-dependent centrality of the network nodes, then we should account for the global flow of information through time. Because the time-dependent edge structure typically allows information to diffuse widely around the network, a natural summary of sparse but dynamic pairwise interactions will generally take the form of a large dense matrix. For this reason, computing nodal centralities for a timedependent network can be extremely expensive in terms of both computation and storage; much more so than for a single, static network. In this work, we focus on the case of dynamic communicability, which leads to broadcast and receive centrality measures. We derive a new algorithm for computing time-dependent centrality that works with a sparsified version of the dynamic communicability matrix. In this way, the computation and storage requirements are reduced to those of a sparse, static network at each time point. The new algorithm is justified from first principles and then tested on a large scale data set. We find that even with very stringent sparsity requirements (retaining no more than ten times the number of nonzeros in the individual time slices), the algorithm accurately reproduces the list of highly central nodes given by the underlying full system. This allows us to capture centrality over time with a minimal level of storage and with a cost that scales only linearly with the number of time points. We also describe and test three variants of the proposed algorithm that require fewer parameters and achieve a further reduction in the computational cost.

AB - Time sliced networks describing human-human digital interactions are typically large and sparse. This is the case, for example, with pairwise connectivity describing social media, voice call or physical proximity, when measured over seconds, minutes or hours. However, if we wish to quantify and compare the overall time-dependent centrality of the network nodes, then we should account for the global flow of information through time. Because the time-dependent edge structure typically allows information to diffuse widely around the network, a natural summary of sparse but dynamic pairwise interactions will generally take the form of a large dense matrix. For this reason, computing nodal centralities for a timedependent network can be extremely expensive in terms of both computation and storage; much more so than for a single, static network. In this work, we focus on the case of dynamic communicability, which leads to broadcast and receive centrality measures. We derive a new algorithm for computing time-dependent centrality that works with a sparsified version of the dynamic communicability matrix. In this way, the computation and storage requirements are reduced to those of a sparse, static network at each time point. The new algorithm is justified from first principles and then tested on a large scale data set. We find that even with very stringent sparsity requirements (retaining no more than ten times the number of nonzeros in the individual time slices), the algorithm accurately reproduces the list of highly central nodes given by the underlying full system. This allows us to capture centrality over time with a minimal level of storage and with a cost that scales only linearly with the number of time points. We also describe and test three variants of the proposed algorithm that require fewer parameters and achieve a further reduction in the computational cost.

KW - dynamic networks

KW - sparsification

KW - centrality

KW - Katz centrality

KW - social network analysis

KW - dynamic communicability

KW - time-dependent centrality

KW - sparsity requirements

UR - https://appliednetsci.springeropen.com/

U2 - 10.1007/s41109-017-0038-z

DO - 10.1007/s41109-017-0038-z

M3 - Article

VL - 2

JO - Applied Network Science

T2 - Applied Network Science

JF - Applied Network Science

SN - 2364-8228

M1 - 17

ER -