2023/11/13 by Juntong Luo, Luo, Juntong, Scott Sallinen +3 · 2 citations
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Graph Theory and Algorithms #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2311.07016
openalex publication_date 2023/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recent advances in dynamic graph processing have enabled the analysis of highly dynamic graphs with change at rates as high as millions of edge changes per second. Solutions in this domain, however, have been demonstrated only for relatively simple algorithms like PageRank, breadth-first search, and connected components. Expanding beyond this, we explore the maximum flow problem, a fundamental, yet more complex problem, in graph analytics. We propose a novel, distributed algorithm for max-flow on dynamic graphs, and implement it on top of an asynchronous vertex-centric abstraction. We show that our algorithm can process both additions and deletions of vertices and edges efficiently at scale on fast-evolving graphs, and provide a comprehensive analysis by evaluating, in addition to throughput, two criteria that are important when applied to real-world problems: result latency and solution stability.