Abstract
Maintaining a $k$-core decomposition quickly in a dynamic graph has important applications in network analysis. The main challenge for designing efficient exact algorithms is that a single update to the graph can cause significant global changes. Our paper focuses on approximation algorithms with small approximation factors that are much more efficient than what exact algorithms can obtain. We present the first parallel, batch-dynamic algorithm for approximate $k$-core decomposition that is efficient in both theory and practice. Our algorithm is based on our novel parallel level data structure, inspired by the sequential level data structures of Bhattacharya et al [STOC '15] and Henzinger et al [2020]. Given a graph with $n$ vertices and a batch of updates $\mathcal{B}$, our algorithm provably maintains a $(2 + \varepsilon)$-approximation of the coreness values of all vertices (for any constant $\varepsilon > 0$) in $O(|\mathcal{B}|\log^2 n)$ amortized work and $O(\log^2 n \log\log n)$ depth (parallel time) with high probability. As a by-product, our $k$-core decomposition algorithm also gives a batch-dynamic algorithm for maintaining an $O(\alpha)$ out-degree orientation, where $\alpha$ is the current arboricity of the graph. Our framework obtains new provably-efficient parallel batch-dynamic algorithms for maximal matching, clique counting, and vertex coloring.
Introduction
In network analysis, a $k$-core is a maximal subgraph where every vertex has at least $k$ neighbors within that subgraph. Identifying these cores is essential for uncovering dense communities, but maintaining them in dynamic settings—where edges are constantly added or deleted—is notoriously difficult.
The core challenge is the "cascade effect": a single edge update can theoretically alter the coreness values of every other vertex in the graph. While sequential algorithms exist, they are too slow for modern massive graphs. Previous parallel attempts lacked theoretical guarantees on "depth" (the longest chain of sequential dependencies), meaning they couldn't effectively utilize many-core processors for large batches of updates. This paper introduces the first parallel, batch-dynamic algorithm for $(2+\epsilon)$-approximate $k$-core decomposition with provable polylogarithmic depth.
The Parallel Level Data Structure (PLDS)
The authors introduce the Parallel Level Data Structure (PLDS), which is fundamentally redesigned to handle batches of updates simultaneously in a parallel environment.
- Level Partitioning: Vertices are partitioned into $O(\log^2 n)$ levels based on their induced degrees. The "level" of a vertex serves as a proxy for its coreness.
- Batch Processing: Instead of processing updates one by one, the PLDS processes a batch $B$ of updates. It uses a movement rule where vertices move levels only when specific degree invariants are violated, preventing unnecessary recomputations.
- Polylogarithmic Depth: By allowing all vertices at a specific level to be checked and moved in parallel, the algorithm achieves a depth of $O(\log^2 n \log \log n)$, ensuring it scales well on multicore machines.
A General Framework for Dynamic Graph Problems
The PLDS also maintains a "low out-degree orientation," which the authors leverage to create a general framework for other dynamic graph problems.
As illustrated above, the framework provides efficient parallel batch-dynamic solutions for:
- k-Core Decomposition and Out-Degree Orientation (using levels).
- Maximal Matching and k-Clique Counting (using orientation).
- Vertex Coloring (using both levels and orientation).
Key Insights and Results
By relaxing the goal to a $(2+\epsilon)$-approximation, the authors break the theoretical barrier of P-completeness associated with exact $k$-core decomposition. The algorithm uses "hysteresis"—waiting until enough error accumulates before updating a vertex's level—to amortize update costs over many edge changes, leading to $O(|B| \log^2 n)$ total work.
Evaluated on a 30-core machine across 11 diverse graphs (including twitter and friendster with billions of edges), the PLDS demonstrated dramatic performance gains:
- Speedup: Up to 723x faster than the best sequential exact algorithms and 114x faster than state-of-the-art parallel exact algorithms.
- Scalability: While other dynamic algorithms timed out on the largest datasets, the PLDS completed all experiments within the three-hour limit.
- Accuracy: Despite being an approximation, the empirical error remained very close to exact values, far outperforming the theoretical $(2+\epsilon)$ bound.
Conclusion
This work provides the first parallel batch-dynamic algorithm for approximate $k$-core decomposition that is efficient in both theory and practice. While the current structure requires $O(n \log^2 n + m)$ space to achieve optimal depth, future work may focus on achieving linear space without sacrificing performance.
Summary updated