Big Data Technologies and Applications. 7th International Conference, BDTA 2016, Seoul, South Korea, November 17–18, 2016, Proceedings

Research Article

Max-flow Min-cut Algorithm in Spark with Application to Road Networks

Download
973 downloads
  • @INPROCEEDINGS{10.1007/978-3-319-58967-1_2,
        author={Varun Ramesh and Shivanee Nagarajan and Saswati Mukherjee},
        title={Max-flow Min-cut Algorithm in Spark with Application to Road Networks},
        proceedings={Big Data Technologies and Applications. 7th International Conference, BDTA  2016, Seoul, South Korea, November 17--18, 2016, Proceedings},
        proceedings_a={BDTA},
        year={2017},
        month={6},
        keywords={},
        doi={10.1007/978-3-319-58967-1_2}
    }
    
  • Varun Ramesh
    Shivanee Nagarajan
    Saswati Mukherjee
    Year: 2017
    Max-flow Min-cut Algorithm in Spark with Application to Road Networks
    BDTA
    Springer
    DOI: 10.1007/978-3-319-58967-1_2
Varun Ramesh1,*, Shivanee Nagarajan1,*, Saswati Mukherjee1,*
  • 1: Anna University
*Contact email: varun.ceg.95@gmail.com, shivanee.ceg@gmail.com, msaswati@auist.net

Abstract

The max-flow min-cut problem is one of the most explored and studied problems in the area of combinatorial algorithms and optimization. In this paper, we solve the max-flow min-cut problem on large random graphs with log-normal distribution of outdegrees using the distributed Edmonds-Karp algorithm. The algorithm is implemented on a cluster using Spark. We compare the runtime between a single machine implementation and cluster implementation and analyze the impact of communication cost on runtime. In our experiments, we observe that the practical value recorded across various graphs is much lesser than the theoretical estimations primarily due to smaller diameter of the graph. Additionally, we extend this model theoretically on a large urban road network to evaluate the minimum number of sensors required for surveillance of the entire network. To validate the feasibility of this theoretical extension, we tested the model with a large log-normal graph with 1.1 million edges and obtained a max-flow value of 54, which implies that the minimum-cut set of the graph consists of 54 edges. This is a reasonable set of edges to place the sensors compared to the total number of edges. We believe that our approach can enhance the safety of road networks throughout the world.