Skip to content

Instantly share code, notes, and snippets.

Created September 25, 2015 13:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anonymous/ae065a6054668e3fb9ae to your computer and use it in GitHub Desktop.
Save anonymous/ae065a6054668e3fb9ae to your computer and use it in GitHub Desktop.
It's the full (Google's) pagerank algorithm as a procedure ... want to make it into a general class
# script doesn't include classes, yet
require 'MDArray'
size = 4
matrix_as_array = [ 0 , 2.0/5 , 0 , 0 , 4.0/15 , 0, 0, 2.0/5, 4.0/15, 0. 4/5.0 , 2/5.0, 4.0/15, 2/5.0, 0 , 0] ]
beta = 0.8
epsilon = 0.000000001
delta = 1.0
it = 0
# The total number — N — of webpages and nodes
n = size.to_f
# The initial rank score vector.
# Each cell is set to (1/N).
pagerank = MDMatrix.double([n,1]).fill(1/n)
# The input graph, M.
# M must have the cells filled
# with (1/d_i), representing the link weights.
# The "matrix_as_array" is a flattened Array,
# like [1,2,3 , 4,5,6 ,7,8,9] for a 3x3 matrix.
matrix = MDMatrix.double([n,n],matrix_as_array)
# until delta <= epsilon do
6.times do
pagerank_old = pagerank
# (1-beta/N) vector.
teleport = (1.0 - beta)
constant = MDMatrix.double([n,1]).fill(teleport/n)
# Actual page rank calculation.
x = matrix * pagerank * beta + constant
# # Re-insert leaked PageRanks.
# Absolute sum of the pagerank scores.
s = x.norm1
s1 = 1.0-s
# Vector correcting dead ends and spider traps.
anti_leak = MDMatrix.double([n,1]).fill(s1/n)
zz = x + anti_leak
pagerank = zz
pagerank.print
# # MDMatrix does not allow subtraction by minus sign.
# # I use a plus b times negative one.
# # #norm1 makes the sum of the column vector's absolute values.
neg_pager = pagerank * -1.0
delta = pagerank_old + neg_pager
# Absolute sum of the scores elements in the delta vector.
delta = delta.norm1
it = it + 1
puts "Power Iteration\t #{it}:\t #{delta.round(5)}"
end
pagerank.print
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment