Please use this identifier to cite or link to this item: https://doi.org/10.1109/ICDCS.2011.62
Title: A MapReduce-based maximum-flow algorithm for large small-world network graphs
Authors: Halim, F. 
Yap, R.H.C. 
Wu, Y. 
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.

SCOPUSTM   
Citations

25
checked on Sep 20, 2019

WEB OF SCIENCETM
Citations

14
checked on Sep 13, 2019

Page view(s)

98
checked on Sep 9, 2019

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.