An efficient heuristic for approximate maximum flow computations

Abstract

Several concepts borrowed from graph theory are routinely used to better understand the inner workings of the (human) brain. To this end, a connectivity network of the brain is built first, which then allows one to assess quantities such as information flow and information routing via shortest path and maximum flow computations. Since brain networks typically contain several thousand nodes and edges, computational scaling is a key research area. In this contribution, we focus on approximate maximum flow computations in large brain networks. By combining graph partitioning with maximum flow computations, we propose a new approximation algorithm for the computation of the maximum flow with runtime O(|V||E|^2/k^2) compared to the usual runtime of O(|V||E|^2) for the Edmonds-Karp algorithm, where $V$ is the set of vertices, $E$ is the set of edges, and $k$ is the number of partitions. We assess both accuracy and runtime of the proposed algorithm on simulated graphs as well as on graphs downloaded from the Brain Networks Data Repository (https://networkrepository.com).