PDF Publication Title:
Text from PDF Page: 075
4RANDOM ALPHA PAGERANK Numquam ponenda est pluralitas sine necessitate. William of Ockham Thus far in the thesis, all the PageRank computations used a particular value of α. Sometimes it was 0.85, sometimes 0.75 or 0.95. We even studied a range of values at one point (figure 2.4). These choices were arbitrary and largely motivated by the “standard” choice of α, namely, 0.85. This chapter begins by asking, what should α be? Recall that the PageRank modification for a Markov chain transforms any input Markov chain into an irreducible, aperiodic chain with a unique stationary distribution. Elements of this unique stationary distribution give the importance of the nodes in the state space of the input Markov chain. Brin and Page proposed the PageRank method to measure the global importance of web pages under the behavior of a random surfer, which can be interpreted as a Markov chain on the web graph [Page et al., 1999]. We now focus on this random surfer model and show that it contains a slight error when interpreted over a set of “surfers.” Let us begin by revisiting the putative random surfer. With probability α, the surfer follows the links of a web page uniformly at random. With probability 1 − α, the surfer jumps to a different page according to a given probability distribution over web pages. Because of its influence on these random jumps, the value α is often called the teleportation parameter. Thus, the PageRank value for a web graph depends on two quantities: the parameter α and the given distribution over the pages. The effect of both of these quantities on the mathematics of the PageRank vector are fairly well understood, but the choice of α is not well justified in the context of the random surfer model. Existing PageRank calculations use a single value of α and two choices stand out in the literature: α = 0.5 [Katz, 1953; Avrachenkov et al., 2007; Chen et al., 2007] and α = 0.85 [Page et al., 1999; Najork et al., 2007]. These choices are discussed in section 4.3.1. Rather than trying and testing arbitrary values of α, suppose we pick α to make the random surfer model more accurate. Because α really ought to be the probability of following a link on a web page, let’s make it so. Empirically measured browsing patterns on the web show that individual users, unsurprisingly, have different browsing behavior [Huberman et al., 1998; White and Drucker, 2007]. We also confirm this result in section 4.5. If we assume that all users have their own probability αi of teleporting, then the PageRank model suggests we should set α = N1 ∑Ni=1 αi , i.e. the mean of these values. More generally, if A is a random variable with a density function 55PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
| CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com | RSS | AMP |