-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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