FFSB: Fast Fibonacci Series-Based personalized PageRank on MPI

摘要

In this paper, we propose a fast MPI algorithm for Monte Carlo approximation PageRank vector of all the nodes in a graph, named Fast Fibonacci Series-Based Personal PageRank. In the latter paper we will call it FFSB algorithm for short. The basic ideal is very efficiently computing single random walks of a given length starting at each node in a graph. More precisely, we design FFSB, which given a graph G and a length λ, outputs a single random walk of length λ at each node in G. We will exhibit that the number of MPI iterations and machine time is better than the most efficient algorithm at present with machine time log2 λ (λ is the given walk length). The algorithm with the complexity 0.72022 × log2 λ × (g + max {L + 2 × o, 2 × g}) is optimal among a broad family of algorithms for the problem. Also the empirical evaluation on real-life graph data crawled from Sina micro blog demonstrates that our algorithm is significantly more efficient than all the existing candidates in production parallel programing environment MPI.