gistfile1.rb

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]]