PDF Publication Title:
Text from PDF Page: 035
linear system. Both representations yield quite a bit of flexibility in working with the problem. We summarize this section with the following definition. Problem1(PageRank). GivenacolumnstochasticP,0≤α<1,andadistri- bution vector v, set M = αP + (1 − α)veT . Solving PageRank is computing or approximating the unique vector x in Mx = x and eT x = 1 or (I − αP)x = (1 − α)v. (2.5) All the relevant pieces of the PageRank problem are present in this statement. Anything that calls itself PageRank will compute a vector that satisfies this property for some α, P, and v. Hence, this problem is the core PageRank problem at the heart of figure 2.2. 2.2.1 PageRank variations An alternative starting point for PageRank is to begin with a sub-stochastic matrix P ̄ . As discussed in the next section, sub-stochastic matrices often arise from random walk or influence propagation definitions on graphs. For such P ̄, there are two established formulations of the PageRank problem: strongly preferential PageRank and weakly preferential PageRank [Boldi et al., 2007]. We also formalize a sink preferential PageRank model below. Each formulation corresponds to a different way of converting P ̄ into a stochastic matrix and focuses on the columns of the matrix P ̄ that are completely 0. The dangling indicator vector d is 1 for such columns and 0 for columns where P ̄ is not completely zero. Formally, ⎧ ⎪1 Pij=0foralli dT =eT −eTP ̄, dj =⎨ (2.6) ⎪⎩0 Pij=/0forsomei. The strongly preferential PageRank problem uses the fully stochastic ma- trix Pv = P ̄ + vdT , (2.7) where v is the same vector as in the PageRank problem (2.3) or (2.4). To convince ourselves it is a column stochastic matrix, note that dT is positive only in the columns that caused P ̄ to fail to be stochastic, and so the matrix Pv will be the matrix P ̄ where each 0 column is replaced by v. Weakly preferential PageRank replaces each 0 column of P ̄ with a different distribution vector u, and uses the stochastic matrix Pu = P ̄ + udT , (2.8) whereuisanarbitrarydistributionvectorwithu ≥0,eTu=1,andu=/v. i 2.2 ⋅ the pagerank problem 15PDF 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 |