Designing and analyzing highly scalable and reliable of full fledged parallel algorithm for computing strongly connected com-ponents to analyze social graphs

With the recent advent of Big Data, developing efficient distributed algorithms for computing Strongly Connected Components of a large dataset has received increasing interests. For example, social networks, information networks and communication networks such as the communities of people that have formed on those networks, what community a person belongs or finding cyclic de-pendencies in the graph.Apache Giraph is an open-source implementation of Google’s Pregel. It is an iterative and real-time graph processing engine designed to be scalable, fault tolerant and highly efficient. This framework provides an accurate platform for the development of parallel algorithms in a distributed environ-ment. It adopts a vertex-centric programming model inspired by Bulk Synchronous Parallel model. A strongly connected component is a maximal sub graph in which all vertices are reachable from every other vertex. Maximal means that it is the largest possible sub graph. It is not possible to find another vertex anywhere in the graph such that it could be added to the sub graph and all the verti-ces in the sub graph would still be connected. In a directed graph G, a pair of vertices u and v are said to be strongly connected to each other if there is a path in each direction between them. Here, we have implemented a parallel algorithm which is based on the new paradigm of graph decomposi-tion for computing strongly connected components. The final outcome mainly focuses on the reduc-tion of total communication costs.