A Survey on Personalized PageRank Computation Algorithms <s> C. BOOKMARK COLORING ALGORITHM <s> Graph conductance queries, also known as personalized PageRank and related to random walks with restarts, were originally proposed to assign a hyperlink-based prestige score to Web pages. More general forms of such queries are also very useful for ranking in entity-relation (ER) graphs used to represent relational, XML and hypertext data. Evaluation of PageRank usually involves a global eigen computation. If the graph is even moderately large, interactive response times may not be possible. Recently, the need for interactive PageRank evaluation has increased. The graph may be fully known only when the query is submitted. Browsing actions of the user may change some inputs to the PageRank computation dynamically. In this paper, we describe a system that analyzes query workloads and the ER graph, invests in limited offline indexing, and exploits those indices to achieve essentially constant-time query processing, even as the graph size scales. Our techniques--data and query statistics collection, index selection and materialization, and query-time index exploitation--have parallels in the extensive relational query optimization literature, but is applied to supporting novel graph data repositories. We report on experiments with five temporal snapshots of the CiteSeer ER graph having 74---702 thousand entity nodes, 0.17---1.16 million word nodes, 0.29---3.26 million edges between entities, and 3.29---32.8 million edges between words and entities. We also used two million actual queries from CiteSeer's logs. Queries run 3---4 orders of magnitude faster than whole-graph PageRank, the gap growing with graph size. Index size is smaller than a text index. Ranking accuracy is 94---98% with reference to whole-graph PageRank. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> C. BOOKMARK COLORING ALGORITHM <s> Graphs can be found in applications like social networks, bibliographic networks, and biological databases. Understanding the relationship, or links, among graph nodes enables applications such as link prediction, recommendation, and spam detection. In this paper, we propose link-based similarity join (LS-join), which extends the similarity join operator to link-based measures. Given two sets of nodes in a graph, the LS-join returns all pairs of nodes that are highly similar to each other, with respect to an e-function. The e-function generalizes common measures like Personalized PageRank (PPR) and SimRank (SR). We study an efficient LS-join algorithm on a large graph. We further improve our solutions for PPR and SR, which involve expensive randomwalk operations. We validate our solutions by performing extensive experiments on three real graph datasets. <s> BIB002 </s> A Survey on Personalized PageRank Computation Algorithms <s> C. BOOKMARK COLORING ALGORITHM <s> We propose and analyze two algorithms for maintaining approximate Personalized PageRank (PPR) vectors on a dynamic graph, where edges are added or deleted. Our algorithms are natural dynamic versions of two known local variations of power iteration. One, Forward Push, propagates probability mass forwards along edges from a source node, while the other, Reverse Push, propagates local changes backwards along edges from a target. In both variations, we maintain an invariant between two vectors, and when an edge is updated, our algorithm first modifies the vectors to restore the invariant, then performs any needed local push operations to restore accuracy. For Reverse Push, we prove that for an arbitrary directed graph in a random edge model, or for an arbitrary undirected graph, given a uniformly random target node t, the cost to maintain a PPR vector to t of additive error e as k edges are updated is O(k + d/e, where d is the average degree of the graph. This is O(1) work per update, plus the cost of computing a reverse vector once on a static graph. For Forward Push, we show that on an arbitrary undirected graph, given a uniformly random start node s, the cost to maintain a PPR vector from s of degree-normalized error e as k edges are updated is O(k + 1/e, which is again O(1) per update plus the cost of computing a PPR vector once on a static graph. <s> BIB003
Bookmark Coloring algorithm (BCA)  is also an iterative algorithm similar to the power iteration. However, BCA asynchronously updates PPR vectors while the power iteration does it in a synchronous manner. BCA utilize equation BIB002 in section 2.D. With the interpretation, PPR can be computed in a cumulative way. The basic BCA for computing PPR( v i ) can be interpreted using a recursive function BC (j, w, c). Though the above algorithm is defined as a recursive function, BCA can also be implemented using a queue data structure  . This scheme provides a more efficient implementation utilizing sparsity than matrix-based algorithms such as the power iteration. This version of BCA is also called ForwardPush algorithm BIB003 . It is possible to compute PPR − → v i [j] for the given target node j and every source node i by reversing the weight propagation direction from the above algorithm. The reversed one is called ReversePush algorithm BIB003 . Several recent studies combines the Push scheme and Monte-Carlo sampling to improve query processing time. These algorithms are discussed in section 4.E and 4.F. BCA gradually completes the summation that is defined in equation (8) using repeated asynchronous updates. It can also be viewed as an asynchronous version of the power iteration, and its convergence rate is also identical to the power iteration. That means that BCA requires large numbers of iterations since the basic algorithm cannot benefit from advanced algorithms such as the GMRES in terms of the number of iterations. If some PPR( v h )s are known, BCA can be computed in a more efficient way utilizing the decomposition theorem. We stop the recursive calls and directly construct the return value using known vectors. HubRank BIB001 is a revised version of BCA with a smart hub selection algorithm and approximation. It provides better performance in terms of the query processing time; however, it still requires a long precomputation time. In an empirical evaluation, it takes over 20 hours to compute PPR vectors for the selected hubs to achieve reasonable query response time.