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
Source: 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

20
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

10
checked on Nov 20, 2017

Page view(s)

73
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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