Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB
A k-core of a graph is a maximal connected subgraph in which every vertex is connected to at least k vertices in the subgraph. k-core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction, visualization, and solving NP-Hard problems on real networks efficiently, like maximal clique finding. In many real-world applications, networks change over time. As a result, it is essential to develop efficient incremental algorithms for streaming graph data. In this paper, we propose the first incremental k-core decomposition algorithms for streaming graph data. These algorithms locate a small subgraph that is guaranteed to contain the list of vertices whose maximum k-core values have to be updated, and efficiently process this subgraph to update the k-core decomposition. Our results show a significant reduction in run-time compared to non-incremental alternatives. We show the efficiency of our algorithms on different types of real and synthetic graphs, at different scales. For a graph of 16 million vertices, we observe speedups reaching a million times, relative to the non-incremental algorithms. © 2013 VLDB Endowment.
Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB
Michael D. Moffitt
ICCAD 2009
Rajeev Gupta, Shourya Roy, et al.
ICAC 2006
Michael Ray, Yves C. Martin
Proceedings of SPIE - The International Society for Optical Engineering