Logo image
Back
Propagation-Based Temporal Network Summarization
Journal article

Propagation-Based Temporal Network Summarization

Bijaya Adhikari, Yao Zhang, Sorour E Amiri, Aditya Bharadwaj and B. Aditya Prakash
IEEE transactions on knowledge and data engineering, Vol.30(4), pp.729-742
04/01/2018
DOI: 10.1109/TKDE.2017.2776282

View Online

Abstract

Modern networks are very large in size and also evolve with time. As their sizes grow, the complexity of performing network analysis grows as well. Getting a smaller representation of a temporal network with similar properties will help in various data mining tasks. In this paper, we study the novel problem of getting a smaller diffusion-equivalent representation of a set of time-evolving networks. We first formulate a well-founded and general temporal-network condensation problem based on the so-called systemmatrix of the network. We then propose NETCONDENSE, a scalable and effective algorithm which solves this problem using careful transformations in sub-quadratic running time, and linear space complexities. Our extensive experiments show that we can reduce the size of large real temporal networks (from multiple domains such as social, co-authorship, and email) significantly without much loss of information. We also show the wide-applicability of NETCONDENSE by leveraging it for several tasks: for example, we use it to understand, explore, and visualize the original datasets and to also speed-up algorithms for the influence-maximization and event detection problems on temporal networks.
 Algorithm design and analysis Eigenvalues and eigenfunctions Event detection graph mining Graph summarization Heuristic algorithms Integrated circuit modeling propagation Silicon temporal networks

Details

Metrics

9 Record Views
12 Times Cited - Web of Science
Logo image