PDF Publication Title:
Text from PDF Page: 052
32 2 ⋅ pagerank background Recall that the Google matrix is G=αS+(1−α)evT =MT. (2.26) Let S = VJV−1 be the Jordan canonical form of S.8 We’ll state the Jordan form without the presence of a final scaling matrix to transform the off-diagonal elements in the Jordan blocks to unit values. (Recall that the choice of off- diagonal values in the Jordan blocks is arbitrary.) Without further ado, set 8 Serra uses X here, but we’ve replaced it by V to avoid confusion with X in the previous section. and then R=I−e wT, 1 wTe =0, 1 wT = (1 − α)(eT − vT V)(I − αJ)−1 1 G = VR(αJ + (1 − α)e1 e1T )R−1 V−1 . (2.27) (2.28) (2.29) (2.30) Stated as such, this result is somewhat opaque. The derivation is straightfor- ward, but needs a few useful facts about stochastic matrices and eigenvalues. So let’s work through it. From S = VJV−1, we have V−1GV = αJ + (1 − α)V−1evT V. (2.31) We simplify the above expression through V−1e = e , which follows from the 1 fact that S is a stochastic matrix.9 At this point, we simply guess the structure of the matrix that reduces the right-hand side of the previous expression to a 9 To be precise, we need the property that 1 is a non-defective eigenvalue of a stochastic matrix and thus the Jordan block has no off-diagonal elements. Jordanmatrix.LetR=I+e wT.We’llshowhowtopickwsothat 1 R−1V−1GV=(αJ+(1−α)e eT)R−1. 11 (2.32) To begin, we require that eTw = 0 so that R−1 = I − e wT. Our expanded 11 equation is (I−e wT)(αJ+(1−α)e vTV)=(αJ+(1−α)e eT)(I−e wT). (2.33) 11111 A few steps of algebra using eTw = 0 and Je = e yield the equivalent 111 expression (1−α)e vTV−αe wTJ=(1−α)e eT −e wT, (2.34) 11111 where everything shares the common e1. This expression encodes only a single vector (1−α)vTV−αwTJ=(1−α)eT −wT 1 or more elegantly the linear system wT(I−αJ)=(1−α)(eT −vTV). 1 (2.35) (2.36)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 (Standard Web Page)