Projects per year
Abstract
Time sliced networks describing humanhuman 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 timedependent centrality of the network nodes, then we should account for the global flow of information through time. Because the timedependent 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 timedependent 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.
Original language  English 

Title of host publication  Complex Networks & Their Applications V 
Subtitle of host publication  Proceedings of the 5th International Workshop on Complex Networks and their Applications (COMPLEX NETWORKS 2016) 
Editors  Hocine Cherifi, Sabrina Gaito, Walter Quattrociocchi, Alessandra Sala 
Place of Publication  Cham 
Publisher  Springer 
Pages  147157 
Number of pages  11 
Volume  693 
ISBN (Print)  9783319509013 
DOIs  
Publication status  Published  30 Nov 2016 
Event  5th International Workshop on Complex Networks and their Applications  Sala Napoleonica di Palazzo Greppi, Milan, Italy Duration: 30 Nov 2016 → 2 Dec 2016 http://complexnetworks.org/index2016.html 
Publication series
Name  Studies in Computational Intelligence 

Publisher  Springer 
Volume  693 
ISSN (Print)  1860949X 
Conference
Conference  5th International Workshop on Complex Networks and their Applications 

Abbreviated title  Complex Networks 2016 
Country/Territory  Italy 
City  Milan 
Period  30/11/16 → 2/12/16 
Internet address 
Keywords
 time sliced networks
 humanhuman digital interactions
 dynamic communicability
 timedependent centrality
 dynamic broadcast centrality
 dynamic receive centrality
Fingerprint
Dive into the research topics of 'Preserving sparsity in dynamic network computation'. Together they form a unique fingerprint.Projects
 1 Finished

Data Analytics for Future Cities
Higham, D.
EPSRC (Engineering and Physical Sciences Research Council)
1/01/15 → 31/12/19
Project: Research Fellowship