The PageRank Algorithm (Page et al.98) Random surfing model: At any page, With prob.a,randomly jumping to a page With prob.(1-a),randomly picking a link to follow. [001/21/2 1 00 M= 0 0 10 0 “Transition matrix” 1/21/20 0 N+#pages d pd)=Q-@)Zmp(d)+a =l 名Na) 25a+-a)m.pld.→ Stationary(stable”) distribution,so we p=(al+(1-a)M)Y'p Ii=1/N ignore time Initial value p(d)=1/N Iterate until converge CCF-ADL at Zhengzhou University,June 25-27,2010 12
The PageRank Algorithm (Page et al. 98) 1 1 1 0 0 1/ 2 1/ 2 1 0 0 0 0 1 0 0 1/ 2 1/ 2 0 0 1 ( ) (1 ) ( ) ( ) 1 [ (1 ) ] ( ) ( (1 ) ) N N i ki k k k k N ki k k T M p d m p d p d N m p d N p I M p = = = = = − + = + − = + − d1 d2 d4 “Transition matrix” d3 Iterate until converge N= # pages Stationary (“stable”) distribution, so we ignore time Random surfing model: At any page, With prob. , randomly jumping to a page With prob. (1-), randomly picking a link to follow. Iij = 1/N Initial value p(d)=1/N 12 CCF-ADL at Zhengzhou University, June 25-27, 2010
PageRank in Practice Interpretation of the damping factor a(0.15): Probability of a random jump -Smoothing the transition matrix(avoid zero's) l-空mr2nt) p=(al+(1-a)M)'p Normalization doesn't affect ranking,leading to some variants Let p'(d )cpA(d )c-constant,p(d )()mp(d,)+ t- 名Npd) pid)-(-ampd 名pa) p'(d)-(1-amP(d)+a The zero-outlink problem:p(di)'s don't sum to 1 One possible solution=page-specificdamping factor (a=1.0 for a page with no outlink) CCF-ADL at Zhengzhou University, 13 June25-27,2010
PageRank in Practice • Interpretation of the damping factor (0.15): – Probability of a random jump – Smoothing the transition matrix (avoid zero’s) • Normalization doesn’t affect ranking, leading to some variants • The zero-outlink problem: p(di)’s don’t sum to 1 – One possible solution = page-specific damping factor (=1.0 for a page with no outlink) 1 1 1 ( ) (1 ) ( ) ( ) ( (1 ) ) N N T i ki k k k k p d m p d p d p I M p N = = = − + = + − 1 1 1 1 1 1 '( ) ( ), , ( ) (1 ) ( ) ( ) 1 '( ) (1 ) '( ) '( ) '( ) (1 ) '( ) N N i i i ki k k k k N N i ki k k k k C N N i ki k k Let p d cp d c constant cp d m cp d cp d N p d m p d p d N p d m p d = = = = = = = = = − + = − + = − + 13 CCF-ADL at Zhengzhou University, June 25-27, 2010