Efficient Core Maintenance of Dynamic Graphs

\(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.