PDF Publication Title:
Text from PDF Page: 088
68 4 ⋅ random alpha pagerank 4.4.3 A path damping and browse path view Although we derived the RAPr model by replacing the deterministic co- efficient α with a random variable A, the resulting model has strong con- nections with other generalizations of PageRank based on path damping coefficients [Baeza-Yates et al., 2006]. From the Neumann series for E [x(A)], (4.9), the coefficient on the jth power of P is the weight placed on a path of length j in the Markov chain. Because these coefficients tend to decrease as j increases, they “damp” longer paths in the Markov chain. Figure 4.5 shows the path damping coefficients for the distributions from figure 4.4. As shown in figure 4.5, the path damping view of RAPr provides interesting information about the impact of different distributions. For details on the algorithmic implications of the path damping view, see section 4.6.3. In the full generalization of the path damping model [Baeza-Yates et al., 2006], we are free to choose the path damping coefficients to be any non- negative sequence with unit sum. One study suggests taking the coefficient on the path of length l to be the empirical probability that surfers follow a path of length l, or alternatively, an approximation from an inverse Gaussian distribution [Huberman et al., 1998]. Let’s introduce a slightly different model based on this idea and demonstrate its relationship to RAPr. Let L be a non-negative integer random variable representing the length of a browsing path on the web. This L is a discrete random variable, not a continuous random variable like A. Using L in this model requires the probability operator, P [⋅], because the expectation of a discrete random variable is only defined over the set of discrete values. For example, ∞ E [L] = ∑ l P [L = l ] l=0 is the expected, or average, length of a browsing path. In this model, a random surfer follows exactly L links on the web before stopping. Under L, surfers stop at PL and can use E [PL v] as another ranking vector, ∞ E [PL v] = ∑ P [L = l] Pl v. (4.18) l=0 This equation gives the direct relationship between a path damping equation andRAPr. IfwecanconstructAsuchthatP[L=l]=E[Al]−E[Al+1], then we could establish a direct relationship between the models. Thus, we need to match moments P [L = 0] = E [A0 ] − E [A1 ] P [L = 1] = E [A1 ] − E [A2 ] P [L = 2] = E [A2 ] − E [A3 ] E [A0 ] = 1 E [A1 ] = E [A0 ] − P [L = 0] ⇒ (4.19) E [A2 ] = E [A1 ] − P [L = 1] ⋮⋮ Computing such a distribution of A is a special case of the Hausdorff moment problem [Talenti, 1987], which has a known characterization for a unique solution. We go no further than noting this equivalence.PDF 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 (Standard Web Page)