MapReduce Preprocess of Big Graphs for Rapid Connected Components Detection

Abstract

Paramount and vast applications such as social networks deal with big graphs. For this reason, big graph analysis and processing is currently a necessity. Detection of connected components is one of the analysis of graphs which is utilized as a sub-part in many graph algorithms, such as clustering. The goal of this paper is to propose a parallel preprocess algorithm with MapReduce to decrease graph volume for rapid detection of connected components. Suggested method is able to lessen the volume up to more than 99% quickly by just two rounds of MapReduce. Our evaluation shows that the combination of the preprocess with detection of connected components has a significant impact on: reduction of execution time up to 7 times, decrease in data transmission of processing nodes in network and MapReduce rounds.