Top

previous chapter An Introduction to Temporal Graphs: An Algorith...

next chapter Of Concurrent Data Structures and Iterations

Hint

Swipe to navigate through the chapters of this book

2015 | OriginalPaper | Chapter

Random Surfing Without Teleportation

Read first chapter

Authors: Athanasios N. Nikolakopoulos, John D. Garofalakis

Publisher: Springer International Publishing

Published in: Algorithms, Probability, Networks, and Games

» Get access to the full-text

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.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

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

Book

Algorithms, Probability, Networks, and Games

Print ISBN: 978-3-319-24023-7

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

https://doi.org/10.1007/978-3-319-24024-4

DOI

https://doi.org/10.1007/978-3-319-24024-4_19

Authors:

Athanasios N. Nikolakopoulos
John D. Garofalakis

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits