Tracking the random surfer: empirically measured teleportation parameters in PageRank

DF Gleich, PG Constantine, AD Flaxman… - Proceedings of the 19th …, 2010 - dl.acm.org
Proceedings of the 19th international conference on World wide web, 2010dl.acm.org
PageRank computes the importance of each node 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 …
PageRank computes the importance of each node 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.
ACM Digital Library