Title: Efficient Core Maintenance of Dynamic Graphs
Authors: Wen Bai, Yuxiao Zhang, Xuezheng Liu, Min Chen and Di Wu
Abstract: k-core is one type of cohesive subgraphs such that every vertex has at least k degree within the graph. It is widely used in many graph mining tasks, including but not limited to community detection, graph visualization and clique finding. Frequently decomposing a dynamic graph to get its k-cores brings expensive cost since k-cores evolve as the dynamic graph changes. To address this problem, previous studies proposed several maintenance solutions to update k-cores based on a single inserted (removed) edge. Unlike previous studies, we maintain affected k-cores from the sparsest to the densest, so the cost of our method is determined by the largest core number of a graph. Experimental results show that our approach can significantly outperform the previous algorithms up to 3 order of magnitude for real graphs tested.
