SYSTEM AND METHOD FOR FINDING CONNECTED COMPONENTS IN A LARGE-SCALE GRAPH

摘要

An improved system and method for finding connected components in a large-scale graph is provided. In a map-reduce framework, subsets of a collection of edges for unique vertices may be distributed to several mappers. Connected components of subgraphs represented by each subset of edges may be computed by each mapper. Then the sets of edges for connected components of subgraphs may be sorted by vertex. The sets of edges representing connected components of subgraphs may be distributed to one or more reducers to find maximal sets of weakly connected components of the large-scale graph. The sorted sets of edges for each vertex representing the maximal sets of connected components for subgraphs may be merged by a reducer to identify maximal sets of connected components of a graph, and the maximal sets of connected components of a graph may be output.