Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.08350 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910602042015744 |
|---|---|
| author | Qian, Jingyun Hahn, Georg |
| author_facet | Qian, Jingyun Hahn, Georg |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08350 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An efficient heuristic for approximate maximum flow computations Qian, Jingyun Hahn, Georg Data Structures and Algorithms Methodology 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). |
| title | An efficient heuristic for approximate maximum flow computations |
| topic | Data Structures and Algorithms Methodology |
| url | https://arxiv.org/abs/2409.08350 |