Tracking the random surfer: Empirically measured teleportation parameters in PageRank

Paul G. Constantine, Abraham Flaxman, David F. Gleich, and Asela Gunawardana

Abstract

PageRank computes the importance of each page in a directed graph under a random surfer model governed by a teleportation parameter. Commonly denoted alpha, this parameter models the probability of following an edge inside the graph or, when the graph comes from a network of web pages and links, clicking a link on a web page. We empirically measure the teleportation parameter based on browser toolbar logs and a click trail analysis. For a particular user or machine, such analysis produces a value of alpha. We find that these values nicely fit a Beta distribution with mean edge-following probability between 0.3 and 0.7, depending on the site. Using these distributions, we compute PageRank scores where PageRank is computed with respect to a distribution as the teleportation parameter, rather than a constant teleportation parameter. These new metrics are evaluated on the graph of pages in Wikipedia.

Details

Publication typeInproceedings
Published inWWW
PublisherAssociation for Computing Machinery, Inc.
> Publications > Tracking the random surfer: Empirically measured teleportation parameters in PageRank