International Journal of

ADVANCED AND APPLIED SCIENCES

EISSN: 2313-3724, Print ISSN: 2313-626X

Frequency: 12
line decor
  
line decor

 Volume 11, Issue 7 (July 2024), Pages: 57-62

----------------------------------------------

 Original Research Paper

Rethinking the implementation and application of the Benczur-Karger minimum cuts algorithm

 Author(s): 

 Hanqin Gu *

 Affiliation(s):

 Western Reserve Academy, Hudson, USA

 Full text

  Full Text - PDF

 * Corresponding Author. 

  Corresponding author's ORCID profile: https://orcid.org/0009-0003-1609-2800

 Digital Object Identifier (DOI)

 https://doi.org/10.21833/ijaas.2024.07.007

 Abstract

In graph theory and network analysis, finding the minimum cut in a graph is a fundamental algorithmic challenge. This paper explores the development and application of Benczur-Karger’s minimum cut algorithms, focusing on the relationship between theoretical advancements and practical implementation. Despite the algorithm's advantages, there are challenges related to its implementation complexities and the effects of compression factor settings. To address these issues, this paper first implements Benczur-Karger’s minimum cuts algorithm in Python and discusses the implementation details. Additionally, we propose a new compression factor setting for Benczur-Karger’s minimum cuts algorithm and conduct an experiment with this new setting. The experimental results show that our proposed compression factor performs better than the original one. Finally, we discuss the application of Benczur-Karger’s minimum cuts algorithm in social network analysis, a field where its use has been limited. The code is available at https://github.com/HarleyHanqin/Modified_BK.

 © 2024 The Authors. Published by IASE.

 This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

 Keywords

 Minimum cut, Graph theory, Benczur-Karger algorithm, Compression factor, Social network analysis

 Article history

 Received 23 February 2024, Received in revised form 23 June 2024, Accepted 27 June 2024

 Acknowledgment 

No Acknowledgment.

 Compliance with ethical standards

 Ethical considerations

This study adheres to ethical standards and guidelines. The Facebook dataset used was anonymized to protect privacy, and no personal information was accessed. All algorithms were developed and tested ethically. The application in social network analysis was conducted using publicly available anonymized data, ensuring privacy and data security.

 Conflict of interest: The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

 Citation:

 Gu H (2024). Rethinking the implementation and application of the Benczur-Karger minimum cuts algorithm. International Journal of Advanced and Applied Sciences, 11(7): 57-62

 Permanent Link to this page

 Figures

 No Figure

 Tables

 Table 1 Table 2 

