University of Washington School of Public Health & Community Medicine
The authors present a scalable and fault-tolerant solution for the maximum clique problem based on the MapReduce framework. The key contribution that enables users to effectively use MapReduce is a recursive partitioning method that partitions the graph into several subgraphs of similar size. After partitioning, the maximum cliques of the different partitions can be computed independently, and the computation is sped up using a branch and bound method. Their experiments show that their approach leads to good scalability, which is unachievable by other partitioning methods since they result in partitions of different sizes and hence lead to load imbalance.