Propagation-Based Temporal Network Summarization
| Autor: | Yao Zhang, B. Aditya Prakash, Aditya Bharadwaj, Sorour E. Amiri, Bijaya Adhikari |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Theoretical computer science
Computer science Event (computing) 02 engineering and technology Automatic summarization Computer Science Applications Set (abstract data type) Computational Theory and Mathematics 020204 information systems Scalability 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Algorithm design Representation (mathematics) Information Systems Network analysis |
| Zdroj: | IEEE Transactions on Knowledge and Data Engineering. 30:729-742 |
| ISSN: | 1041-4347 |
| Popis: | 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 system-matrix 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|