A map-reduce algorithm to find strongly connected components of directed graphs

Abstract Online social networks have become ubiquitous platforms, comprising intricately linked structures that reflect complex user interactions. Analyzing the interconnected component structure of these large directed graphs is pivotal for critical applications like viral marketing and contagion prediction. This paper presents a parallel algorithm to efficiently discover strongly connected components in massive social graphs by distributing computation across clustered servers. Our proposed distributed approach conducts localized connected component extraction during the Map phase. The merged aggregation in the Reduce phase then uncovers global maximum interconnected sets spanning the fragmented structures. We employ mathematical induction across Map-Reduce stages to demonstrate the algorithm’s correctness for obtaining exhaustive component enumeration across servers. Implementation and complexity analysis on synthetic benchmark graphs highlight significant efficiency gains, with the algorithm demonstrating near-linear speedup for increasing data-set and cluster sizes. The proposed technique advances the state-of-the-art for extracting strongly connected structures from colossal real-world social networks, enabling actionable insights around influence cascades and contagion pathways underlying these intricate linkage patterns.