Abstract
Personalized PageRank is an algorithm to classify the importance of web pages on a user-dependent basis. We introduce two generalizations of Personalized PageRank with node-dependent restart. The first generalization is based on the proportion of visits to nodes before the restart, whereas the second generalization is based on the proportion of time a node is visited just before the restart. In the original case of constant restart probability, the two measures coincide. We discuss interesting particular cases of restart probabilities and restart distributions. We show that both generalizations of Personalized PageRank have an elegant expression connecting the so-called direct and reverse Personalized PageRanks that yield a symmetry property of these Personalized PageRanks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Avrachenkov, K., van der Hofstad, R.W., Sokol, M.: Personalized PageRank with Node-dependent Restart, Inria Research Report no.8570 (July 2014). http://hal.inria.fr/INRIA-RRRT/hal-01052482
Avrachenkov, K., Filar, J., Howlett, P.: Analytic perturbation theory and its applications. SIAM Publisher (2013)
Avrachenkov, K., Dobrynin, V., Nemirovsky, D., Pham, S., Smirnova, E.: Pagerank based clustering of hypertext document collections. In: Proceedings of ACM SIGIR 2008 (2008)
Avrachenkov, K., Gonçalves, P., Mishenin, A., Sokol, M.: Generalized optimization framework for graph-based semi-supervised learning. In: Proceedings of SIAM Conference on Data Mining (SDM 2012)
Avrachenkov, K., Gonçalves, P., Sokol, M.: On the Choice of Kernel and Labelled Data in Semi-supervised Learning Methods. In: Bonato, A., Mitzenmacher, M., Prałat, P. (eds.) WAW 2013. LNCS, vol. 8305, pp. 56–67. Springer, Heidelberg (2013)
Avrachenkov, K., Ribeiro, B., Towsley, D.: Improving Random Walk Estimation Accuracy with Uniform Restarts. In: Kumar, R., Sivakumar, D. (eds.) WAW 2010. LNCS, vol. 6516, pp. 98–109. Springer, Heidelberg (2010)
Avrachenkov, K., Litvak, N., Sokol, M., Towsley, D.: Quick detection of nodes with large degrees. Internet Mathematics 10, 1–19 (2013)
Baeza-Yates, R., Boldi, P., Castillo, C.: Generalizing pagerank: Damping functions for link-based ranking algorithms. In: Proceedings of ACM SIGIR 2006, pp. 308–315 (2006)
Boldi, P.: TotalRank: Ranking without damping. In: Poster Proceedings of WWW 2005, pp. 898–899 (2005)
Brin, S., Page, L., Motwami, R., Winograd, T.: The PageRank citation ranking: bringing order to the Web. Stanford University Technical Report (1998)
Castillo, C., Donato, D., Gionis, A., Murdock, V., Silvestri, F.: Know your neighbors: Web spam detection using the web topology. In: Proceedings of ACM SIGIR 2007, pp. 423–430 (July 2007)
Chen, N., Olvera-Cravioto, M.: Directed random graphs with given degree distributions. Stochastic Systems 3, 147–186 (electronic) (2013)
Chen, P., Xie, H., Maslov, S., Redner, S.: Finding scientific gems with Google’s PageRank algorithm. Journal of Informetrics 1(1), 8–15 (2007)
Constantine, P.G., Gleich, D.F.: Using Polynomial Chaos to Compute the Influence of Multiple Random Surfers in the PageRank Model. In: Bonato, A., Chung, F.R.K. (eds.) WAW 2007. LNCS, vol. 4863, pp. 82–95. Springer, Heidelberg (2007)
Constantine, P.G., Gleich, D.F.: Random alpha PageRank. Internet Mathematics 6(2), 189–236 (2010)
Fouss, F., Francoisse, K., Yen, L., Pirotte, A., Saerens, M.: An experimental investigation of kernels on graphs for collaborative recommendation and semi-supervised classification. Neural Networks 31, 53–72 (2012)
Haveliwala, T.: Topic-Sensitive PageRank. In: Proceedings of WWW 2002 (2002)
van der Hofstad, R.: Random Graphs and Complex Networks, Lecture notes in preparation (2014) (preprint). http://www.win.tue.nl/~rhofstad/NotesRGCN.html
Liu, X., Bollen, J., Nelson, M.L., van de Sompel, H.: Co-authorship networks in the digital library research community. Information Processing & Management 41, 1462–1480 (2005)
Massa, P., Avesani, P.: Trust-aware recommender systems. In: Proceedings of the 2007 ACM Conference on Recommender Systems (RecSys 2007), pp. 17–24 (2007)
Moler, C.D., Moler, K.A.: Numerical Computing with MATLAB. SIAM (2003)
Tijms, H.C.: A first course in stochastic models. John Wiley and Sons (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Avrachenkov, K., van der Hofstad, R., Sokol, M. (2014). Personalized PageRank with Node-Dependent Restart. In: Bonato, A., Graham, F., Prałat, P. (eds) Algorithms and Models for the Web Graph. WAW 2014. Lecture Notes in Computer Science(), vol 8882. Springer, Cham. https://doi.org/10.1007/978-3-319-13123-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-13123-8_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13122-1
Online ISBN: 978-3-319-13123-8
eBook Packages: Computer ScienceComputer Science (R0)