FAST AND SCALABLE CONNECTED COMPONENT COMPUTATION

摘要

Finding connected components in a graph is a well-known problem in a wide variety of application areas such as social network analysis, data mining, image processing, and etc. We present an efficient and scalable approach to find all the connected components in a given graph. We compare our approach with the state-of-the-art on a real-world graph. We also demonstrate the viability of our approach on a massive graph with ˜6B nodes and ˜92B edges on an 80-node Hadoop cluster. To the best of our knowledge, this is the largest graph publicly used in such an experiment.

主权项

1. A system for finding connected components in a graph comprising:
an input device that receives a list of edges in the graph; a distributed processing arrangement coupled to the input device, the distributed processing arrangement including a plurality of processors that execute, in a distributed fashion, an iterative process that generates adjacency for each known node in the graph; the distributed processing arrangement further deduplicates:
wherein the output of the deduplicating comprises a mapping from each node in the graph to a corresponding component identifier.