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

1 Introduction

The k-core of a graph is widely applied across multiple disciplines due to its ability to simplify the analysis of complex networks [Batagelj and Zaversnik, 2003]. Defined as the maximal induced subgraph where each vertex maintains at least k neighbors, k-core provides a clear view of the fundamental structure within networks [Seidman, 1983]. This characteristic renders k-core particularly useful in various applications such as social network analysis [Govind and Lal,

∗Corresponding authors.

2021; Li et al., 2018b], community detection [Malliaros et al., 2016], biological research [Guo et al., 2022], financial network analysis [Batagelj and Zaverˇsnik, 2011], and transportation systems [Bruckner et al., 2015]. Building on this foundation, the core maximization problem aims to maximize the size of the k-core by inserting a specified number of edges, a challenge that is recognized as NP-hard and APX-hard [Chitnis and Talmon, 2018; Malliaros et al., 2020; Zhou et al., 2019].

Motivation example. Consider a graph G with 13 vertices, as illustrated in Figure 1(a). The entire graph G forms a 1core where every vertex has at least one neighbor. The coreness of a vertex, indicated by the number next to its label in Figure 1, refers to the largest k such that the vertex belongs to the k-core of the graph. For instance, the coreness of v6 is 2. The 3-core includes four vertices: {v1, v2, v3, v4}.

Core maximization has numerous practical applications in real-world scenarios. In social network analysis, adding connections can enhance information spread, making marketing campaigns more effective [Li et al., 2018a; Aral and Walker, 2012]. In biology, strengthening protein-protein interaction networks helps discover key functional modules and drug targets [Yue et al., 2020]. In transportation networks, adding routes increases robustness, reduces congestion, and improves connectivity [Sarıy¨uce et al., 2016].

Challenges and Contributions. Core maximization is a challenging task due to its NP-hard and APX-hard nature and high computational complexity, which makes it difficult to solve efficiently [Zhou et al., 2019]. Early methods like EKC [Zhou et al., 2019] and VEK [Zhou et al., 2022] adopt a greedy edge insertion approach, inserting edges one by one to maximize the k-core size. EKC suffers from significant computational complexity, making it impractical for large graphs. VEK attempts to improve efficiency by using a vertex-oriented heuristic, but it still encounters performance bottlenecks. Later, FastCM/FastCM+ [Sun et al., 2022] improved upon these methods by partitioning the graph and adding nodes in groups, which provides greater flexibility. However, all of the above methods directly insert edges in each iteration, overlooking the changes in the degrees of the nodes in the current solution during each iteration, which reduces the number of edges that need to be inserted.

Example-1. Consider Figure 1(a), where k = 3 and b = 3. FastCM+ transforms the node set {v5, v6, v7, v8, v9} into a k-core in the first iteration, inserting the edges {(v6, v9), (v7, v8)}. However, when v10 and v11 are considered part of the solution, the degrees of v7 and v9 become 3, at which point no edge needs to be inserted that has one endpoint as v7 or v9.

These limitations motivate the need for a more adaptive solution. In this paper, we propose Dynamic SeedGrowthCM, which addresses the shortcomings of these existing approaches by dynamically adjusting the estimated benefit of each λ-shell component before each iteration using two strategies-complete growth and partial growth. Experimental results demonstrate that Dynamic Seed-GrowthCM outperforms state-of-the-art methods on a range of datasets. In summary, we make the main contributions in this paper as follows.

• We propose a novel algorithm, Dynamic SeedGrowthCM, which dynamically adjusts the estimated benefit of each λ-shell component in each iteration to effectively address the core maximization problem.
• We introduce two growth strategies-complete growth and partial growth-that enable a flexible approach to adding adjacent λ-shells, enhancing the adaptability of the solution.
• We conduct extensive experiments on multiple datasets, demonstrating that Dynamic Seed-GrowthCM significantly outperforms existing state-of-the-art methods in both solution quality and computational efficiency.

2 RelatedWork

K-Core Decomposition and Maintenance. K-core decomposition is a fundamental technique in network analysis that identifies cohesive subgraphs by iteratively removing nodes with fewer than k connections. Initially proposed by Seidman [Seidman, 1983], and later optimized by Batagelj and Zaverˇsnik [Batagelj and Zaversnik, 2003], this method efficiently analyzes large-scale networks. Streaming algorithms by Sarıy¨uce et al. [Sar´ıy¨uce et al., 2013] further enable kcore decomposition on dynamic graphs, allowing real-time updates. For parallel core maintenance, Hua et al. [Hua et al., 2019] and Jin et al. [Jin et al., 2018] developed faster approaches, improving the efficiency of updating k-core structures as graphs evolve. Zhang et al. [Zhang et al., 2017b] introduced an order-based core maintenance approach, accelerating the process by leveraging node sequence optimizations. Core maintenance on edge-weighted graphs has also been addressed by Liu and Zhang [Liu and Zhang, 2020], and Zhou et al. [Zhou et al., 2021], expanding its application to more complex networks.

To handle large dynamic graphs, Zhang et al. [Weng et al., 2021] developed distributed algorithms that efficiently distribute the workload across multiple processors, ensuring scalability. Additionally, Khaouid et al. [Khaouid et al., 2015] proposed a method for k-core decomposition on large networks using a single PC, while Bonchi et al. [Bonchi et al., 2019] extended the k-core concept to distancegeneralized cores. The anchored k-core problem, introduced by Bhawalkar et al. [Bhawalkar et al., 2015], stabilizes core structures by anchoring specific nodes, ensuring resilience even under node removal. A federated approach has also been proposed for secure distributed k-core decomposition [Guo et al., 2024].

Core Minimization and Maximization. Core minimization and maximization are critical approaches in network analysis, focusing on manipulating the k-core structure for various objectives.

In core minimization, the goal is to reduce the k-core size by weakening the connectivity. Zhu et al. [Zhu et al., 2018] proposed edge manipulation techniques to remove edges strategically, reducing the k-core and its influence in the network. Liu et al. [Liu et al., 2021] tackled the anchored k-core budget minimization problem, aiming to minimize the k-core size while maintaining core stability within a defined budget. Zhang et al. [Zhang et al., 2017a] addressed the collapsed k-core problem, focusing on the removal of critical users in social networks whose exit leads to a collapse of the k-core structure, weakening the network significantly.

In contrast, core maximization focuses on enhancing the k-core size. Laishram et al. [Laishram et al., 2020] introduced residual core maximization to increase network stability by expanding residual cores. Zhou et al. [Zhou et al., 2019] used an edge addition approach to achieve a similar goal, while Zhou et al. [Zhou et al., 2022] proposed a vertexoriented approach for edge k-core problems. Sun et al. [Sun et al., 2022] developed scalable algorithms to efficiently maximize the k-core in large graphs. Medya et al. [Medya et al., 2020] employed a game-theoretic approach to improve core resilience, while Laishram et al. [Laishram et al., 2018] explored ways to measure and enhance the resilience of k-core structures against node and edge removal.

3 Preliminaries

Consider an undirected and unweighted graph G = (V,E), where V is the set of vertices and E is the set of edges. Let n be the number of vertices and m be the number of edges, with the assumption that m ≥ n-1. For any subgraph S, the neighborhood of a vertex u is represented as N(u, S), and the degree of u in S, meaning the number of neighbors of u in S, is denoted as deg(u, S) = |N(u, S)|.

Definition 1 (k-core). Given a graph G, a subgraph S is the k-core of G, denoted by Ck(G), if: (i) ∀u ∈ S, deg(u, S) ≥ k; and (ii) ∄S′ ⊃ S that satisfies (i).

The k-core can be obtained by recursively removing every vertex with a degree less than k in the graph, with a time complexity of O(m) [Seidman, 1983]. This process reveals a hierarchical structure, where each node is associated with a λ-shell, representing the collection of nodes with the same coreness. The coreness of a node is determined by the largest k-core in which it exists.

Definition 2 (coreness). Given a graph G, the coreness of a vertex u, denoted by cn(u), is defined as the largest integer k such that u ∈ Ck(G) and u /∈ Ck+1(G).

Definition 3 (λ-shell). Given a graph G, a subgraph S is the λ-shell of G, denoted by Hλ(G), if: (i) ∀u ∈ S, cn(u) = λ; and (ii) ∄S′ ⊃ S that satisfies (i).

Based on the above definitions, we can formulate the problem of core maximization as follows.

Problem Statement. Given a graph G, an integer k, and a budget b, the core maximization problem aims to insert b new distinct edges into G to maximize the size of its k-core. The nodes that are converted into the k-core are referred to as kcore followers.

4 Dynamic Seed-GrowthCM

4.1 Method Overview

In this section, we introduce Dynamic Seed-GrowthCM, a novel approach to core maximization that emphasizes dynamic adaptation. It consists of four phases as follows.

• Phase-I: λ-Shell Partition. In this phase, the λ-shell is divided into several disjoint components. Each component serves as the smallest unit for conversion within our method, allowing for independent edge insertions aimed at core conversion.
• Phase-II: Initialization. In this phase, the estimated benefit of each λ-shell component is calculated and initialized. Estimated benefit measures the gain of converting a λ-shell component into part of the k-core.
• Phase-III: Iterative Dynamic Growth. In each iteration, we either select a new seed to add to the current solution or grow an existing seed-through either complete or partial growth. Then, the estimated benefit of all components is updated.
• Phase-IV: Offline Storage Phase. Given the predictable growth patterns of graphs, we store strategies offline based on common graph behaviors. When the same graph is encountered again, these pre-determined strategies are quickly retrieved and applied, enhancing efficiency and reducing the need for recalibration. This approach accelerates the core maximization process by instantly implementing effective strategies.

4.2 λ-Shell Partition

In processing large sparse graph data, the effective implementation of core maximization methods is crucial. The budget b for inserting edges is inherently much smaller than the potential edges, quantified as ∣∣∣ |V |×(|V |-1) 2 - |E|∣∣∣, emphasizing the need for an efficient search strategy to handle the vast difference. The hierarchical structure formed by λ-shells is an excellent choice for core maximization. However, since λ-shells are not necessarily connected, we employ λ-Shell Partition to divide them into several connected components, which better facilitates solution generation.

Definition 4 (λ-Shell Partition). The λ-Shell Partition divides Hλ(G) into its connected components, denoted as:

where each Ci is a connected component of Hλ(G), and satisfies:h⋃

Theorem 1 (Local Insertion Closure for λ-Shell Components). For any λ1-shell component C1 and λ2-shell component C2, an edge insertion (u, v) where u, v ∈ C1 will not change the coreness of any node in C2.

Proof. Assume that the coreness of w ∈ C2 has changed. Since no edges have been deleted in the graph, it is obviously true that cn(w) cannot decrease. If cn(w) increases to λ2+1, according to the k-core maintenance rules [Sar´ıy¨uce et al., 2013], by setting k = λ2 + 1, it implies that λ1 = λ2 and w is reachable from u or v via a path consisting of vertices with coreness λ2. This means that w ∈ C1 ∩ C2. However, this contradicts the definition of λ-shell components, as C1 and C2 are distinct, disconnected components. Therefore, the theorem holds.

4.3 Initialization

λ-threshold. We first analyze the structure of the λ-shell component and propose a new concept, the λ-threshold component, to identify the nodes that play an important role in the process of converting the λ-shell component into part of the k-core.

Since the λ-shell component has a local insertion closure, i.e., inserting edges in one component does not affect other components, we focus on considering how to completely convert the nodes in a component to part of the k-core. First, we provide the definition of the dynamic solution for k-core maximization and the dynamic degree of the node, allowing the node's degree to change with the solution, giving the node better adaptability.

Definition 5 (Dynamic Solution) Given a graph G, an integer k, and a budget b, the dynamic solution of the graph, denoted as V (k, b, i), represents the k-core obtained after the i-th iteration.

Definition 6 (Dynamic Degree) Given a graph G, an integer k, and a budget b, the dynamic degree of a node u, denoted as deg(u, k, b, i), is the number of neighbors of u in the k-core after the (i -1)-th iteration, plus the number of nodes in the same component as u. Formally, it is defined as:

Algorithm 1 Initialization

Input: a λ-shell component Ci

Output: the estimated benefit of the eb(Ci)

• 1: Obtain the λ-threshold component T(Ci, k, b, 0);
• 2: for all nodes u ∈ T(Ci, k, b, 0) do
• 3: Calculate deg(u, k, b, 1);
• 4: end for
• 5: Eneed(Ci) = 1/2 ∑u∈T (Ci,k,b,j) (k - deg(u, k, b, 1));
• 6: eb(Ci) = |Ci|/Eneed(Ci);
• 7: Return eb(Ci);

where N(u) represents the set of neighbors of u in G, and Cu denotes the λ-shell component to which u belongs.

Then, based on the following observation, we define the λ-threshold to identify the nodes that play a key role in the solution generation process.

Given a graph G, a λ-shell component Ci, the nodes in Ci all have coreness λ, but deg(u, k, b, i) can be larger than λ where u ∈ Ci. These nodes do not become part of the kcore because the number of neighbors satisfying the k-core requirement is less than k.

Example-2. Consider Figure 1(a), where k = 3 and b = 3, node v5 has deg(v5, 3, 3, 1) = 3 at the beginning of the first iteration, but because its neighbors v6 and v8 have deg(v6, 3, 3, 1) = 2 and deg(v8, 3, 3, 1) = 2, v5 does not belong to the k-core. After selecting the λ-shell component to be converted into part of the k-core, we must carefully choose which edges to add, rather than adding them randomly.

Definition 7 (λ-threshold component) Given a graph G, an integer k, a budget b, and a λ-shell component Ci, at the j-th iterationits, its λ-threshold component, denoted as T(Ci, k, b, j), is defined as the set of nodes in Ci whose dynamic degree is less than or equal to k, denoted as:

Estimated benefit initialization. In this step, we use the dynamic degree and λ-threshold component to initialize the estimated benefit of each λ-shell component. First, we introduce a method for determining the number of edges needed to convert any λ-threshold component to part of the k-core.

Theorem 2. Given a graph G, an integer k, a budget b, and a λ-shell component Ci, in the j-th iteration, Ci becomes part of a k-core if every node u in T(Ci, k, b, j) is newly connected to other nodes within Ci or V (k, b, i) by (k - deg(u, k, b, j)) edges.

We assume that the conversion of the λ-threshold component Ci into a k-core can be achieved entirely by adding edges between nodes with dynamic degrees less than k. The number of edges required to achieve this transformation is given by:

Then, we can define the estimated benefit of each λ-shell component.

Definition 8 (Estimated benefit) For a λ-shell component Ci, its estimated benefit, denoted as eb(Ci), is defined as |Ci | Eneed(Ci) , where Eneed(Ci) represents the number of edges required to convert Ci into part of the k-core.

4.4 Iterative Dynamic Growth

By Theorem 2, we can deduce that within each λ-shell component, edges can be inserted between the λ-threshold components until the k-core requirement is met. The choice of edges to insert is not unique. Furthermore, we observe that within each λ-shell component, the difference between applying Complete Conversion and Partial Conversion, as proposed in FastCM/FastCM+ [Sun et al., 2022], is minimal. Therefore, this method focuses on the contribution of edges that span across different λ-shell components, and introduces Complete Growth and Partial Growth. We first introduce the definitions of seed and growth.

Definition 9 (Seed) Given a graph G, an integer k, and a budget b, after the i-th iteration,

where each Sj is a connected component of V (k, b, i), we refer to Sj as a seed.

Definition 10 (Growth) Given a seed Sj, the definition of growth is to add some λ-shell components Cgrowth(Sj) = {C1,C2, . . . ,Cm} that are connected to the seed to the current solution, such that the seed grows to S′j = Sj ∪ Cgrowth(Sj). For complete growth and partial growth, we record S′j as CG(Sj) and PG(Sj), respectively.

Complete Growth. In this section, we present the complete growth, which takes into account the dynamic relationships between different λ-shell components. To begin, we classify the edges connecting λ-shell components into the following categories: effective edges, semi-effective edges, and ineffective edges.

Definition 11 (Effective Edges, Semi-Effective Edges, and Ineffective Edges): When in the i-th iteration, we attempt to convert the λ-shell component C1 into k-core followers. Suppose C1 is connected to V (k, b, i - 1) through

Algorithm 2 Complete Growth

Input: Graph G, Integer k, Budget b, estimated benefit for all λ-shell components EB = {eb(C1), eb(C2), . . . , eb(Cn)} Output: Set of inserted edges E

1: i ← 0, SeedSet ← ∅; 2: while b > Eneed(V (k, b, i)) do 3: Cj = argmax(eb(Ci)),Ci ∈ EB; 4: Sh = argmax(eb(CG(Si) \ Si)), Si ∈ SeedSet ; 5: if eb(Cj)>eb(Sh) then 6: SeedSet ← SeedSet ∪ Cj (Add Cj to SeedSet and update it to Sj); 7: else 8: Completely grow Sh to S′h ; 9: SeedSet ← SeedSet \ Sh ∪ S′h ; 10: end if 11: i ← i + 1; 12: for all nodes u ∈ SeedSet do 13: Calculate deg(u, k, b, i); 14: end for 15: end while 16: Insert edges in SeedSet such that each node's degree achieves k;

• 17: Return the inserted edges E;

edge e(u, v), where u ∈ C1 and v ∈ V (k, b, i - 1). Consider the case where the edge does not exist, and calculate deg(u, k, b, i) and deg(v, k, b, i). In this case:

• (i) If deg(u, k, b, i) < k and deg(v, k, b, i) < k, then e(u, v) is an effective edge.
• (ii) If deg(u, k, b, i) ≥ k and deg(v, k, b, i) ≥ k, then e(u, v) is an ineffective edge.
• (iii) Else, e(u, v) is a semi-effective edge.

When both Cu and Cv are in the current solution, compared to the case where the edge does not exist, a valid edge reduces Eneed(Cu) and Eneed(Cv) by 0.5 each. A semi-valid edge reduces Eneed(Cu) or Eneed(Cv) by 0.5, while an invalid edge has no effect on Eneed(Cu) and Eneed(Cv). Here, Cu and Cv represent the λ-shell components to which nodes u and v belong, respectively.

In the i-th iteration, the complete growth of a seed means adding all the λ-shell components connected to that seed into the current solution. Then the dynamic degree of nodes is updated. The growth process stops if the following condition holds: Eneed(V (k, b, i)) = 1 2 ∑u∈V (k,b,i) max(0, (k - deg(u, k, b, i + 1))) > b. To accommodate the dynamic change of node degrees, we perform edge insertion after the

iteration is completed.

Example-3. Consider Figure 2, where k = 3 and b = 6. In the first iteration, the algorithm attempts to convert {v5, v6, v7, v8, v9} into k-core followers, e(v4, v5) is an semieffective edge. In the second iteration, the algorithm tries to convert {v11, v12, v13, v14} into k-core followers, e(v9, v11) is an ineffective edge. In the third iteration, the algorithm attempts to convert {v10} into k-core followers, e(v7, v10) is an effective edge.

Partial Growth. Complete growth effectively improves the solution quality of the core maximization. However, the complete growth strategy may be insufficient in certain situations.

Algorithm 3 Partial Growth

Input: Graph G, Integer k, Budget b, estimated benefit for all λ-shell components EB = {eb(C1), eb(C2), . . . , eb(Cn)} Output: Set of inserted edges E

1: i ← 0, SeedSet ← ∅; 2: while b > Eneed(V (k, b, i)) do 3: Cj = argmax(eb(Ci)),Ci ∈ EB; 4: Sh = argmax(eb(PG(Si) \ Si)), Si ∈ SeedSet ; 5: if eb(Cj)>eb(Sh) then 6: SeedSet ← SeedSet ∪Cj {(Add Cj to SeedSet and update it to Sj)}; 7: else 8: Partially grow Sh to S′h ; 9: SeedSet ← SeedSet \ Sh ∪ S′h ; 10: end if 11: i ← i + 1; 12: for each edge e = (u, v), where u ∈ S′h \ Sh and v /∈ V (k, b, i) do 13: if edge e is effective then 14: Eneed(Cv) ← Eneed(Cv) - 1; 15: else if edge e is semi-effective then 16: Eneed(Cv) ← Eneed(Cv) - 0.5; 17: end if 18: Update eb(Cv) = |Cv| Eneed(Cv) ; 19: end for

• 20: end while
• 21: Insert edges in all λ-threshold components such that each node's degree achieves k;
• 22: Return the inserted edges E;

For instance, the number of edges required to convert all connected components into the k-core might exceed the available budget b, preventing further growth. To address this limitation, we propose a more fine-grained partial growth strategy.

Example-4. Consider Figure 3, where k = 3 and b = 2. When using complete growth, in the first iteration, {v5, v6, v7} is transformed into the k-core, requiring b = 1. In the second iteration, the algorithm attempts to grow {v5, v6, v7} into {v5, v6, v7, v8, v9}, requiring b = 2.5. Since the budget b is not sufficient, the growth fails, and the iteration ends. The final k-core followers are {v5, v6, v7}, and the inserted edges are e(v4, v6) and e(v4, v5). As we assume the graph is unweighted, edges like e(v5, v6) cannot be reconnected if they already exist. However, this is clearly not the optimal solution, as inserting e(v4, v8) and e(v5, v8) would result in the k-core followers being {v5, v6, v7, v8}.

The above example demonstrates that by refining the growth process and dividing it into more granular steps-where each growth phase converts only one λ-shell component-we can achieve superior results. This is the key idea behind partial conversion. However, to implement partial conversion, a critical issue must be addressed: how to dynamically adjust the estimated benefit of each λ-shell component to ensure that the optimal one is selected for growth.

We derive the following estimated benefit update rule: In the i-th iteration, after the algorithm adds the λ-shell component Ci to the k-core followers, all λ-shell components Cj connected to Ci will be updated as follows: for each effective edge between Cj and Ci, the Eneed(Cj) is reduced by 1, and for each semi-effective edge, the Eneed(Cj) is reduced by 0.5. The estimated benefit of Cj is then recalculated based on the updated Eneed(Cj ) value.

The above update rule is based on the observation that when Ci become k-core followers, all the edges connecting Ci and Cj will still make the dynamic degree of the nodes in Ci change, but since Ci has been added to the solution, the eb(Ci) change has no effect on the subsequent iteration process, therefore, we reflect this benefit in Cj . In addition, in the i-th iteration, the partial growth of a seed means adding the λshell components with largest estimated benefit connected to that seed into the current solution. Then the estimated benefit of the λ-shell component connected to the grown seed will be updated according to the rules presented above.

4.5 Offline Storage

Compared to complete growth, partial growth offers advantages in solution quality but requires more computational time. However, we can still accelerate the process using offline storage techniques. Due to the inherent invariability of the underlying structure of the graph, certain properties remain consistent across the same graph [Malliaros et al., 2020]. In k-core maximization, the relative estimated benefit order of the λ-shell components remains largely consistent, even when faced with different parameters k and b. By storing the relative estimated benefit order, the next time we encounter the same graph, we can directly generate k-core followers based on this order without recalculating the estimated benefit of each λ-shell component.

5 Experiments

In this section, we present the results of evaluating our proposed method on multiple public datasets. We detail the experimental setup, including the parameters used, and the evaluation metrics applied to assess performance. A comprehensive comparison of the results is also provided, showing how our method performs relative to state-of-the-art algorithms. Datasets. We use 10 real-world network datasets in our experiments, chosen for their diversity and relevance to the task. Table 1 summarizes the key graph statistics for these datasets. All datasets are obtained from two public repositories: Network Repository (http://networkrepository.com) and SNAP (http://snap.stanford.edu), and are treated as undirected graphs to ensure consistency across experiments.

Compared methods. We compare the proposed method against four other methods, described as follows.

• EKC [Zhou et al., 2019]: follows a greedy approach by adding one edge between non-adjacent vertices per iteration to maximize the k-core.
• VEK [Zhou et al., 2022]: adopts a greedy strategy focused on adding one vertex per iteration, optimizing the process through a scoring function and efficient candidate pruning.
• FastCM [Sun et al., 2022]: performs complete conversion and focuses on converting vertices within the (k - 1)-shell.
• FastCM+ [Sun et al., 2022]: combines complete and partial conversion strategies to convert vertices in the (k - λ)-shell (λ ≥ 1), using DP-based node selection methods.
• Dynamic Seed-GrowthCM CG: is our proposed algorithm using complete growth, abbreviated as DSG CG.
• Dynamic Seed-GrowthCM PG: is our proposed algorithm using partial growth, abbreviated as DSG PG.
• Dynamic Seed-GrowthCM PG+: is Dynamic SeedGrowthCM PG combined with an Offline Storage technique, abbreviated as DSG PG+.

Parameters and evaluation metrics. By default, We set the parameter k to 20 and the budget b to 200. We use the number of k-core followers and the algorithm running time as evaluation metrics. Due to the previously demonstrated poor performance of EKC [Zhou et al., 2019] and VEK [Zhou et al., 2022] in terms of both runtime and solution quality, we directly refer to the results reported in [Sun et al., 2022] rather than conducting the experiments again. All experiments were conducted on a machine equipped with an AMD Ryzen 7 5800H CPU (3.2 GHz), 16 GB of RAM, and running Windows 11. Each experiment was repeated ten times, and the average results are reported.

5.1 Effectiveness and Efficiency Evaluations

As shown in Table 1, our proposed algorithms, Dynamic Seed-GrowthCM CG (DSG CG) and Dynamic SeedGrowthCM PG (DSG PG), consistently outperform all baseline methods across various datasets by achieving a greater number of k-core followers. The key to this superior performance lies in our utilization of edges spanning across different λ-shell components. On the other hand, it is evident that the method employing complete growth, DSG CG, achieves shorter running times compared to all previously proposed methods, except on the Facebook dataset. While the partial growth method, DSG PG+, incurs slightly longer running times than DSG CG, it maintains the effectiveness of DSG PG and achieves a higher number of k-core followers.

5.2 Evaluation by Varying b

Figure 4 reports that as b increases, the number of k-core followers obtained by all methods increases. Among them, DSG PG achieves the highest number of k-core followers. Additionally, as b increases, the gap between DSG PG/DSG CG and FastCM+/FastCM becomes increasingly larger. This is because the number of λ-shell components requiring conversions increase with b, and the edges spanning different λ-shell components increase accordingly, highlighting the growing advantages of DSG PG/DSG CG. Figure 5 reports the running time of different algorithms as b increases. DSG PG+ maintains a comparable number of k-core followers to DSG PG while significantly reducing its running time, demonstrating the feasibility of offline storage.

5.3 Case Study on Collaboration Network

We applied core maximization to a collaboration network, which is a connected component comprising 14 nodes, extracted from the ca-GrQc dataset. The edges in the network represent co-authorship between authors, indicating that they have collaborated on a research paper.

Our objective is to strengthen a specific k-core by inserting new edges, thereby increasing interactions among authors. We set k = 4 and b = 4. Initially, the size of the 4-core is 6. By applying our algorithm, the size of the 4-core increases to 12, as illustrated in Figure 6.

6 Conclusion

In this paper, we propose Dynamic Seed-GrowthCM, which employs complete/partial growth to address k-core maximization. The method accounts for dynamic changes in node degrees and effectively leverages edges across different λshell components, leading to improved performance. Experimental results show that our method enhances both efficiency and solution quality. This makes our method particularly suitable for large-scale, real-world networks.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant No. 62276187 and No. 62422210), the National Key Research and Development Program of China (Grant No. 2023YFC3304503), and the Hong Kong RGC Project (Grant No. 12200424).