Please use this identifier to cite or link to this item:
|Title:||A MapReduce-based maximum-flow algorithm for large small-world network graphs||Authors:||Halim, F.
|Issue Date:||2011||Citation:||Halim, F., Yap, R.H.C., Wu, Y. (2011). A MapReduce-based maximum-flow algorithm for large small-world network graphs. Proceedings - International Conference on Distributed Computing Systems : 192-202. ScholarBank@NUS Repository. https://doi.org/10.1109/ICDCS.2011.62||Abstract:||Maximum-flow algorithms are used to find spam sites, build content voting system, discover communities, etc., on graphs from the Internet. Such graphs are now so large that they have outgrown conventional memory-resident algorithms. In this paper, we show how to effectively parallelize a max-flow algorithm based on the Ford-Fulkerson method on a cluster using the MapReduce framework. Our algorithm exploits the property that such graphs are small-world networks with low diameter and employs optimizations to improve the effectiveness of MapReduce and increase parallelism. We are able to compute max-flow on a subset of the Facebook social network graph with 411 million vertices and 31 billion edges using a cluster of 21 machines in reasonable time. © 2011 IEEE.||Source Title:||Proceedings - International Conference on Distributed Computing Systems||URI:||http://scholarbank.nus.edu.sg/handle/10635/43220||ISBN:||9780769543642||DOI:||10.1109/ICDCS.2011.62|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Sep 20, 2019
WEB OF SCIENCETM
checked on Sep 13, 2019
checked on Sep 9, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.