Power Method for PageRank

powermethod.jl

#############################################
# PageRank algorithm using the power method #
# youri mouton 18/08/2017                   #
#############################################

# Adjacency matrix
A = [ 0 2 0;
      0 0 2;
      1 1 0];

# Out degree matrix
D = diagm(sum(A,2)[:])

# Transition probability matrix
P = inv(D) * A

# Transition probability matrix transposition
PT = P'

# We assume each node has equal importance, so for 3 nodes,
# initialise a [1/3;1/3;1/3] vector.
# Initial vector that will iterate until convergence
V = ones(size(A,1),1)*(1/size(A,1))

# Main power method loop, 50 iterations are adequate
# since the convergence is fast.
# You could also do PT^50 * V.
# The power method effectively calculates the right eigenvector of PT, the
# transposed transition probability matrix.
for i = 1 : 50
  V = PT * V
end

print(V)