Computing Large Connected Components Using Map Reduce in Logarithmic Rounds

摘要

Graph structures are often used for representingdata 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 offinding 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 atrade-off between number of rounds and the communications perround. Let d be the diameter of the graph and n be the numberof nodes in the largest component, all the prior implementationsof this algorithm in MapReduce take linear, O(d), number of mapreduce rounds and quadratic, O(n|V| +|E|), communications perround. The efficient algorithm proposed here finishes it in 2(log d) round and take (|V| + |E|) number of communications perround (where d = diameter of graph with V vertices and E edges, n = Number of nodes in largest component).