Discovering and Maintaining the Best k in Core Decomposition

The mode of <tex-math notation="LaTeX">k</tex-math> -core and its hierarchical decomposition have been applied in many areas, such as sociology, the world wide web, and biology. Algorithms on related studies often need an input value of parameter <tex-math notation="LaTeX">k</tex-math> , while there is no existing solution other than manual selection. In this paper, given a graph and a scoring metric, we aim to find the best value of <tex-math notation="LaTeX">k</tex-math> such that the score of the <tex-math notation="LaTeX">k</tex-math> -core (or <tex-math notation="LaTeX">k</tex-math> -core set) is the highest. The problem is challenging because there are various community scoring metrics and the computation is costly on large datasets. With the well-designed vertex ordering, we propose time-and-space-optimal algorithms to compute the best <tex-math notation="LaTeX">k</tex-math> , which are applicable to most community metrics. As real-world networks are often fast-evolving, we also design a novel framework to maintain the best <tex-math notation="LaTeX">k</tex-math> -core (set) against graph dynamics. We prove the dynamic algorithms are bounded, i.e., the update cost is decided by the changes of input and output. The proposed algorithms can benefit the solutions to <tex-math notation="LaTeX">k</tex-math> -core-related problems and their dynamic counterparts. Extensive experiments are conducted on 10 real-world networks with size up to billion-scale, which validates the efficiency of our algorithms and the effectiveness of the resulting <tex-math notation="LaTeX">k</tex-math> -cores.