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.

Modern data generation has grown to enormous proportions, with events occurring at increasingly higher rates. Yet for graph analytics, this growth in scale and velocity has not been matched by improved algorithm or infrastructure techniques: most systems still focus on post-mortem or static analysis. This paper builds on an efficient graph processing abstraction that enables online analysis of dynamically evolving graphs at scale. Integral to this abstraction is that events tied to both graph topology changes as well as algorithmic maintenance occur and are processed asynchronously, concurrently, and autonomously (i.e., without shared state).