A Survey on Personalized PageRank Computation Algorithms <s> D. CHARACTERISTICS OF PERSONALIZED PAGERANK <s> Recent web search techniques augment traditional text matching with a global notion of "importance" based on the linkage structure of the web, such as in Google's PageRank algorithm. For more refined searches, this global notion of importance can be specialized to create personalized views of importance--for example, importance scores can be biased according to a user-specified set of initially-interesting pages. Computing and storing all possible personalized views in advance is impractical, as is computing personalized views at query time, since the computation of each view requires an iterative computation over the web graph. We present new graph-theoretical results, and a new technique based on these results, that encode personalized views as partial vectors. Partial vectors are shared across multiple personalized views, and their computation and storage costs scale well with the number of views. Our approach enables incremental computation, so that the construction of personalized views from partial vectors is practical at query time. We present efficient dynamic programming algorithms for computing partial vectors, an algorithm for constructing personalized views from partial vectors, and experimental results demonstrating the effectiveness and scalability of our techniques. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. CHARACTERISTICS OF PERSONALIZED PAGERANK <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> BIB002 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. CHARACTERISTICS OF PERSONALIZED PAGERANK <s> How closely related are two nodes in a graph? How to compute this score quickly, on huge, disk-resident, real graphs? Random walk with restart (RWR) provides a good relevance score between two nodes in a weighted graph, and it has been successfully used in numerous settings, like automatic captioning of images, generalizations to the "connection subgraphs", personalized PageRank, and many more. However, the straightforward implementations of RWR do not scale for large graphs, requiring either quadratic space and cubic pre-computation time, or slow response time on queries. We propose fast solutions to this problem. The heart of our approach is to exploit two important properties shared by many real graphs: (a) linear correlations and (b) block- wise, community-like structure. We exploit the linearity by using low-rank matrix approximation, and the community structure by graph partitioning, followed by the Sherman- Morrison lemma for matrix inversion. Experimental results on the Corel image and the DBLP dabasets demonstrate that our proposed methods achieve significant savings over the straightforward implementations: they can save several orders of magnitude in pre-computation and storage cost, and they achieve up to 150x speed up with 90%+ quality preservation. <s> BIB003 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. CHARACTERISTICS OF PERSONALIZED PAGERANK <s> Why doesn't your home page appear on the first page of search results, even when you query your own name? How do other web pages always appear at the top? What creates these powerful rankings? And how? The first book ever about the science of web page rankings, Google's PageRank and Beyond supplies the answers to these and other questions and more. The book serves two very different audiences: the curious science reader and the technical computational reader. The chapters build in mathematical sophistication, so that the first five are accessible to the general academic reader. While other chapters are much more mathematical in nature, each one contains something for both audiences. For example, the authors include entertaining asides such as how search engines make money and how the Great Firewall of China influences research. The book includes an extensive background chapter designed to help readers learn more about the mathematics of search engines, and it contains several MATLAB codes and links to sample web data sets. The philosophy throughout is to encourage readers to experiment with the ideas and algorithms in the text. Any business seriously interested in improving its rankings in the major search engines can benefit from the clear examples, sample code, and list of resources provided. Many illustrative examples and entertaining asides MATLAB code Accessible and informal style Complete and self-contained section for mathematics review <s> BIB004 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. CHARACTERISTICS OF PERSONALIZED PAGERANK <s> Link prediction, personalized graph search, fraud detection, and many such graph mining problems revolve around the computation of the most "similar" k nodes to a given query node. One widely used class of similarity measures is based on random walks on graphs, e.g., personalized pagerank, hitting and commute times, and simrank. There are two fundamental problems associated with these measures. First, existing online algorithms typically examine the local neighborhood of the query node which can become significantly slower whenever high-degree nodes are encountered (a common phenomenon in real-world graphs). We prove that turning high degree nodes into sinks results in only a small approximation error, while greatly improving running times. The second problem is that of computing similarities at query time when the graph is too large to be memory-resident. The obvious solution is to split the graph into clusters of nodes and store each cluster on a disk page; ideally random walks will rarely cross cluster boundaries and cause page-faults. Our contributions here are twofold: (a) we present an efficient deterministic algorithm to find the k closest neighbors (in terms of personalized pagerank) of any query node in such a clustered graph, and (b) we develop a clustering algorithm (RWDISK) that uses only sequential sweeps over data files. Empirical results on several large publicly available graphs like DBLP, Citeseer and Live-Journal (~ 90 M edges) demonstrate that turning high degree nodes into sinks not only improves running time of RWDISK by a factor of 3 but also boosts link prediction accuracy by a factor of 4 on average. We also show that RWDISK returns more desirable (high conductance and small size) clusters than the popular clustering algorithm METIS, while requiring much less memory. Finally our deterministic algorithm for computing nearest neighbors incurs far fewer page-faults (factor of 5) than actually simulating random walks. <s> BIB005
PPR has some useful characteristics. The most important and frequently utilized ones are the linearity and the decomposition theorem BIB001 . The following equation represents the linearity: It means that we can compute PPR w 1 − → u + w 2 − → v when we know PPR − → u and PPR − → v without solving a linear equation. For example, if PPR (0, 0, 0, 1, 0) T and PPR (1, 0, 0, 0, 0) T are known, we can compute PPR vector of any linear combination of (0, 0, 0, 1, 0) T and (1, 0, 0, 0, 0) T such as (0.2, 0, 0, 0.8, 0) T via weighted summation of the known PPR vectors. This property is utilized by several optimization methods such as Bookmark Coloring Algorithm (Section 4. C). The decomposition theorem is also an interesting property that is closely related to the graph structure. The following equation represents the decomposition theorem: It means that we can compute PPR − → v 1 if we know all PPR vectors from the out neighbor nodes of n 1 . Assume that we want to compute PPR − → v 1 , and we know PPR of all out neighbor nodes. Then, in the example graph in Fig. 1 , the following equation holds according to the decomposition theorem: Therefore, we can compute PPR − → v 1 as the summation of vectors if we know the vectors corresponding to Since solving linear equation is an expensive task, utilizing the above properties is one of major approaches for PPR computations. Another important property of PPR is that it can be rewritten in summation form as follows: This interpretation of PPR can be seen as iterative summation of the state vectors for each step of a random walker that follows the transition behavior of PPR. If we assume that the initial state r (0) = s , then the state vector of the 1 st step r BIB003 can be computed as (1−c) s + cP s by equation (4). The state vector of the 2 nd step can be obtained in the same fashion as follows: r If we repeat the former process infinitely, we can eventually reach the equation r and the equation can be rewritten as the summation form of the equation (8). This property is utilized in several important methods including sampling-based algorithms  , BIB002 . Another property is weighted symmetry. Basically, PPR is not a symmetric measure unlike other widely used similarity measures such as Euclidean distance. That is, we cannot say that the proximity of node i from node j is equal to that of node j from node i in terms of PPR. In other words, we cannot However, PPR also has the property of partial symmetry when the given graph is an undirected graph. Equation (9) shows the property BIB005 : Though it is not a perfect symmetric property, it can be utilized for optimization by avoiding repetitive computations. If we have the vector PPR − → v j beforehand, we can get the PPR − → v k [j] for any node k by using the property. PPR also can be viewed as a solution of the linear system (I − cP) r = (1 − c) s. The system matrix (I − cP) of the above linear system has the following properties BIB004 : The above properties guarantee the existence and uniqueness of the solution of the given linear system. They also assure that the solution can be computed using iterative methods for solving linear equations such as the Jacobi method.