A Survey on Personalized PageRank Computation Algorithms <s> F. OTHERS <s> A local partitioning algorithm finds a set with small conductance near a specified seed vertex. In this paper, we present a generalization of a local partitioning algorithm for undirected graphs to strongly connected directed graphs. In particular, we prove that by computing a personalized PageRank vector in a directed graph, starting from a single seed vertex within a set S that has conductance at most α, and by performing a sweep over that vector, we can obtain a set of vertices S′ with conductance ΦM(S′) = O(√α log |S|). Here, the conductance function ΦM is defined in terms of the stationary distribution of a random walk in the directed graph. In addition, we describe how this algorithm may be applied to the PageRank Markov chain of an arbitrary directed graph, which provides a way to partition directed graphs that are not strongly connected. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> F. OTHERS <s> Web page prefetching techniques are used to address the access latency problem of the Internet. To perform successful prefetching, we must be able to predict the next set of pages that will be accessed by users. The PageRank algorithm used by Google is able to compute the popularity of a set of Web pages based on their link structure. In this paper, a novel PageRank-like algorithm is proposed for conducting Web page prediction. Two biasing factors are adopted to personalize PageRank, so that it favors the pages that are more important to users. One factor is the length of time spent on visiting a page and the other is the frequency that a page was visited. The experiments conducted show that using these two factors simultaneously to bias PageRank results in more accurate Web page prediction than other methods that use only one of these two factors. <s> BIB002 </s> A Survey on Personalized PageRank Computation Algorithms <s> F. OTHERS <s> Extractors and taggers turn unstructured text into entity-relation(ER) graphs where nodes are entities (email, paper, person,conference, company) and edges are relations (wrote, cited,works-for). Typed proximity search of the form type=personNEAR company~"IBM", paper~"XML" is an increasingly usefulsearch paradigm in ER graphs. Proximity search implementations either perform a Pagerank-like computation at query time, which is slow, or precompute, store and combine per-word Pageranks, which can be very expensive in terms of preprocessing time and space. We present HubRank, a new system for fast, dynamic, space-efficient proximity searches in ER graphs. During preprocessing, HubRank computesand indexes certain "sketchy" random walk fingerprints for a small fraction of nodes, carefully chosen using query log statistics. At query time, a small "active" subgraph is identified, bordered bynodes with indexed fingerprints. These fingerprints are adaptively loaded to various resolutions to form approximate personalized Pagerank vectors (PPVs). PPVs at remaining active nodes are now computed iteratively. We report on experiments with CiteSeer's ER graph and millions of real Cite Seer queries. Some representative numbers follow. On our testbed, HubRank preprocesses and indexes 52 times faster than whole-vocabulary PPV computation. A text index occupies 56 MB. Whole-vocabulary PPVs would consume 102GB. If PPVs are truncated to 56 MB, precision compared to true Pagerank drops to 0.55; incontrast, HubRank has precision 0.91 at 63MB. HubRank's average querytime is 200-300 milliseconds; query-time Pagerank computation takes 11 seconds on average. <s> BIB003 </s> A Survey on Personalized PageRank Computation Algorithms <s> F. OTHERS <s> This paper looks inside FolkRank, one of the well-known folksonomy-based algorithms, to present its fundamental properties and promising possibilities for improving performance in tag recommendations. Moreover, we introduce a new way to compute a differential approach in FolkRank by representing it as a linear combination of the personalized PageRank vectors. By the linear combination, we present FolkRank's probabilistic interpretation that grasps how FolkRank works on a folksonomy graph in terms of the random surfer model. We also propose new FolkRank-like methods for tag recommendations to efficiently compute tags' rankings and thus reduce expensive computational cost of FolkRank. We show that the FolkRank approaches are feasible to recommend tags in real-time scenarios as well. The experimental evaluations show that the proposed methods provide fast tag recommendations with reasonable quality, as compared to FolkRank. Additionally, we discuss the diversity of the top n tags recommended by FolkRank and its variants. <s> BIB004 </s> A Survey on Personalized PageRank Computation Algorithms <s> F. OTHERS <s> Many information-management tasks (including classification, retrieval, information extraction, and information integration) can be formalized as inference in an appropriate probabilistic first-order logic. However, most probabilistic first-order logics are not efficient enough for realistically-sized instances of these tasks. One key problem is that queries are typically answered by "grounding" the query---i.e., mapping it to a propositional representation, and then performing propositional inference---and with a large database of facts, groundings can be very large, making inference and learning computationally expensive. Here we present a first-order probabilistic language which is well-suited to approximate "local" grounding: in particular, every query $Q$ can be approximately grounded with a small graph. The language is an extension of stochastic logic programs where inference is performed by a variant of personalized PageRank. Experimentally, we show that the approach performs well on an entity resolution task, a classification task, and a joint inference task; that the cost of inference is independent of database size; and that speedup in learning is possible by multi-threading. <s> BIB005 </s> A Survey on Personalized PageRank Computation Algorithms <s> F. OTHERS <s> Graph clustering has been an essential part in many methods and thus its accuracy has a significant effect on many applications. In addition, exponential growth of real-world graphs such as social networks, biological networks and electrical circuits demands clustering algorithms with nearly-linear time and space complexity. In this paper we propose Personalized PageRank Clustering (PPC) that employs the inherent cluster exploratory property of random walks to reveal the clusters of a given graph. We combine random walks and modularity to precisely and efficiently reveal the clusters of a graph. PPC is a top-down algorithm so it can reveal inherent clusters of a graph more accurately than other nearly-linear approaches that are mainly bottom-up. It also gives a hierarchy of clusters that is useful in many applications. PPC has a linear time and space complexity and has been superior to most of the available clustering algorithms on many datasets. Furthermore, its top-down approach makes it a flexible solution for clustering problems with different requirements. <s> BIB006 </s> A Survey on Personalized PageRank Computation Algorithms <s> F. OTHERS <s> In this paper we evaluate citation networks of authors, publications and journals, constructed from the ISI Web of Science database (Computer Science categories). Our aim was to find a method with which to rank authors of scientific papers so that the most important occupy the top positions. We utilized a hand-made list of authors, each of whom have received an ACM Fellowship or have been awarded by an ACM SIG (Artificial Intelligence or Hardware categories). The developed method also included the adoption of the PageRank algorithm, which can be considered a measure of prestige, as well as other measures of significance (h-index, publication count, citation count, publication's author count), with these measures analyzed regarding their influence on the final rankings. <s> BIB007 </s> A Survey on Personalized PageRank Computation Algorithms <s> F. OTHERS <s> Local graph diffusions have proven to be valuable tools for solving various graph clustering problems. As such, there has been much interest recently in efficient local algorithms for computing them. We present an efficient local algorithm for approximating a graph diffusion that generalizes both the celebrated personalized PageRank and its recent competitor/companion - the heat kernel. Our algorithm is based on writing the diffusion vector as the solution of an initial value problem, and then using a waveform relaxation approach to approximate the solution. Our experimental results suggest that it produces rankings that are distinct and competitive with the ones produced by high quality implementations of personalized PageRank and localized heat kernel, and that our algorithm is a useful addition to the toolset of localized graph diffusions. <s> BIB008
There are many other fields where PPR is applied. The FolkRank is a folksonomy-based algorithm that is used for tag recommendations. Kim and El Saddik BIB004 proposed a new way to efficiently compute the FolkRank by representing it as a linear combination of PPR vectors. In first-order probabilistic representation systems, inference by grounding can be very computationally expensive. Wang et al. BIB005 proposed a first-order probabilistic language to approximate the local grounding by applying PPR to a small graph. Nykl et al. BIB007 evaluated a citation network that was built using the ISI Web of Science database. Their aim was to find an evaluation method that best matches the list of authors who received ACM Fellowships or ACM SIGs. The best ranking method included PPR where the personalization is based on PageRank journal values. Local graph diffusion is an effective tool for solving graph clustering problems. Avron and Horesh BIB008 proposed an efficient local algorithm for approximating a graph diffusion, which generalizes PPR and the heat kernel. Tabrizi et al. BIB006 proposed a Personalized PageRank Clustering (PPC) algorithm that utilizes the random walk and modularity to accurately reveal the inherent clusters of graphs. It also gives a hierarchy of the clusters given linear time and space complexity. Andersen et al. BIB001 presented a generalized local partitioning algorithm for undirected graphs to strongly connect directed graphs by computing PPR vector. Guo et al. BIB002 proposed the Access Time-length and Frequency-based PageRank to prefetch web pages for web page caching. With respect to databases, Balmin et al.  devised a method called ''ObjectRank'', which is a variation of PPR, to perform keyword searches based on authority. Chakrabarti BIB003 proposed HubRank, which is a proximity search platform for Entity-Relation graphs, using the dynamic PPR.