https://www.r-bloggers.com/2014/04/from-random-walks-to-personalized-pagerank/

A simple recursice formulation

• if page P with importance x has n outlinks, each link gets x/n votes
• importance = sum of votes
• need to add one more equation to get unique solution: y+a+m=1

solution

• If j has an outlink i , then Mij**=1/n**

• We get a column stochastic matrix M

• $R \times \bold r=\bold r$

• So the rank vector is a first/principal eigenvector(eigenvalue=1) of the stochastic web matrix

• Power Iteration method

  • $\bold r_0=[1/n,1/n, \dots ]^T, \bold r_k=M \times \bold r_{k-1}$
  • until converge enough with respect to any norm

• Random Walk Interpretation

  • imagine a surfer randomly walk on graph
  • choosing one outlink uniformly at random

problem1: spider traps

• A group of pages is a spider trap if there are no links from within the group to outside the group
• trap the surfer
  • fix(random teleport): at each step, have a probability (0.1~0.2) to not follow link but jump to some page uniformly at random
• $A=\beta * M+(1-\beta)*[1/n \dots]$

problem2: dead end

• a node with no any outlink
• no longer a column stochastic matrix