Pagerank implementation.

PageRank.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# PageRank #
# Author: Overxfl0w13 #

from random import randint

def make_ergodic_chain(access_graph,alpha):
	for i in xrange(len(access_graph)):
		if reduce(lambda x,y: x+y,access_graph[i])==0: access_graph[i] = [1.0/len(access_graph[i]) for x in access_graph[i]]
		else: 
			dif_0 = len(filter(lambda x:x!=0,access_graph[i]))
			for j in xrange(len(access_graph[i])):			
				access_graph[i][j] = alpha/len(access_graph[i]) if access_graph[i][j]==0 else ((1-alpha)/dif_0)+(alpha/len(access_graph[i]))
	return access_graph
	
def page_rank(web_adjacency_graph,alpha,random_walk):
	trans_prob = make_ergodic_chain(web_adjacency_graph,alpha)
	aux,ant    = random_walk[:],[0 for x in xrange(len(random_walk))]
	while aux!=ant:
		ant = aux[:]
		aux = vector_x_matrix(aux,trans_prob)
	return aux	

def show_results(pagerank):
	for x in xrange(len(pagerank)): print "La web",x,"tiene un pagerank:",pagerank[x]
			
def vector_x_matrix(v1,m1):
	res = [0 for x in xrange(len(v1))]
	for j in xrange(len(res)):
		for k in xrange(len(res)): res[j] += v1[k]*m1[k][j]	
	return res
	
	
	
if __name__ == "__main__":
	web_adjacency_graph = [[0,0,1,0,0,0,0],[0,1,1,0,0,0,0],[1,0,1,1,0,0,0],[0,0,0,1,1,0,0],[0,0,0,0,0,0,1],[0,0,0,0,0,1,1],[0,0,0,1,1,0,1]]
	alpha       = 0.14
	random_walk = [0 for x in xrange(len(web_adjacency_graph[0]))]
	random_walk[randint(1,len(random_walk))-1] = 1
	show_results(page_rank(web_adjacency_graph,alpha,random_walk))