Computing Maximum Flow for Large Social Networks in MapReduce, seminar by Roland Yap, National University of Singapore

Abstract:

Maximum flow is used extensively in analyzing 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 of the speaker:

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.

 

Date/time: 
Monday, July 4, 2011, 16:00