Distributed Randomized Algorithms for PageRank Based on a Novel Interpretation

PageRank is a well-known centrality measure for the web used in search engines, representing the importance of each web page. In this paper, we develop a new class of distributed algorithms for the computation of PageRank. Each page computes its own PageRank value by interacting with pages connected over hyperlinks. Our approach is based on a simple but novel interpretation of PageRank. Gossip-type randomization is employed in the update schemes, and it is shown that the page selection need not be limited to the uniform distribution. In comparison with other existing techniques, significant advantages can be seen in their convergence performance as demonstrated via numerical examples.