PDF Publication Title:
Text from PDF Page: 034
2 ⋅ pagerank background The data for the PageRank problem are P a column stochastic matrix that defines the transitions of a Markov chain; α ateleportationparameterordampingparameter,0≤α<1;and v a teleportation distribution, where v ≥ 0 and eT v = 1, also known as i the preference vector. To fix the scheme, PageRank modifies it so that it does something predictable from v. The parameter α controls the trade-off between P and v. Transitions of the PageRank process are given by a modified Markov matrix M=α P +(1−α)veT =M(α,P,v). (2.2) follow transitions reset Subsequently, we will omit the explicit dependence on the parameters when they are clear from context. Interpreted as a Markov chain, PageRank is a process that follows transitions in the original process P with probability α or resets according to a known distribution over the states with probability (1 − α). In contrast with P, the dominant eigenvector Mx = x is always unique. This x is the PageRank vector (with a slight detail addressed below). Uniqueness of the eigenvector is trivial when vi > 0 and follows from the Perron-Frobenius theorem because α < 1 implies that Mi j > 0. A detail often swept under the rug is what happens when vi ≥ 0. Without a completely positive v, M is no longer irreducible and the simple theorems for a unique eigenvector do not apply. That said, the eigenvector is still unique because M has only a single ergodic class over the set of states reachable from the support of v. Berman and Plemmons [1994, theorem 3.23] justifies this statement with the more general result that all unit eigenvectors of a stochastic matrix are convex combinations of unit eigenvectors of the ergodic classes extended to all states with 0 probability.1 PageRank values are also the stationary distribution probabilities for the modified Markov chain, namely the PageRank vector x is the stationary dis- tribution vector. For this reason, the PageRank vector is a probability distri- bution vector and has the natural normalization 14 x ≥0,eTx=1. i The discussion thus far is the eigenvector definition of PageRank: Mx = x and eT x = 1. 1 A special case is also not difficult to see.Whenvi ≥ 0thenMcanbesym- metrically permuted and partitioned so that M = [ M1 ], where the spectral M12 M2 radius of M1 < 1 and M2 is stochastic and irreducible. The rows and columns in M2 correspond to all states reach- able from the support of v. Solutions to[ M1 ][x1 ] = [x1 ]areunique M12 M2 x2 x2 because ρ(M1) < 1 implies that x1 = 0 and also stochasticity and irreducibility of M2 implies that x2 is unique. As a probability distribution, the PageRank vector is also the solution of the linear system (I − αP)x = (1 − α)v, (2.4) which follows from eT x = 1 and Mx = αPx + (1 − α)v = x. This system is non-singular for all α < 1, and (I − αP) is an M-matrix. We could hardly ask to be luckier! Note that there is no difficulty with non-negative v for the (2.3)PDF Image | ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION
PDF Search Title:
ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATIONOriginal File Name Searched:
gleich.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 |