Top

Published in:

2015 | OriginalPaper | Chapter

Random Surfing Without Teleportation

Authors : Athanasios N. Nikolakopoulos, John D. Garofalakis

Published in: Algorithms, Probability, Networks, and Games

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In the standard Random Surfer Model, the teleportation matrix is necessary to ensure that the final PageRank vector is well-defined. The introduction of this matrix, however, results in serious problems and imposes fundamental limitations to the quality of the ranking vectors. In this work, building on the recently proposed NCDawareRank framework, we exploit the decomposition of the underlying space into blocks, and we derive easy to check necessary and sufficient conditions for random surfing without teleportation.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter An Introduction to Temporal Graphs: An Algorithmic Perspective

next chapter Of Concurrent Data Structures and Iterations

For thorough treatment of the theory as well as proofs to several formulations of the Perron-Frobenius theorem the interested reader can see [18].

notice that if this was not the case, there would be a nonzero element in the block below the diagonal necessarily.

Avrachenkov, K., Litvak, N., Pham, K.S.: Distribution of pagerank mass among principle components of the web. In: Bonato, A., Chung, F.R.K. (eds.) WAW 2007. LNCS, vol. 4863, pp. 16–28. Springer, Heidelberg (2007) CrossRef

Baeza-Yates, R., Boldi, P., Castillo, C.: Generic damping functions for propagating importance in link-based ranking. Internet Math. 3(4), 445–478 (2006). http://dx.doi.org/10.1080/15427951.2006.10129134 MathSciNetCrossRefMATH

Boldi, P.: Totalrank: ranking without damping. In: Special Interest Tracks and Posters of the 14th International Conference on World Wide Web, WWW 2005, pp. 898–899. ACM, New York (2005). http://doi.acm.org/10.1145/1062745.1062787

Boldi, P., Santini, M., Vigna, S.: A deeper investigation of pagerank as a function of the damping factor. In: Frommer, A., Mahoney, M.W., Szyld, D.B. (eds.) Web Information Retrieval and Linear Algebra Algorithms, 11-16 February 2007, Dagstuhl Seminar Proceedings, vol. 07071, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany (2007). http://drops.dagstuhl.de/opus/volltexte/2007/1072

Boldi, P., Santini, M., Vigna, S.: Pagerank: functional dependencies. ACM Trans. Inf. Syst. 27(4), 1–23 (2009). http://doi.acm.org/10.1145/1629096.1629097 CrossRef

Constantine, P.G., Gleich, D.F.: Random alpha pagerank. Internet Math. 6(2), 189–236 (2009). http://dx.doi.org/10.1080/15427951.2009.10129185 MathSciNetCrossRefMATH

Courtois, P.J.: On time and space decomposition of complex structures. Commun. ACM 28(6), 590–603 (1985). http://doi.acm.org/10.1145/988672.988714 CrossRef

Eiron, N., McCurley, K.S., Tomlin, J.A.: Ranking the web frontier. In: Proceedings of the 13th International Conference on World Wide Web, WWW 2004, pp. 309–318. ACM, New York (2004). http://doi.acm.org/10.1145/988672.988714

Frobenius, G.: Üeber matrizen aus positiven elementen i and ii. Sitzungsber. Preuss. Akad. Wiss, Berlin (1908) MATH

10.

Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (2012) CrossRef

11.

Kamvar, S., Haveliwala, T.: The condition number of the pagerank problem (2003)

12.

Langville, A.N., Meyer, C.D.: Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, Princeton (2011) MATH

13.

Nikolakopoulos, A.N., Garofalakis, J.D.: NCDawareRank: a novel ranking method that exploits the decomposable structure of the web. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013, pp. 143–152. ACM, New York (2013). http://doi.acm.org/10.1145/2433396.2433415

14.

Nikolakopoulos, A.N., Garofalakis, J.D.: NCDREC: a decomposability inspired framework for top-n recommendation. In: 2014 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT), Warsaw, Poland, 11–14 August 2014 - Volume II, pp. 183–190. IEEE (2014). http://dx.doi.org/10.1109/WI-IAT.2014.32

15.

Nikolakopoulos, A.N., Kouneli, M.A., Garofalakis, J.D.: Hierarchical itemspace rank: exploiting hierarchy to alleviate sparsity in ranking-based recommendation. Neurocomputing 163, 126–136 (2015). http://www.sciencedirect.com/science/article/pii/S0925231215002180 CrossRef

16.

Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: bringing order to the web (1999)

17.

Perron, O.: Zur theorie der matrices. Mathematische Annalen 64(2), 248–263 (1907)MathSciNetCrossRefMATH

18.

Seneta, E.: Non-negative matrices and markov chains. Springer Series in Statistics. Springer, New York (2006) MATH

19.

Simon, H.A.: The Sciences of the Artificial, vol. 136. MIT press, Cambridge (1996)

20.

Simon, H.A., Ando, A.: Aggregation of variables in dynamic systems. Econometrica J. Econometric Soc. 29, 111–138 (1961)CrossRefMATH

Title: Random Surfing Without Teleportation
Authors: Athanasios N. Nikolakopoulos
John D. Garofalakis
Publisher: Springer International Publishing
Book: Algorithms, Probability, Networks, and Games
Print ISBN: 978-3-319-24023-7

Electronic ISBN: 978-3-319-24024-4

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-24024-4_19

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner