Parallel algorithm maintains core numbers quickly for dynamic graphs
Batch-Dynamic Coreness and Applications with Logarithmic Work via Balanced Pressures
Data Structures and Algorithms
Summary
Graphs—networks of connections—often change over time, and understanding how tightly connected parts of these graphs are is important for many uses. The authors introduce a new method that quickly estimates these connection levels when many connections change at once. Their approach assigns each point in the graph a pressure value and adjusts these pressures in parallel to keep the network balanced. This method is faster and more accurate than previous attempts and works well even on very large real-world graphs.
What this means in practice
- •For network engineers: Maintain efficient approximations of connectivity levels as networks change in real time to optimize monitoring and routing.
- •For social media platform teams: Accelerate analyses of community structures and dense areas in large user graphs to support feature updates and recommendations.
Authors
Quinten De Man, Laxman Dhulipala, Kishen N Gowda, Zhongqi Wang
Abstract
We give a parallel algorithm that maintains a one-sided $(2+\varepsilon)$-approximation of all core numbers under batches of edge insertions and deletions. For fixed $\varepsilon>0$, the expected amortized work is $O(\log n)$ per edge update, and each batch has deterministic polylogarithmic depth. This improves on the previously known $(4+\varepsilon)$-approximation and $O(\log^2 n)$ amortized work bounds. This approximation factor approaches the factor-two limit for polylogarithmic update and query time under the OMv conjecture. Our algorithm is based on assigning each vertex a "pressure" and splits each edge's unit load smoothly between its endpoints according to their pressures. After each batch of updates, our dynamic algorithm adjusts the pressures of vertices in parallel to restore balance between the pressures and loads. We show that by maintaining balanced pressures we can obtain good approximations of core numbers. Our construction also gives a $(1+\varepsilon)$-approximation of the densest-subgraph value with logarithmic expected amortized work and supports batch-dynamic maximal matching, clique counting, forest decomposition, and coloring in low-arboricity graphs with improved or matching work bounds. We give a practical implementation of our batch-dynamic coreness algorithm and find that it is able to achieve smaller empirical error than the state-of-the-art parallel batch-dynamic implementation, while running faster. On six real-world graphs, it runs $32\times$ faster than that implementation in geometric mean and $4.1\times$ faster than a state-of-the-art heuristic baseline. On three graphs with up to 1.8 billion edges, it is $9.2\times$ faster than the heuristic baseline.