Maximum Core Spanning Tree Insertion Maintenance for Large Dynamic Graphs

The Maximum Core Spanning Tree (MCST) is a representative cohesive structure generated based on k-core, which is the maximum edge weight spanning tree indicating the “staired coreness hierarchy” in each connected component. The edge weight here is defined as \(w_{uv} = \min \{core(u), core(v)\}\) , and core(x) is the corness of vertex x. Unlike the insertion maintenance problem of Maximum Spanning Tree (MST) which has known efficient algorithms, MCST insertion maintenance raises special challenges, which is mainly due to the cascaded vertex coreness changes after single-edge insertion. In this paper, we show a series of properties of MCST and MCST insertion maintenance problem and propose a LoopFree algorithm to maintain the MCST efficiently. In particular, the time complexity for MCST maintenance for edge insertion is bounded by \(O(|E^*|+|V|)\) , where \(E^*\) is the edge set whose edge weight changes after insertion. Through extensive evaluations, we show the proposed MCST insertion maintenance algorithm has good efficiency on real-world datasets.