Document Open Access Logo

Efficiently Computing Maximum Flows in Scale-Free Networks

Authors Thomas Bläsius, Tobias Friedrich, Christopher Weyand

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.21.pdf
  • Filesize: 0.73 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Bläsius
  • Karlsruhe Institute of Technology, Germany
Tobias Friedrich
  • Hasso Plattner Institute, Universität Potsdam, Germany
Christopher Weyand
  • Karlsruhe Institute of Technology, Germany

Cite As Get BibTex

Thomas Bläsius, Tobias Friedrich, and Christopher Weyand. Efficiently Computing Maximum Flows in Scale-Free Networks. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.21

Abstract

We study the maximum-flow/minimum-cut problem on scale-free networks, i.e., graphs whose degree distribution follows a power-law. We propose a simple algorithm that capitalizes on the fact that often only a small fraction of such a network is relevant for the flow. At its core, our algorithm augments Dinitz’s algorithm with a balanced bidirectional search. Our experiments on a scale-free random network model indicate sublinear run time. On scale-free real-world networks, we outperform the commonly used highest-label Push-Relabel implementation by up to two orders of magnitude. Compared to Dinitz’s original algorithm, our modifications reduce the search space, e.g., by a factor of 275 on an autonomous systems graph.
Beyond these good run times, our algorithm has an additional advantage compared to Push-Relabel. The latter computes a preflow, which makes the extraction of a minimum cut potentially more difficult. This is relevant, for example, for the computation of Gomory-Hu trees. On a social network with 70000 nodes, our algorithm computes the Gomory-Hu tree in 3 seconds compared to 12 minutes when using Push-Relabel.

Subject Classification

ACM Subject Classification
  • Theory of computation → Network flows
Keywords
  • graphs
  • flow
  • network
  • scale-free

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Ravindra K. Ahuja, Murali Kodialam, Ajay K. Mishra, and James B. Orlin. Computational investigations of maximum flow algorithms. European Journal of Operational Research, 97(3):509-542, 1997. URL: https://doi.org/10.1016/S0377-2217(96)00269-X.
  2. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network flows: Theory, algorithms and applications. Prentice-Hall, Inc., 1993. Google Scholar
  3. Albert-László Barabási. Network science. Cambridge university press, 2016. Google Scholar
  4. Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1-21:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.21.
  5. Thomas Bläsius, Tobias Friedrich, and Christopher Weyand. Efficiently computing maximum flows in scale-free networks. CoRR, abs/2009.09678, 2020. URL: http://arxiv.org/abs/2009.09678.
  6. Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, and Marianne Thieffry. Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.20.
  7. Michele Borassi and Emanuele Natale. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. In 24th Annual European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:18. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.20.
  8. Y. Boykov and V. Kolmogorov. An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(9):1124-1137, 2004. URL: https://doi.org/10.1109/TPAMI.2004.60.
  9. Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. Theoretical Computer Science, 760:35-54, 2019. URL: https://doi.org/10.1016/j.tcs.2018.08.014.
  10. Bala G. Chandran and Dorit S. Hochbaum. A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem. Operations Research, 57(2):358-376, 2009. Google Scholar
  11. B. V. Cherkassky and A. V. Goldberg. On implementing the pushemdashrelabel method for the maximum flow problem. Algorithmica, 19(4):390-410, 1997. URL: https://doi.org/10.1007/pl00009180.
  12. U. Derigs and W. Meier. Implementing Goldberg’s max-flow-algorithm — A computational investigation. Zeitschrift für Operations Research, 33(6):383-403, 1989. URL: https://doi.org/10.1007/BF01415937.
  13. Yefim Dinitz. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Mathematics Doklady, 11:1277-1280, 1970. Google Scholar
  14. Shimon Even and R. Endre Tarjan. Network flow and testing graph connectivity. SIAM Journal on Computing, 4(4):507-518, 1975. URL: https://doi.org/10.1137/0204043.
  15. Gary William Flake, Robert E. Tarjan, and Kostas Tsioutsiouliklis. Graph clustering and minimum cut trees. Internet Mathematics, 1(4):385-408, 2004. URL: https://doi.org/10.1080/15427951.2004.10129093.
  16. L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399–404, 1956. URL: https://doi.org/10.4153/CJM-1956-045-5.
  17. Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Robert E. Tarjan, and Renato F. Werneck. Maximum Flows by Incremental Breadth-First Search. In 19th Annual European Symposium on Algorithms (ESA 2011), Lecture Notes in Computer Science, pages 457-468. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-23719-5_39.
  18. Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. URL: https://doi.org/10.1145/48014.61051.
  19. Andrew V. Goldberg and Robert E. Tarjan. Efficient maximum flow algorithms. Commun. ACM, 57(8):82-89, 2014. URL: https://doi.org/10.1145/2628036.
  20. R. E. Gomory and T. C. Hu. Multi-Terminal Network Flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961. Google Scholar
  21. Dan Gusfield. Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 19(1):143-155, 1990. URL: https://doi.org/10.1137/0219009.
  22. Felix Halim, Roland H.C. Yap, and Yongzheng Wu. A MapReduce-Based Maximum-Flow Algorithm for Large Small-World Network Graphs. In 2011 31st International Conference on Distributed Computing Systems, pages 192-202, 2011. ISSN: 1063-6927. URL: https://doi.org/10.1109/ICDCS.2011.62.
  23. Dorit S. Hochbaum. The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Operations Research, 56(4):992-1009, August 2008. URL: https://doi.org/10.1287/opre.1080.0524.
  24. Alexander V. Karzanov. On finding a maximum flow in a network with special structure and some applications. Matematicheskie Voprosy Upravleniya Proizvodstvom, 5:81-94, 1973. Google Scholar
  25. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Physical Review E, 82(3), 2010. URL: https://doi.org/10.1103/physreve.82.036106.
  26. Kevin Lang. Finding good nearly balanced cuts in power law graphs. Technical Report YRL-2004-036, Yahoo! Research Labs, 2004. Google Scholar
  27. Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1):29-123, 2009. URL: https://doi.org/10.1080/15427951.2009.10129177.
  28. Lorenzo Orecchia and Zeyuan Allen Zhu. Flow-based algorithms for local graph clustering. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2014. URL: https://doi.org/10.1137/1.9781611973402.94.
  29. Satu Elisa Schaeffer. Graph clustering. Computer Science Review, 1(1):27-64, 2007. URL: https://doi.org/10.1016/j.cosrev.2007.05.001.
  30. Boris Schäling. The boost C++ libraries. Boris Schäling, 2011. URL: https://theboostcpplibraries.com/.
  31. S.-W. Son, H. Jeong, and J. D. Noh. Random field ising model and community structure in complex networks. The European Physical Journal B, 50(3):431-437, 2006. URL: https://doi.org/10.1140/epjb/e2006-00155-4.
  32. Tanmay Verma and Dhruv Batra. MaxFlow revisited: An empirical comparison of maxflow algorithms for dense vision problems. In Procedings of the British Machine Vision Conference 2012. British Machine Vision Association, 2012. URL: https://doi.org/10.5244/c.26.61.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact