TL;DR
This paper introduces the first parallel, batch-dynamic algorithm for $(2 + \varepsilon)$-approximate $k$-core decomposition. By leveraging a novel "Parallel Level Data Structure" (PLDS), the authors achieve polylogarithmic depth (parallel time) and massive speedups—up to 723x—over state-of-the-art sequential and parallel baselines on graphs with billions of edges.
What Problem Does This Paper Address?
The $k$-core of a graph is the maximal subgraph where every vertex has at least $k$ neighbors within that subgraph. $k$-core decomposition is a vital tool for community detection and network analysis, but it is notoriously difficult to maintain in dynamic settings where edges are constantly added or removed.
The primary challenge is that a single edge update can trigger a "cascade" of changes across the entire graph. Furthermore, the standard algorithm for finding $k$-cores—iteratively "peeling" low-degree vertices—is inherently sequential. In technical terms, exact $k$-core decomposition is P-complete, meaning it's unlikely to have a highly parallel algorithm. This paper tackles the problem by relaxing the requirement to a $(2 + \varepsilon)$-approximation, allowing for efficient parallelization without sacrificing too much accuracy.
Methods
The authors propose the Parallel Level Data Structure (PLDS). Inspired by sequential level structures, the PLDS partitions vertices into $O(\log^2 n)$ levels based on their induced degrees.
Key technical components include:
- Invariants: The structure maintains two invariants: an upper bound on the degree of a vertex to neighbors at its level or higher, and a lower bound on its degree to neighbors at its level or lower.
- Batch Processing: Unlike sequential structures that update one edge at a time, the PLDS processes a batch of updates $\mathcal{B}$ simultaneously. It moves vertices between levels in parallel while maintaining the invariants.
- Low Out-Degree Orientation: As a side effect, the PLDS maintains a directed version of the graph where every node has a low out-degree (proportional to the graph's arboricity $\alpha$). This orientation serves as a "Swiss Army knife" to solve other problems like maximal matching, clique counting, and vertex coloring.
Datasets
The algorithms were evaluated on 11 real-world undirected graphs from SNAP, the DIMACS Shortest Paths challenge, and the Network Repository. These include:
- Social/Web Networks: dblp, wiki, youtube, livejournal, orkut, twitter, friendster.
- Specialized Networks: brain (dense human brain network), usa, and ctr (road networks).
- Scale: The largest dataset, friendster, contains over 65 million vertices and 1.8 billion edges.
Key Insights and Ideas
- The Power of Approximation: By accepting a $(2 + \varepsilon)$ error bound, the authors move the problem from the "inherently sequential" P-complete category into one that can be solved in polylogarithmic parallel time (depth).
- Level-Based Estimation: A vertex's coreness can be estimated simply by looking at the level it settles into within the PLDS. This avoids the need for complex global recalculations.
- Parallel Cascades: While sequential algorithms might move a vertex one level at a time (causing long dependency chains), the PLDS deletion algorithm moves vertices to their final level in a single step, significantly reducing parallel depth.
- Unified Framework: The data structure isn't just for $k$-cores; the low out-degree orientation it provides is a fundamental building block for a variety of other batch-dynamic graph algorithms.
Key Results
The authors implemented their algorithm (PLDS) and an optimized version (PLDSOpt) on a 30-core machine.
- Speedups: PLDSOpt achieved up to a 114.52x speedup against the best parallel exact implementation and up to 723.72x against the best exact sequential algorithm.
- Scalability: On massive graphs like twitter and friendster, most existing dynamic algorithms timed out (taking over 3 hours), while the PLDS algorithms finished in seconds or minutes.
- Accuracy: Despite the theoretical $(2 + \varepsilon)$ bound, the empirical error was much lower, typically staying within a factor of 1.2x to 2.4x of the exact value.
- Parallel Efficiency: The algorithm demonstrated excellent self-relative speedup, scaling well as more threads were added.
Limitations and Future Work
- Space Complexity: The current PLDS uses $O(n \log^2 n + m)$ space. While manageable for most modern hardware, it is super-linear in the number of vertices. The authors note that a linear-space version is theoretically possible but might incur higher parallel depth.
- Adversarial Robustness: Some of the derived algorithms (like vertex coloring) are only proven robust against "oblivious" adversaries (who don't see the algorithm's previous outputs) rather than "adaptive" ones.
- Future Directions: A major open problem is designing a parallel batch-dynamic algorithm that is strictly space-efficient (linear space) without increasing the parallel time (depth).
Summary updated