Incremental <Emphasis Type="Italic">k</Emphasis>-core decomposition: algorithms and evaluation |
| |
Authors: | Ahmet Erdem Sar?yüce Bu?ra Gedik Gabriela Jacques-Silva Kun-Lung Wu Ümit V Çatalyürek |
| |
Affiliation: | 1.Sandia National Labs,Livermore,USA;2.Bilkent University,Ankara,Turkey;3.IBM T.J. Watson Research Center,Yorktown Heights,USA;4.The Ohio State University,Columbus,USA |
| |
Abstract: | 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 dynamic graph data. In this paper, we propose a suite of incremental k-core decomposition algorithms for dynamic graph data. These algorithms locate a small subgraph that is guaranteed to contain the list of vertices whose maximum k-core values have changed and efficiently process this subgraph to update the k-core decomposition. We present incremental algorithms for both insertion and deletion operations, and propose auxiliary vertex state maintenance techniques that can further accelerate these operations. Our results show a significant reduction in runtime compared to non-incremental alternatives. We illustrate the efficiency of our algorithms on different types of real and synthetic graphs, at varying scales. For a graph of 16 million vertices, we observe relative throughputs reaching a million times, relative to the non-incremental algorithms. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|