Computing Maximum Flow for Large Social Networks in MapReduce - Talk by Prof. Roland Yap

Speaker: Roland Yap, National University of Singapore
Host: Laks Lakshmanan 

Title: Computing Maximum Flow for Large Social Networks in MapReduce

Abstract:

Maximum flow is used extensively in analysing social networks. For example, it is used to find spammers, protect content voting, discover communities, etc. in social networks. Real life social networks can be very large and thus memory resident algorithms may not be applicable. We develop distributed algorithms which are suitable for clusters and cloud computing using the Google MapReduce framework. Our maximum flow algorithm has optimizations which increase parallelism while reducing overheads in a MapReduce setting. We are able to compute maximum flow on a large social network with around 400 million vertices in reasonable time using this approach.

Bio:

Roland Yap is an associate professor in the School of Computing, National University of Singapore. He has worked extensively on Constraint Programming and Constraint Logic Programming. His research interests are in constraint programming, logic programming, programming languages, systems security and database. More recently he is interested in distributed systems and social computing which this talk will focus on.