Optimized parallel algorithms for computing PageRank

PageRank is the measure of importance of a node within a set of nodes. It was originally developed for ranking pages in the web to provide relevant and latest search results for a user’s query. However, it is very useful and is still being used in many other domains such as social network analysis, spam detection and bibliometrics. Due to the continuous growth of real-world networks at a remarkable speed, massive graphs present a significant challenge for search engines. These graphs can contain millions or even billions of nodes and edges, which demands the need for efficient parallel algorithms. In this thesis, we design an efficient and optimized parallel algorithm for computing PageRank. There exists several good parallel algorithms for computing PageRank, however, they still suffer from communication overhead and load imbalance. Our algorithm provides improved and optimized communication strategy, better load balance and higher speed up. We developed and incorporated an efficient communication mechanism which reduces inter processor communication significantly. This has led to communication efficiency of 2-4-fold over the existing algorithm for the 7 graphs we have experimented with. We have also incorporated a parallel load balancing algorithm which provides faster partitioning mechanism and improved load balancing. Our experiments on several real-world datasets show that the proposed algorithm provides superior performance over the existing algorithms