Google PageRank as mean playing time for pinball on the reverse web

D.J. Higham

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

It is known that the output from Google's PageRank algorithm may be interpreted as (a) the limiting value of a linear recurrence relation that is motivated by interpreting links as votes of confidence, and (b) the invariant measure of a teleporting random walk that follows links except for occasional uniform jumps. Here, we show that, for a sufficiently frequent jump rate, the PageRank score may also be interpreted as a mean finishing time for a reverse random walk. At a general step this new process either (i) remains at the current page, (ii) moves to a page that points to the current page, or (iii) terminates. The process is analogous to a game of pinball where a ball bounces between pages before eventually dropping down the exit chute. This new interpretation of PageRank gives another view of the principle that highly ranked pages will be those that are linked into by highly ranked pages that have relatively few outgoing links.
LanguageEnglish
Pages1359-1362
Number of pages3
JournalApplied Mathematics Letters
Volume18
Issue number12
DOIs
Publication statusPublished - Dec 2005

Fingerprint

PageRank
Reverse
Random walk
Jump
Linear Recurrence Relation
Bounce
Vote
Terminate
Invariant Measure
Confidence
Ball
Limiting
Game
Output

Keywords

  • google
  • search algorithm
  • page rank
  • linear recurrence
  • mathematics
  • votes of confidence
  • probability

Cite this

@article{67ebf5892a8247b3a91710b986a1997b,
title = "Google PageRank as mean playing time for pinball on the reverse web",
abstract = "It is known that the output from Google's PageRank algorithm may be interpreted as (a) the limiting value of a linear recurrence relation that is motivated by interpreting links as votes of confidence, and (b) the invariant measure of a teleporting random walk that follows links except for occasional uniform jumps. Here, we show that, for a sufficiently frequent jump rate, the PageRank score may also be interpreted as a mean finishing time for a reverse random walk. At a general step this new process either (i) remains at the current page, (ii) moves to a page that points to the current page, or (iii) terminates. The process is analogous to a game of pinball where a ball bounces between pages before eventually dropping down the exit chute. This new interpretation of PageRank gives another view of the principle that highly ranked pages will be those that are linked into by highly ranked pages that have relatively few outgoing links.",
keywords = "google, search algorithm, page rank, linear recurrence, mathematics, votes of confidence, probability",
author = "D.J. Higham",
year = "2005",
month = "12",
doi = "10.1016/j.aml.2005.02.020",
language = "English",
volume = "18",
pages = "1359--1362",
journal = "Applied Mathematics Letters",
issn = "0893-9659",
number = "12",

}

Google PageRank as mean playing time for pinball on the reverse web. / Higham, D.J.

In: Applied Mathematics Letters, Vol. 18, No. 12, 12.2005, p. 1359-1362.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Google PageRank as mean playing time for pinball on the reverse web

AU - Higham, D.J.

PY - 2005/12

Y1 - 2005/12

N2 - It is known that the output from Google's PageRank algorithm may be interpreted as (a) the limiting value of a linear recurrence relation that is motivated by interpreting links as votes of confidence, and (b) the invariant measure of a teleporting random walk that follows links except for occasional uniform jumps. Here, we show that, for a sufficiently frequent jump rate, the PageRank score may also be interpreted as a mean finishing time for a reverse random walk. At a general step this new process either (i) remains at the current page, (ii) moves to a page that points to the current page, or (iii) terminates. The process is analogous to a game of pinball where a ball bounces between pages before eventually dropping down the exit chute. This new interpretation of PageRank gives another view of the principle that highly ranked pages will be those that are linked into by highly ranked pages that have relatively few outgoing links.

AB - It is known that the output from Google's PageRank algorithm may be interpreted as (a) the limiting value of a linear recurrence relation that is motivated by interpreting links as votes of confidence, and (b) the invariant measure of a teleporting random walk that follows links except for occasional uniform jumps. Here, we show that, for a sufficiently frequent jump rate, the PageRank score may also be interpreted as a mean finishing time for a reverse random walk. At a general step this new process either (i) remains at the current page, (ii) moves to a page that points to the current page, or (iii) terminates. The process is analogous to a game of pinball where a ball bounces between pages before eventually dropping down the exit chute. This new interpretation of PageRank gives another view of the principle that highly ranked pages will be those that are linked into by highly ranked pages that have relatively few outgoing links.

KW - google

KW - search algorithm

KW - page rank

KW - linear recurrence

KW - mathematics

KW - votes of confidence

KW - probability

U2 - 10.1016/j.aml.2005.02.020

DO - 10.1016/j.aml.2005.02.020

M3 - Article

VL - 18

SP - 1359

EP - 1362

JO - Applied Mathematics Letters

T2 - Applied Mathematics Letters

JF - Applied Mathematics Letters

SN - 0893-9659

IS - 12

ER -