Dynamic Seed-GrowthCM: A Dynamic Benefit-Oriented Algorithm for Core Maximization on Large Graphs

Abstract

The k-core has garnered significant attention in recent research as an effective measure of node importance within a graph. A k-core is defined as the maximal induced subgraph where each node has a degree of at least k. This paper addresses the core maximization problem: given a graph G, an integer k, and a budget b, the objective is to insert b new distinct edges into G to maximize the size of its k-core. This problem is theoretically proven to be NP-hard and APX-hard. However, the existing heuristic methods often struggle to achieve a good balance between efficiency and answer quality. In this paper, we propose a novel dynamic approach that, for the first time, uncovers the dynamic changes in node degrees. We introduce a new concept using the contribution of edges across different λ-shell components to the final solution. Based on these findings, we present the Dynamic Seed-GrowthCM method. This method selects the λ-shell component with the largest estimated benefit as the initial seed. In each iteration, depending on complete/partial growth, either a new seed is incorporated into the solution, or an existing seed undergoes growth, becoming a larger seed by adding connected components of the λ-shell component to the solution. Experimental results on ten datasets demonstrate that our algorithm significantly outperforms state-of-the-art methods in terms of solution quality on large graphs, while achieving a high computational efficiency.