A Survey on Personalized PageRank Computation Algorithms <s> E. MONTE-CARLO SAMPLING-BASED METHODS <s> PageRank is one of the principle criteria according to which Google ranks Web pages. PageRank can be interpreted as a frequency of visiting a Web page by a random surfer and thus it reflects the popularity of a Web page. Google computes the PageRank using the power iteration method which requires about one week of intensive computations. In the present work we propose and analyze Monte Carlo type methods for the PageRank computation. There are several advantages of the probabilistic Monte Carlo methods over the deterministic power iteration method: Monte Carlo methods provide good estimation of the PageRank for relatively important pages already after one iteration; Monte Carlo methods have natural parallel implementation; and finally, Monte Carlo methods allow to perform continuous update of the PageRank as the structure of the Web changes. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. MONTE-CARLO SAMPLING-BASED METHODS <s> In this paper, we design a fast MapReduce algorithm for Monte Carlo approximation of personalized PageRank vectors of all the nodes in a graph. The basic idea is very efficiently doing single random walks of a given length starting at each node in the graph. More precisely, we design a MapReduce algorithm, which given a graph G and a length », outputs a single random walk of length » starting at each node in G. We will show that the number of MapReduce iterations used by our algorithm is optimal among a broad family of algorithms for the problem, and its I/O efficiency is much better than the existing candidates. We will then show how we can use this algorithm to very efficiently approximate all the personalized PageRank vectors. Our empirical evaluation on real-life graph data and in production MapReduce environment shows that our algorithm is significantly more efficient than all the existing algorithms in the MapReduce setting. <s> BIB002 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. MONTE-CARLO SAMPLING-BASED METHODS <s> We propose a new algorithm, FAST-PPR, for computing personalized PageRank: given start node s and target node t in a directed graph, and given a threshold δ, it computes the Personalized PageRank π_s(t) from s to t, guaranteeing that the relative error is small as long πs(t) > δ. Existing algorithms for this problem have a running-time of Ω(1/δ in comparison, FAST-PPR has a provable average running-time guarantee of O(√d/δ) (where d is the average in-degree of the graph). This is a significant improvement, since δ is often O(1/n) (where n is the number of nodes) for applications. We also complement the algorithm with an Ω(1/√δ) lower bound for PageRank estimation, showing that the dependence on δ cannot be improved. We perform a detailed empirical study on numerous massive graphs, showing that FAST-PPR dramatically outperforms existing algorithms. For example, on the 2010 Twitter graph with 1.5 billion edges, for target nodes sampled by popularity, FAST-PPR has a 20 factor speedup over the state of the art. Furthermore, an enhanced version of FAST-PPR has a 160 factor speedup on the Twitter graph, and is at least 20 times faster on all our candidate graphs. <s> BIB003 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. MONTE-CARLO SAMPLING-BASED METHODS <s> Most methods for Personalized PageRank (PPR) precompute and store all accurate PPR vectors, and at query time, return the ones of interest directly. However, the storage and computation of all accurate PPR vectors can be prohibitive for large graphs, especially in caching them in memory for real-time online querying. In this paper, we propose a distributed framework that strikes a better balance between offline indexing and online querying. The offline indexing attains a fingerprint of the PPR vector of each vertex by performing billions of ``short'' random walks in parallel across a cluster of machines. We prove that our indexing method has an exponential convergence, achieving the same precision with previous methods using a much smaller number of random walks. At query time, the new PPR vector is composed by a linear combination of related fingerprints, in a highly efficient vertex-centric decomposition manner. Interestingly, the resulting PPR vector is much more accurate than its offline counterpart because it actually uses more random walks in its estimation. More importantly, we show that such decomposition for a batch of queries can be very efficiently processed using a shared decomposition. Our implementation, PowerWalk, takes advantage of advanced distributed graph engines and it outperforms the state-of-the-art algorithms by orders of magnitude. Particularly, it responses to tens of thousands of queries on graphs with billions of edges in just a few seconds. <s> BIB004
Monte-Carlo sampling is one traditional method to solve problems with high complexity. It avoids the complexity by deriving the solutions using samples that are produced with a large number of trials. This method can be easily applied to the Personalized PageRank problem. In this case, the sample database is a collection of random walk traces, that is, a set of node sequences (which are called ''fingerprints''). There are two Monte-Carlo methods for the Personalized PageRank problem: the MC end-point and the MC complete path BIB001 . The MC end-point method uses the summation form (equation (8)). If we know P k s with enough depth k, We can compute PPR ( s) using simple algebraic operations, and P k s can be approximated by counting the end points of the sample traces with length k from the starting node that is specified within s. While the MC end-point uses only the end point of each trace, the MC complete path method uses every node within traces. Monte-Carlo scheme is mainly utilized in the fully Personalized PageRank problem since it does not requires a square space to store all computed PPR vectors. One of most important algorithms in this category is doubling BIB002 . It populates long traces by concatenating short traces, and the procedure is defined using MapReduce framework. In the empirical evaluation, the doubling algorithm performs approximately 8 times faster than rounding (section 4.E). In spite of its impressive enhancement, it does not strictly guarantee the error bound because of the substantial limitation of sampling method, and it is hard to say that it obviously outperforms other advanced approaches considering that rounding is a relatively underperforming algorithm that has an identical convergence rate to the power iteration. One of recent studies, FAST-PPR, also adopts the Monte-Carlo scheme. It solves point-to-point Personalized PageRank problem that computes PPR − → v i [j] when the graph and two nodes (source and sink) are given BIB003 . It utilizes two sided random walk samples (from the source and sink) at the same time. It can be viewed as the combination of Monte-Carlo sampling and ReversePush that is discussed in section 4.C. As a result, it achieves impressive performance. However, it is unclear how to utilize the point-to-point PPR in the applications since the entries of PPR vectors are relative values. Another recently proposed method, PowerWalk BIB004 is also a sampling-based algorithm. To produce accurate answers, it process queries in iterative manners based on the sampled information.