Preserving sparsity in dynamic network computation

Francesca Arrigo, Desmond J. Higham

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

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.
LanguageEnglish
Title of host publicationComplex Networks & Their Applications V
Subtitle of host publicationProceedings of the 5th International Workshop on Complex Networks and their Applications (COMPLEX NETWORKS 2016)
EditorsHocine Cherifi, Sabrina Gaito, Walter Quattrociocchi, Alessandra Sala
Place of PublicationCham
PublisherSpringer
Pages147-157
Number of pages11
Volume693
ISBN (Print)9783319509013
DOIs
Publication statusPublished - 30 Nov 2016
Event5th International Workshop on Complex Networks and their Applications - Sala Napoleonica di Palazzo Greppi, Milan, Italy
Duration: 30 Nov 20162 Dec 2016
http://complexnetworks.org/index2016.html

Publication series

NameStudies in Computational Intelligence
PublisherSpringer
Volume693
ISSN (Print)1860-949X

Conference

Conference5th International Workshop on Complex Networks and their Applications
Abbreviated titleComplex Networks 2016
CountryItaly
CityMilan
Period30/11/162/12/16
Internet address

Fingerprint

Costs

Keywords

  • time sliced networks
  • human-human digital interactions
  • dynamic communicability
  • time-dependent centrality
  • dynamic broadcast centrality
  • dynamic receive centrality

Cite this

Arrigo, F., & Higham, D. J. (2016). Preserving sparsity in dynamic network computation. In H. Cherifi, S. Gaito, W. Quattrociocchi, & A. Sala (Eds.), Complex Networks & Their Applications V: Proceedings of the 5th International Workshop on Complex Networks and their Applications (COMPLEX NETWORKS 2016) (Vol. 693, pp. 147-157). (Studies in Computational Intelligence; Vol. 693). Cham: Springer. https://doi.org/10.1007/978-3-319-50901-3_12
Arrigo, Francesca ; Higham, Desmond J. / Preserving sparsity in dynamic network computation. Complex Networks & Their Applications V: Proceedings of the 5th International Workshop on Complex Networks and their Applications (COMPLEX NETWORKS 2016). editor / Hocine Cherifi ; Sabrina Gaito ; Walter Quattrociocchi ; Alessandra Sala. Vol. 693 Cham : Springer, 2016. pp. 147-157 (Studies in Computational Intelligence).
@inproceedings{8e733d80557a4e4cb6ca93429d6478ef,
title = "Preserving sparsity in dynamic network computation",
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.",
keywords = "time sliced networks, human-human digital interactions, dynamic communicability, time-dependent centrality, dynamic broadcast centrality, dynamic receive centrality",
author = "Francesca Arrigo and Higham, {Desmond J.}",
year = "2016",
month = "11",
day = "30",
doi = "10.1007/978-3-319-50901-3_12",
language = "English",
isbn = "9783319509013",
volume = "693",
series = "Studies in Computational Intelligence",
publisher = "Springer",
pages = "147--157",
editor = "Hocine Cherifi and Sabrina Gaito and Walter Quattrociocchi and Alessandra Sala",
booktitle = "Complex Networks & Their Applications V",

}

Arrigo, F & Higham, DJ 2016, Preserving sparsity in dynamic network computation. in H Cherifi, S Gaito, W Quattrociocchi & A Sala (eds), Complex Networks & Their Applications V: Proceedings of the 5th International Workshop on Complex Networks and their Applications (COMPLEX NETWORKS 2016). vol. 693, Studies in Computational Intelligence, vol. 693, Springer, Cham, pp. 147-157, 5th International Workshop on Complex Networks and their Applications, Milan, Italy, 30/11/16. https://doi.org/10.1007/978-3-319-50901-3_12

Preserving sparsity in dynamic network computation. / Arrigo, Francesca; Higham, Desmond J.

Complex Networks & Their Applications V: Proceedings of the 5th International Workshop on Complex Networks and their Applications (COMPLEX NETWORKS 2016). ed. / Hocine Cherifi; Sabrina Gaito; Walter Quattrociocchi; Alessandra Sala. Vol. 693 Cham : Springer, 2016. p. 147-157 (Studies in Computational Intelligence; Vol. 693).

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

T1 - Preserving sparsity in dynamic network computation

AU - Arrigo, Francesca

AU - Higham, Desmond J.

PY - 2016/11/30

Y1 - 2016/11/30

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.

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.

KW - time sliced networks

KW - human-human digital interactions

KW - dynamic communicability

KW - time-dependent centrality

KW - dynamic broadcast centrality

KW - dynamic receive centrality

UR - http://www.springer.com/gp/book/9783319509006

U2 - 10.1007/978-3-319-50901-3_12

DO - 10.1007/978-3-319-50901-3_12

M3 - Conference contribution book

SN - 9783319509013

VL - 693

T3 - Studies in Computational Intelligence

SP - 147

EP - 157

BT - Complex Networks & Their Applications V

A2 - Cherifi, Hocine

A2 - Gaito, Sabrina

A2 - Quattrociocchi, Walter

A2 - Sala, Alessandra

PB - Springer

CY - Cham

ER -

Arrigo F, Higham DJ. Preserving sparsity in dynamic network computation. In Cherifi H, Gaito S, Quattrociocchi W, Sala A, editors, Complex Networks & Their Applications V: Proceedings of the 5th International Workshop on Complex Networks and their Applications (COMPLEX NETWORKS 2016). Vol. 693. Cham: Springer. 2016. p. 147-157. (Studies in Computational Intelligence). https://doi.org/10.1007/978-3-319-50901-3_12