# Maximum Flow on Highly Dynamic Graphs

**Authors:** Juntong Luo, Scott Sallinen, Matei Ripeanu  
**arXiv:** [2311.07016](https://arxiv.org/abs/2311.07016)  
**Date:** 2023-11-13  
**Summary page:** https://www.summarizepaper.com/en/paper/2311.07016v1/

## Key points

- Significant advancements in dynamic graph processing in recent years
- Ability to handle millions of edge changes per second
- Growing interest in tackling complex problems like the maximum flow problem
- Novel distributed algorithm for maximum flow on dynamic graphs using asynchronous vertex-centric abstraction
- Evaluation based on throughput, result latency, and solution stability
- Experimental setup using a commodity desktop machine with specific hardware specifications
- Evaluation using real-world timestamped graphs from various sources, including Ethereum transfers dataset
- Algorithm demonstrates efficient processing capabilities for fast-evolving graphs and promising results in handling large real-world dynamic graphs efficiently.

## Summary

, , , , 

In recent years, there have been significant advancements in dynamic graph processing, allowing for the analysis of highly dynamic graphs with rapid rates of change. This includes the ability to handle millions of edge changes per second. While existing solutions in this field have primarily focused on simpler algorithms like PageRank, breadth-first search, and connected components, there is a growing interest in tackling more complex problems such as the maximum flow problem in graph analytics. To address this challenge, a novel distributed algorithm for maximum flow on dynamic graphs has been proposed and implemented using an asynchronous vertex-centric abstraction. This algorithm has demonstrated efficient processing capabilities for both additions and deletions of vertices and edges on fast-evolving graphs. In addition to evaluating throughput, the algorithm's performance is also assessed based on two critical criteria for real-world applications: result latency and solution stability. For experimental purposes, a commodity desktop machine with a 16-core AMD Ryzen 9 5950x processor, 128GB of RAM, and an NVMe SSD is utilized. The experiments parallelize across all cores except for scalability testing. Real-world timestamped graphs from various sources are used for evaluation, including Ethereum transfers dataset restricted to transactions of at least 0.1 ETH. The evaluation covers aspects such as performance and scalability (including throughput sustainability and core scalability), effective resource utilization (improving response latency at lower event rates), and solution stability under extreme cases by selecting source and sink vertices based on popularity metrics like PageRank. Overall, the proposed algorithm shows promising results in handling large real-world dynamic graphs efficiently. By addressing the maximum flow problem with a distributed approach and leveraging asynchronous processing techniques, it opens up new possibilities for analyzing complex graph structures with high levels of dynamism.