Link Analysis PageRank Example a m Yahoo y1/2120 a1/201 m01/20 r= mr mazon Soft /21/20 y=y/2+a/2 a 201a a=y/2+ m m01/20 m=a/2
Link Analysis 11 Example Yahoo Amazon M’soft y 1/2 1/2 0 a 1/2 0 1 m 0 1/2 0 y a m y = y /2 + a /2 a = y /2 + m m = a /2 r = Mr y 1/2 1/2 0 y a = 1/2 0 1 a m 0 1/2 0 m PageRank
Link Analysis PageRank Power iteration method Simple iterative scheme( aka relaxation) Suppose there are n web pages Initialize: rO =[1/N,.1/NJT ■ terete: Stop when rk+1-rk,<e x|1=∑1|x| is the li norm Can use any other vector norm e. g euclidean
Link Analysis 12 Power Iteration method ▪ Simple iterative scheme (aka relaxation) ▪ Suppose there are N web pages ▪ Initialize: r 0 = [1/N,….,1/N]T ▪ Iterate: r k+1 = Mrk ▪ Stop when |r k+1 - r k|1 < ▪ |x|1 = 1≤i≤N|xi| is the L1 norm ▪ Can use any other vector norm e.g., Euclidean PageRank
Link Analysis PageRank Power iteration Example Yahoo y a m y1/21/20 a1/201 01/20 mazon Soft 1/31/35/123/8 2/5 a 1/3121/311/2 2/5 1/31/61416 1/5
Link Analysis 13 Power Iteration Example Yahoo Amazon M’soft y 1/2 1/2 0 a 1/2 0 1 m 0 1/2 0 y a m y a = m 1/3 1/3 1/3 1/3 1/2 1/6 5/12 1/3 1/4 3/8 11/24 1/6 2/5 2/5 1/5 . . . PageRank
Link Analysis PageRank Random Walk Interpretation magine a random web surfer At any time t, surfer is on some page p At time t+1, the surfer follows an outlink from p uniformly at random Ends up on some page Q linked from p Process repeats indefinitely Let p(t be a vector whose ith component is the probability that the surfer is at page i at time t p(t is a probability distribution on pages
Link Analysis 14 Random Walk Interpretation ▪ Imagine a random web surfer ▪ At any time t, surfer is on some page P ▪ At time t+1, the surfer follows an outlink from P uniformly at random ▪ Ends up on some page Q linked from P ▪ Process repeats indefinitely ▪ Let p(t) be a vector whose ith component is the probability that the surfer is at page i at time t ▪ p(t) is a probability distribution on pages PageRank
Link Analysis PageRank The stationary distribution Where is the surfer at time t+1? Follows a link uniformly at random p(t+1 =Mp(t) Suppose the random walk reaches a state such that p(t+1 =mp(t=p(t) Then p(t is called a stationary distribution for the random walk Our rank vector r satisfies r= mr So it is a stationary distribution for the random surfer
Link Analysis 15 The stationary distribution ▪ Where is the surfer at time t+1? ▪ Follows a link uniformly at random ▪ p(t+1) = Mp(t) ▪ Suppose the random walk reaches a state such that p(t+1) = Mp(t) = p(t) ▪ Then p(t) is called a stationary distribution for the random walk ▪ Our rank vector r satisfies r = Mr ▪ So it is a stationary distribution for the random surfer PageRank