A Survey on Personalized PageRank Computation Algorithms <s> A. PERSONALIZED WEB SEARCH <s> The importance of a Web page is an inherently subjective matter, which depends on the readers interests, knowledge and attitudes. But there is still much that can be said objectively about the relative importance of Web pages. This paper describes PageRank, a mathod for rating Web pages objectively and mechanically, effectively measuring the human interest and attention devoted to them. We compare PageRank to an idealized random Web surfer. We show how to efficiently compute PageRank for large numbers of pages. And, we show how to apply PageRank to search and to user navigation. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> A. PERSONALIZED WEB SEARCH <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> BIB002 </s> A Survey on Personalized PageRank Computation Algorithms <s> A. PERSONALIZED WEB SEARCH <s> In this paper, we consider the problem of calculating fast and accurate approximations to the personalized PageRank score of a webpage. We focus on techniques to improve speed by limiting the amount of web graph data we need to access. Our algorithms provide both the approximation to the personalized PageRank score as well as guidance in using only the necessary information—and therefore sensibly reduce not only the computational cost of the algorithm but also the memory and memory bandwidth requirements. We report experiments with these algorithms on web graphs of up to 118 million pages and prove a theoretical approximation bound for all. Finally, we propose a local, personalized web-search system for a future client system using our algorithms. <s> BIB003 </s> A Survey on Personalized PageRank Computation Algorithms <s> A. PERSONALIZED WEB SEARCH <s> Although personalized search has been proposed for many years and many personalization strategies have been investigated, it is still unclear whether personalization is consistently effective on different queries for different users, and under different search contexts. In this paper, we study this problem and get some preliminary conclusions. We present a large-scale evaluation framework for personalized search based on query logs, and then evaluate five personalized search strategies (including two click-based and three profile-based ones) using 12-day MSN query logs. By analyzing the results, we reveal that personalized search has significant improvement over common web search on some queries but it also has little effect on other queries (e.g., queries with small click entropy). It even harms search accuracy under some situations. Furthermore, we show that straightforward click-based personalization strategies perform consistently and considerably well, while profile-based ones are unstable in our experiments. We also reveal that both long-term and short-term contexts are very important in improving search performance for profile-based personalized search strategies. <s> BIB004
One of well-known application examples of PPR is personalized web searches. Applying PPR to personalized web searches was suggested at the birth of PageRank BIB001 . Its actual application was studied later by Haveliwala  . In this paper, the restart vector s is defined by topics that represent personal preferences. In particular, let T j be the set webpages in the category c j on the Open Directory Project. BIB002 When computing PageRank for topic c j , the non-uniform vector v j is used in place of the uniform vector 1 By using the biased restart vector − → v j , the result of PageRank can represent the importance of each page in terms of a certain topic. The result of the experiment shows that using a biased restart vector in place of an unbiased vector significantly improves the precision of an information retrieval system. Gleich and Polito BIB003 also proposed an approximate PPR algorithm and personalized web search system that can provide personalized search results to users without violating the users' privacy. Dou et al. BIB004 presented a large-scale evaluation framework for personalized search strategies and analyzed the effects of many personalization strategies.