public
Last active

  • Download Gist
gistfile1.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
require "matrix"
 
#First, you construct an adjacency matrix. An adjacency matrix is just a matrix of what is linking to what.
 
#[0, 1, 1, 1, 1, 0, 1]
#[1, 0, 0, 0, 0, 0, 0]
#[1, 1, 0, 0, 0, 0, 0]
#[0, 1, 1, 0, 1, 0, 0]
#[1, 0, 1, 1, 0, 1, 0]
#[1, 0, 0, 0, 1, 0, 0]
#[0, 0, 0, 0, 1, 0, 0]
 
#This example is based on the wikipedia description, http://en.wikipedia.org/wiki/PageRank#Algorithm
 
#So, for example, row 1 is what Page ID=1 is linking to, ie, pages 2, 3, 4, 5, and 7.
 
#Let's call the matrix m1,
 
m1 = Matrix[[ 0.0,1.0,1.0,1.0,1.0,0.0,1.0],[1.0,0.0,0.0,0.0,0.0,0.0,0.0],[1.0,1.0,0.0,0.0,0.0,0.0,0.0],[0.0,1.0,1.0,0.0,1.0,0.0,0.0],[1.0,0.0,1.0,1.0,0.0,1.0,0.0],[1.0,0.0,0.0,0.0,1.0,0.0,0.0],[0.0,0.0,0.0,0.0,1.0,0.0,0.0]]
 
#I've got it in floating point so it'll end up in floating point...
 
#Now, the first thing you need to do is compute the row-stochastic matrix, which is the same thing as getting each row to add up to 1.
 
def row_stochastic(matrix)
x = 0
row_total = []
while x < matrix.row_size
y = 0
row_total << 0
while y < matrix.row_size
row_total[x] += matrix.row(x)[y]
y += 1
end
x += 1
end
a1 = matrix.to_a
x = 0
while x < matrix.row_size
y = 0
while y < matrix.row_size
a1[x][y] = a1[x][y]/row_total[x]
y += 1
end
x += 1
end
Matrix[*a1]
end
 
#You'd end up with a matrix like this:
 
puts row_stochastic(m1)
 
#[[0.0, 0.2, 0.2, 0.2, 0.2, 0.0, 0.2]
#[1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
#[0.5, 0.5, 0.0, 0.0, 0.0, 0.0, 0.0]
#[0.0, 0.33, 0.33, 0.0, 0.33, 0.0, 0.0]
#[0.25, 0.0, 0.25, 0.25 , 0.0, 0.25, 0.0]
#[0.5, 0.0, 0.0, 0.0, 0.5, 0.0, 0.0]
#[0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0]]
 
#Now, you need to transpose it before you continue.
 
row_stochastic(m1).transpose
 
#Now, you've got to compute the principal eigenvector. I won't go in to the details of what that is, but here's the method, and #what it returns.
 
def eigenvector(matrix)
i = 0
a = []
while i < matrix.row_size
a << [1]
i += 1
end
eigen_vector = Matrix[*a]
i = 0
while i < 100
eigen_vector = matrix*eigen_vector
eigen_vector = eigen_vector / eigen_vector.row(0)[0]
i += 1
end
eigen_vector
end
 
puts eigenvector(row_stochastic(m1).transpose)
 
#[[1.0], [0.547368421052632], [0.463157894736842], [0.347368421052632], [0.589473684210526], [0.147368421052632], [0.2 ]]
 
#Now, just normalize it, by having it all add up to 1.
 
def normalize(matrix)
i = 0
t = 0
while i < matrix.row_size
t += matrix.column(0)[i]
i += 1
end
matrix = matrix/t
end
 
#Giving, in the end,
 
puts normalize(eigenvector(row_stochastic(m1).transpose))
 
#[[0.303514376996805], [0.166134185303514], [0.140575079872204], [0.105431309904153], [0.178913738019169], [0.0447284345047923 ], #[0.060702875399361]]

I belive this method breaks down if you have disconnected graphs. The google white paper adds a damping factor to solve this problem.

You're totally right! Here's an outline and working Javascript example: http://williamcotton.com/pagerank-explained-with-javascript

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.