Computing Large Connected Components Using Map Reduce In Logarithmic Rounds

Graph structures are often used for representing data object and link between them in large datasets. Knowledge extraction from these data relies on finding the connected components within these graphs. Given a large graph G = (V,E), where V is the set of vertices and E is the set of edges, the problem is to find the connected components efficiently. The problem of finding the connected components is labeling each vertex with its graph component number. Recent works have been done to address this problem in MapReduce, but there always exists a trade-off between number of rounds and the communications per round. Let d be the diameter of the graph and n be the number of nodes in the largest component, all the prior implementations of this algorithm in MapReduce take linear, O(d), number of map reduce rounds and quadratic, O(n|V| +|E|), communications per round. The efficient algorithm proposed here finishes it in 2(log d) round and take (|V| + |E|) number of communications per round (where d = diameter of graph with V vertices and E edges, n = Number of nodes in largest component).