Skip to content

Instantly share code, notes, and snippets.

@burningTyger
Forked from williamcotton/gist:127435
Created June 23, 2010 12:11
Show Gist options
  • Save burningTyger/449848 to your computer and use it in GitHub Desktop.
Save burningTyger/449848 to your computer and use it in GitHub Desktop.
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]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment