Source-linked AI summary
Efficient Core Maintenance in Large Dynamic Graphs
Rong-Hua Li, Jeffrey Xu Yu
TL;DR
Dynamic graph updates make full k-core recomputation expensive for large networks. The paper identifies the nodes that may change after an edge insertion or deletion, recomputes only those nodes, and adds two pruning strategies. Experiments report speedups up to 101.8× on real-world data and speedup ratios above 4700 for a five-million-node synthetic graph.
Problem
Maintaining core numbers after dynamic edge insertions or deletions is difficult, while recomputing every node with the O(n+m) static algorithm is expensive on very large graphs.
Method
The algorithm restricts updates to induced core subgraphs around changed-edge endpoints, identifies definitely changing nodes, recomputes them, and applies X-pruning and Y-pruning.
Results
101.8× is the maximal speedup of algorithm XY over baseline B across the reported real-world datasets, while the speedup ratio exceeds 4700 for a five-million-node synthetic graph.
Takeaways & Limitations
The method is most preferable for very large graphs with relatively small batches of updates; for small, frequently changing graphs, the baseline can be more efficient.
Abstract
from arXiv · showhide
The $k$-core decomposition in a graph is a fundamental problem for social network analysis. The problem of $k$-core decomposition is to calculate the core number for every node in a graph. Previous studies mainly focus on $k$-core decomposition in a static graph. There exists a linear time algorithm for $k$-core decomposition in a static graph. However, in many real-world applications such as online social networks and the Internet, the graph typically evolves over time. Under such applications, a key issue is to maintain the core number of nodes given the graph changes over time. A simple implementation is to perform the linear time algorithm to recompute the core number for every node after the graph is updated. Such simple implementation is expensive when the graph is very large. In this paper, we propose a new efficient algorithm to maintain the core number for every node in a dynamic graph. Our main result is that only certain nodes need to update their core number given the graph is changed by inserting/deleting an edge. We devise an efficient algorithm to identify and recompute the core number of such nodes. The complexity of our algorithm is independent of the graph size. In addition, to further accelerate the algorithm, we develop two pruning strategies by exploiting the lower and upper bounds of the core number. Finally, we conduct extensive experiments over both real-world and synthetic datasets, and the results demonstrate the efficiency of the proposed algorithm.
I. INTRODUCTION
Dynamic graphs make maintaining node core numbers costly because an edge update can propagate effects through neighboring nodes. The paper targets this by updating only a bounded, identified subset rather than recomputing the entire graph.
- k-core measures cohesive subgroups while supporting applications including network visualization, Internet analysis, protein-function prediction, influence identification, and percolation studies.
- Static k-core decomposition is computable in O(n+m), but dynamic edge updates can require core-number maintenance across affected nodes.
- Recomputing every node after each update is expensive for very large graphs.
- The proposed approach identifies only nodes whose core numbers may change and then recomputes those nodes after edge insertion or deletion.
II. PRELIMINARIES
The preliminaries define k-cores, core numbers, and the dynamic maintenance problem. Although static decomposition is linear-time, recomputing all nodes after each update is costly.
- A k-core is the largest subgraph in which every node has degree at least k.
- A node’s core number is the largest k-core containing it, and cores are nested across increasing core levels.
- k-core decomposition computes the core number for every node in the graph.
- In the example, nodes v3 through v7 form a 4-core, larger nested subgraphs form a 3-core, and the whole graph is a 2-core.
- Static decomposition takes O(n+m), whereas the dynamic problem updates known core numbers after edge insertion or deletion without automatically recomputing the whole graph.
III. THE PROPOSED ALGORITHM
The proposed theory localizes possible core-number changes to induced core subgraphs around updated edge endpoints. Lemmas establish update bounds and distinguish endpoint core-number cases.
- For every node v, the neighbor-count quantities satisfy Yv ≤ Cv ≤ Xv ≤ Dv.
- An induced core subgraph Gv contains v and connected reachable nodes whose core numbers equal Cv.
- For edge endpoints u and v, only Gu, Gv, or Gu∪v may require updates, depending on whether Cu is greater than, less than, or equal to Cv.
- Inserting or deleting one edge changes any node’s core number by at most 1.
- When Cu = Cv, inserting an edge causes both endpoint core numbers to increase by 1 or both to remain unchanged.
A. The basic algorithm
The basic maintenance algorithm uses three stages to locate potentially affected nodes, filter nodes whose core numbers remain unchanged, and update the remainder. Its worst-case cost depends on the affected region rather than total graph size.
- The basic algorithm: Color finds the relevant induced core subgraph, RecolorInsert or RecolorDelete filters nodes, and UpdateInsert or UpdateDelete changes the identified core numbers.
- The basic algorithm: For insertion with equal endpoint core number c, Color traverses the union Gu∪v and initially colors every node in Vc by 1.
- The basic algorithm: RecolorInsert recursively changes nodes with insufficient Xw support to color 0, while remaining color-1 nodes are exactly those requiring updates.
- The basic algorithm: The insertion algorithm has worst-case complexity O(|Vc| Σu∈Vc Du), independent of graph size.
B. Pruning strategies
The paper accelerates dynamic k-core maintenance with X-pruning and Y-pruning, which remove nodes whose core numbers are provably unchanged after an edge update.
- Algorithmic role: The basic insertion and deletion algorithms depend on the size of V_c rather than the full graph, motivating pruning of definitely unchanged nodes.X-pruning and Y-pruning replace parts of candidate discovery while retaining the recoloring and update stages.
- X-pruning: X-pruning uses X_w, an upper bound on C_w, to prune nodes that cannot increase to c+1 after edge insertion.When X_w < c+1, the node’s core number will not increase; the strategy also prunes downstream nodes separated by it.
- Pruning scope: The pruning rules restrict updates to induced core subgraphs connected to the affected endpoint or endpoints.The relevant subgraph depends on whether the endpoint core numbers are greater than, less than, or equal to each other.
- Illustrative example: For deletion of edge (v8, v10), the core number of nodes {v8, v10, v9, v2, v18} decreases from the relevant c=3 case to 2.Both endpoint upper-bound counts are below c, so the affected induced subgraphs must be examined.
- Y-pruning: Y-pruning uses Y_w, a lower bound on C_w, to prune nodes whose core numbers cannot decrease after edge deletion.When Y_w = c, path-based rules identify nodes that can be safely removed from the update candidate set.
IV. EXPERIMENTS
The experiments evaluate the proposed approach through a comprehensive experimental study, beginning with the setup and then reporting results.
- IV. EXPERIMENTS: The paper conducts comprehensive experiments to evaluate its approach.The section reports the experimental setup before presenting results.
A. Experimental setup
The evaluation compares baseline and proposed maintenance algorithms across 15 real-world datasets on a specified server environment.
- Algorithms: Five algorithms are compared: baseline B, basic algorithm N, X-pruning algorithm X, Y-pruning algorithm Y, and combined algorithm XY.The proposed variants differ by whether they include X-pruning, Y-pruning, or both.
- Datasets: The datasets cover co-authorship, online social, communication, peer-to-peer, and location-based social networks.The study collects 15 real-world datasets from these network categories.
- Datasets: Table I summarizes the datasets used in the evaluation.The supplied table passage identifies its role as a dataset summary.
- Environment: The experiments run on a Windows Server 2007 with 4xDual-Core Intel Xeon 2.66 GHz CPUs and 128G memory.All algorithms are implemented in Visual C++ 6.0.
B. Results for single edge updates
Across the evaluated datasets, the proposed algorithms outperform the baseline for single-edge updates, with combined pruning generally best and larger speedups on larger graphs.
- Evaluation protocol: 500 random edge insertions and 500 random edge deletions are used to measure average insertion, deletion, and update times.The reported averages are computed over the corresponding update operations.
- Overall results: All proposed algorithms outperform baseline B across the evaluated datasets, with algorithm XY ranked best, followed by X, Y, N, and B.Algorithm XY combines both X-pruning and Y-pruning.
- Speedup: 101.8x is the maximal speedup of algorithm XY over B for average update time on Gowalla.On Gowalla, algorithms X, Y, and N achieve 81.7x, 62.3x, and 56.2x speedups, respectively.
- Speedup: 3.2x is the minimal speedup of algorithm XY over B for average update time on HepTh.On HepTh, algorithms X, Y, and N achieve 3.0x, 2.3x, and 2.2x speedups, respectively.
- Pruning effects: X-pruning reduces HepTh average deletion, insertion, and update times over N by 96.3%, 10%, and 36.8%, respectively.Y-pruning reduces the corresponding times by 6%, 3.1%, and 4.3%.
- Pruning effects: On Gnutella, X-pruning reduces average deletion time over N by 143.75%, compared with 5.8% for insertion time.Y-pruning reduces deletion time by 59% and insertion time by 2.8% over N.
C. Results for a batch of edge updates
The paper evaluates core-maintenance performance for batches of edge updates against recomputing all core numbers. Its algorithm is especially advantageous for large graphs with relatively few updates, while the baseline can be preferable for smaller, frequently changing graphs.
- Batch-update evaluation: For a batch of r edge updates, algorithm XY is invoked r times, whereas baseline algorithm B recomputes all node core numbers once.The comparison uses XY because it is reported as the best algorithm for single edge updates.
- Batch-update evaluation: 101.8 is the speedup ratio of algorithm XY over algorithm B on the Gowalla dataset for a single edge update.For Gowalla, XY is more efficient than B when the batch has at most 101 updates.
- Batch-update evaluation: Algorithm XY’s speedup ratio increases with graph size, making it more efficient for large graphs with small r.For a batch, the paper states that XY is preferable when r is below the single-update speedup ratio.
- Batch-update evaluation: When a graph is very small and frequently varying, the baseline algorithm is more efficient than algorithm XY.The paper contrasts this setting with very large graphs that evolve slowly.
- Synthetic large-graph evaluation: For synthetic graphs with 5 million nodes and 25 million edges, the speedup ratio exceeds 4700.For a fixed graph size, XY is preferable below the red curve in Fig. 5; otherwise, the baseline is more efficient.
V. RELATED WORK
Related work establishes k-core decomposition as a widely used tool for network analysis and describes algorithms for static and specialized graph settings. It also highlights implementation considerations such as random access in disk-resident graphs.
- Applications: K-core decomposition has been applied to visualize large networks, analyze Internet topology, study protein interaction networks, identify influential spreaders, and investigate percolation.These applications are presented as examples of prior uses of k-core decomposition.
- Applications: Prior visualization methods use k-core decomposition to partition large graphs, draw autonomous-systems graphs, and uncover hierarchical network structure.Triangle k-core is also described as a distinct notion for extracting clique-like structure and visualizing graphs.
- Theoretical studies: Random graph models have been used to investigate the threshold phenomenon for the existence of a k-core.The passage refers to this as a separate line of related work.
- Algorithms: Batagelj and Zaversnik proposed an O(n + m) static k-core decomposition algorithm that recursively removes the lowest-degree node and maintains node order with bin sorting.The algorithm may be inefficient for disk-resident graphs because it requires random graph access.
VI. CONCLUSIONS
The paper proposes an efficient dynamic-graph algorithm that identifies and updates only nodes whose core numbers may change after an edge update, with additional pruning strategies and evaluation on real and synthetic datasets.
- Conclusion: Only nodes in the induced core subgraphs of u, v, or their union may need core-number updates after inserting or deleting edge (u, v).The induced core subgraph Gu contains nodes reachable from u with the same core number as u, and similarly for v.
- Conclusion: The method uses coloring to identify potentially affected nodes, recoloring to determine nodes that definitely require updates, and a linear algorithm to update their core numbers.This is the paper’s stated maintenance pipeline.
- Conclusion: X-pruning and Y-pruning further accelerate the dynamic core-maintenance algorithm.The pruning strategies exploit bounds on core numbers, as described in the paper context.
- Conclusion: Experiments on 15 real-world and 5 large synthetic datasets demonstrate the efficiency of the proposed algorithm.The evaluation covers both real-world and synthetic data.