Article

The effect of the back button in a random walk: application for pagerank

Authors:

Fabien Mathieu,

Mohamed BouklitAuthors Info & Claims

WWW Alt. '04: Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters

Pages 370 - 371

https://doi.org/10.1145/1013367.1013480

Published: 19 May 2004 Publication History

Get Access

Abstract

Theoretical analysis of the Web graph is often used to improve the efficiency of search engines. The PageRank algorithm, proposed by Brin and Page, is used by the Google search engine to improve the results of the queries. The purpose of this article is to describe an enhanced version of the PageRank algorithm using a realistic model forthe back button. We introduce a limited history stack model (you cannot click more than m times in a row), and showthat when m=1, the computation of this Back PageRank can be as fast as that of a standard PageRank.

References

[1]

S. Brin, R. Motwani, L. Page, and T. Winograd. What can you do with a Web in your Pocket? Data Engineering Bulletin, 21(2):37--47, 1998.

Google Scholar

[2]

A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web. Computer Networks: The International Journal of Computer and Telecommunications Networking, 33(1-6):309--320, 2000.

Digital Library

Google Scholar

[3]

R. Fagin, A. R. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, and A. Tomkins. Random walks with "back buttons" (extended abstract). pages 484--493, 2000.

Digital Library

Google Scholar

[4]

Google. http://www.google.com/, 1998.

Google Scholar

[5]

L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Technical report, Computer Science Department, Stanford University, 1998.

Google Scholar

[6]

L. Saloff-Coste. Lectures on finite Markov chains. In G. G. E. Giné and L. Saloff-Coste, editors, Lecture Notes on Probability Theory and Statistics, number 1665 in LNM, pages 301--413. Springer Verlag, 1996.

Google Scholar

Cited By

View all

Leonardo Wang VTang YGuo JBao X(2022)The Elaboration and Further Improvements of PageRank2022 International Conference on Cloud Computing, Big Data Applications and Software Engineering (CBASE)10.1109/CBASE57816.2022.00024(92-98)Online publication date: Sep-2022
https://doi.org/10.1109/CBASE57816.2022.00024
Rossi RGleich D(2012)Dynamic pagerank using evolving teleportationProceedings of the 9th international conference on Algorithms and Models for the Web Graph10.1007/978-3-642-30541-2_10(126-137)Online publication date: 22-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-30541-2_10
Mirzal AFurukawa M(2010)A Method for Accelerating the HITS AlgorithmJournal of Advanced Computational Intelligence and Intelligent Informatics10.20965/jaciii.2010.p008914:1(89-98)Online publication date: 20-Jan-2010
https://doi.org/10.20965/jaciii.2010.p0089
Show More Cited By

Index Terms

The effect of the back button in a random walk: application for pagerank
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices

Recommendations

BackRank: an alternative for PageRank?
WWW '05: Special interest tracks and posters of the 14th international conference on World Wide Web

This paper proposes to extend a previous work, The Effect of the Back Button in a Random Walk: Application for PageRank [5]. We introduce an enhanced version of the PageRank algorithm using a realistic model for the Back button, thus improving the ...
Click-boosting random walk for image search reranking
ICIMCS '13: Proceedings of the Fifth International Conference on Internet Multimedia Computing and Service

Image reranking is an effective way for improving the retrieval performance of keyword-based image search engines. A fundamental issue underlying the success of existing image reranking approaches is the ability in identifying potentially useful ...
Random walk based rank aggregation to improving web search

In Web search, with the aid of related query recommendation, Web users can revise their initial queries in several serial rounds in pursuit of finding needed Web pages. In this paper, we address the Web search problem on aggregating search results of ...

Comments

Information & Contributors

Information

Published In

WWW Alt. '04: Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters

May 2004

532 pages

ISBN:1581139128

DOI:10.1145/1013367

Conference Chairs:
Stuart Feldman
IBM Research
,
Mike Uretsky
New York University
,
Program Chairs:
Marc Najork
Microsoft Research
,
Craig Wills
Worcester Polytechnic Institute

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

WWW04

Sponsor:

WWW04: The 2004 World Wide Web Conference ( in conjunction with ACM Conference on Electronic Commerce [EC'04])

May 19 - 21, 2004

NY, New York, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
368
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Leonardo Wang VTang YGuo JBao X(2022)The Elaboration and Further Improvements of PageRank2022 International Conference on Cloud Computing, Big Data Applications and Software Engineering (CBASE)10.1109/CBASE57816.2022.00024(92-98)Online publication date: Sep-2022
https://doi.org/10.1109/CBASE57816.2022.00024
Rossi RGleich D(2012)Dynamic pagerank using evolving teleportationProceedings of the 9th international conference on Algorithms and Models for the Web Graph10.1007/978-3-642-30541-2_10(126-137)Online publication date: 22-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-30541-2_10
Mirzal AFurukawa M(2010)A Method for Accelerating the HITS AlgorithmJournal of Advanced Computational Intelligence and Intelligent Informatics10.20965/jaciii.2010.p008914:1(89-98)Online publication date: 20-Jan-2010
https://doi.org/10.20965/jaciii.2010.p0089
Meiss MGonçalves BRamasco JFlammini AMenczer FChignell MToms E(2010)Agents, bookmarks and clicksProceedings of the 21st ACM conference on Hypertext and hypermedia10.1145/1810617.1810658(229-234)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1810617.1810658
Meiss MGonçalves BRamasco JFlammini AMenczer F(2010)Modeling Traffic on the Web GraphAlgorithms and Models for the Web-Graph10.1007/978-3-642-18009-5_6(50-61)Online publication date: 2010
https://doi.org/10.1007/978-3-642-18009-5_6
Levene M(2010)BibliographyAn Introduction to Search Engines and Web Navigation10.1002/9780470874233.biblio(424-461)Online publication date: 4-Aug-2010
https://doi.org/10.1002/9780470874233.biblio
Shakery AZhai CYu PTsotras VFox ELiu B(2006)A probabilistic relevance propagation model for hypertext retrievalProceedings of the 15th ACM international conference on Information and knowledge management10.1145/1183614.1183693(550-558)Online publication date: 6-Nov-2006
https://dl.acm.org/doi/10.1145/1183614.1183693
Richardson MPrakash ABrill ECarr LDe Roure DIyengar AGoble CDahlin M(2006)Beyond PageRankProceedings of the 15th international conference on World Wide Web10.1145/1135777.1135881(707-715)Online publication date: 23-May-2006
https://dl.acm.org/doi/10.1145/1135777.1135881
Sydow M(2005)Random Surfer with Back StepFundamenta Informaticae10.5555/2370509.237051468:4(379-398)Online publication date: 1-Dec-2005
https://dl.acm.org/doi/10.5555/2370509.2370514
Sydow M(2005)Random Surfer with Back StepFundamenta Informaticae10.5555/1227240.122724568:4(379-398)Online publication date: 1-Jun-2005
https://dl.acm.org/doi/10.5555/1227240.1227245
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

BackRank: an alternative for PageRank?

Click-boosting random walk for image search reranking

Random walk based rank aggregation to improving web search

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations