Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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

Higham, D.J. (2005) Google PageRank as mean playing time for pinball on the reverse web. Applied Mathematics Letters, 18 (12). pp. 1359-1362. ISSN 0893-9659

[img]
Preview
PDF (strathprints000161.pdf)
Download (100Kb) | Preview

    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.

    Item type: Article
    ID code: 161
    Keywords: google, search algorithm, page rank, linear recurrence, mathematics, votes of confidence, probability, Mathematics, Applied Mathematics
    Subjects: Science > Mathematics
    Department: Faculty of Science > Mathematics and Statistics
    Related URLs:
      Depositing user: Ms Sarah Scott
      Date Deposited: 21 Feb 2006
      Last modified: 04 Sep 2014 23:23
      URI: http://strathprints.strath.ac.uk/id/eprint/161

      Actions (login required)

      View Item

      Fulltext Downloads: