---
title: "Dynamic Seed-GrowthCM: A Dynamic Benefit-Oriented Algorithm for Core Maximization on Large Graphs"
authors:
  - "Dongyuan Ma"
  - "Dongxiao He"
  - "Xin Huang"
doi: "10.24963/ijcai.2025/352"
url: "https://ijcai.org/proceedings/2025/352"
pdf: "https://ijcai.org/proceedings/2025/0352.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "3162-3170"
track: "Main Track"
keywords:
  - "Data Mining: DM: Networks"
  - "Data Mining: DM: Big data and scalability"
  - "Data Mining: DM: Mining graphs"
---

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

Dongyuan Ma, Dongxiao He, Xin Huang

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 3162-3170. DOI: [10.24963/ijcai.2025/352](https://doi.org/10.24963/ijcai.2025/352)

## 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.