----------------------------------------------   

 References (26)

  1. Arora S, Rao S, and Vazirani U (2009). Expander flows, geometric embeddings and graph partitioning. Journal of the ACM, 56(2): 5. https://doi.org/10.1145/1502793.1502794   [Google Scholar]
  2. Batson J, Spielman DA, and Srivastava N (2014). Twice-Ramanujan sparsifiers. SIAM Journal on Computing, 41(6): 1704-1721. https://doi.org/10.1137/090772873   [Google Scholar]
  3. Becchetti L, Clementi AE, Natale E, Pasquale F, and Trevisan L (2020). Find your place: Simple distributed algorithms for community detection. SIAM Journal on Computing, 49(4): 821-864. https://doi.org/10.1137/19M1243026   [Google Scholar]
  4. Benczúr AA and Karger DR (1996). Approximating s-t minimum cuts in Õ(n2) time. In the Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA: 47-55.   [Google Scholar]
  5. Bulut M and Özcan E (2021). Optimization of electricity transmission by Ford–Fulkerson algorithm. Sustainable Energy, Grids and Networks, 28: 100544. https://doi.org/10.1016/j.segan.2021.100544   [Google Scholar]
  6. Cygan M, Komosa P, Lokshtanov D, Pilipczuk M, Pilipczuk M, Saurabh S, and Wahlström M (2020). Randomized contractions meet lean decompositions. ACM Transactions on Algorithms (TALG), 17(1): 1-30. https://doi.org/10.1145/3426738   [Google Scholar]
  7. Ford LR and Fulkerson DR (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8: 399-404. https://doi.org/10.4153/CJM-1956-045-5   [Google Scholar]
  8. Gayathri G, Mathew S, and Mordeson JN (2024). Max-flow min-cut theorem for directed fuzzy incidence networks. Journal of Applied Mathematics and Computing, 70(1): 149-173. https://doi.org/10.1007/s12190-023-01952-x   [Google Scholar]
  9. Henzinger M, Noe A, Schulz C, and Strash D (2018). Practical minimum cut algorithms. Journal of Experimental Algorithmics, 23: 1-22. https://doi.org/10.1145/3274662   [Google Scholar]
  10. Huang G, Li Y, Jameel S, Long Y, and Papanastasiou G (2024a). From explainable to interpretable deep learning for natural language processing in healthcare: How far from reality? Computational and Structural Biotechnology Journal, 24: 362-373. https://doi.org/10.1016/j.csbj.2024.05.004   [Google Scholar] PMid:38800693 PMCid:PMC11126530
  11. Huang G, Long Y, Luo C, Shen J, and Sun X (2024b). Prompting explicit and implicit knowledge for multi-hop question answering based on human reading process. Arxiv Preprint Arxiv:2402.19350. https://doi.org/10.48550/arXiv.2402.19350   [Google Scholar]
  12. Jin W, Zhao B, Yu H, Tao X, Yin R, and Liu G (2023). Improving embedded knowledge graph multi-hop question answering by introducing relational chain reasoning. Data Mining and Knowledge Discovery, 37(1): 255-288. https://doi.org/10.1007/s10618-022-00891-8   [Google Scholar]
  13. Karger DR (1994a). Random sampling in cut, flow, and network design problems. In the Proceedings of the 26th Annual ACM Symposium on Theory of Computing, Montreal, Canada: 648-657. https://doi.org/10.1145/195058.195422   [Google Scholar]
  14. Karger DR (1994b). Using randomized sparsification to approximate minimum cuts. In the Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, USA.   [Google Scholar]
  15. Karger DR (2000). Minimum cuts in near-linear time. Journal of the ACM, 47(1): 46-76. https://doi.org/10.1145/331605.331608   [Google Scholar]
  16. Karger DR and Stein C (1996). A new approach to the minimum cut problem. Journal of the ACM, 43(4): 601-640. https://doi.org/10.1145/234533.234534   [Google Scholar]
  17. Leskovec J and Mcauley J (2012). Learning to discover social circles in ego networks. In the Proceedings of Advances in Neural Information Processing Systems 25 (NIPS 2012), Red Hook, USA: 539–547.   [Google Scholar]
  18. Manoharan DS and Sathesh A (2020). Improved version of graph-cut algorithm for CT images of lung cancer with clinical property condition. Journal of Artificial Intelligence and Capsule Networks, 2(4): 201-206. https://doi.org/10.36548/jaicn.2020.4.002   [Google Scholar]
  19. Mukhopadhyay S and Nanongkai D (2020). Weighted min-cut: Sequential, cut-query, and streaming algorithms. In the Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Chicago, USA: 496-509. https://doi.org/10.1145/3357713.3384334   [Google Scholar] PMid:32629488
  20. Nagamochi H and Ibaraki T (1992a). Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics, 5(1): 54-66. https://doi.org/10.1137/0405004   [Google Scholar]
  21. Nagamochi H and Ibaraki T (1992b). A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(1): 583-596. https://doi.org/10.1007/BF01758778   [Google Scholar]
  22. Niazi M and Rahbar K (2024). Setting the regularization coefficient based on image energy in image segmentation using kernel graph cut algorithm. Journal of Electronic Imaging, 33(2): 023031. https://doi.org/10.1117/1.JEI.33.2.023031   [Google Scholar]
  23. Niu YF, Wan XY, Xu XZ, and Ding D (2020). Finding all multi-state minimal paths of a multi-state flow network via feasible circulations. Reliability Engineering & System Safety, 204: 107188. https://doi.org/10.1016/j.ress.2020.107188   [Google Scholar]
  24. Stoer M and Wagner F (1997). A simple min-cut algorithm. Journal of the ACM, 44(4): 585–591. https://doi.org/10.1145/263867.263872   [Google Scholar]
  25. Zhao P, Yu J, Zhang H, Qin Z, and Wang C (2020). How to securely outsource finding the min-cut of undirected edge-weighted graphs. IEEE Transactions on Information Forensics and Security, 15: 315-328. https://doi.org/10.1109/TIFS.2019.2922277   [Google Scholar]
  26. Zhou Y, Li Y, Zhang Z, Wang Y, Wang A, Fishman EK, Yuille AL, and Park S (2019). Hyper-pairing network for multi-phase pancreatic ductal adenocarcinoma segmentation. In the Medical Image Computing and Computer Assisted Intervention–22nd International Conference, Springer International Publishing, Shenzhen, China: 155-163. https://doi.org/10.1007/978-3-030-32245-8_18   [Google Scholar]