pagerank.py

import numpy

# The link structure
links = {
	'a.com': ['b.com', 'c.com', 'g.com', 'i.com'],
    'b.com': ['d.com', 'c.com', 'a.com'],
    'c.com': ['i.com'],
    'd.com': [],
    'e.com': ['d.com'],
    'f.com': ['c.com'],
    'g.com': ['c.com', 'e.com'],
    'h.com': ['e.com', 'g.com', 'i.com'],
    'i.com': ['h.com', 'f.com', 'd.com'],
}

def page_rank(links, d=0.85, eps=0.01):
	"""
	d = damping factor
	eps = accepted error
	"""
	list_websites = links.keys()
	no_websites = len(list_websites)
	
	# Build the A matrix
	A = []
	for w in list_websites:
		# If the website has no out-links
		if not links.get(w):
			# Link the website to all other websites
			links[w] = [ws for ws in list_websites if ws != w]

		# Build the line of the A matrix
		no_links = len(links.get(w))
		A_line = [0 for _ in xrange(no_websites)]
		
		# Add for each out-link a probability in the line
		for idx, pws in enumerate(list_websites):
			if pws in links.get(w):
				A_line[idx] = 1.0 / no_links
		A.append(A_line)
				
	A = numpy.matrix(A)
	
	prev_p = numpy.matrix([1.0/no_websites for _ in xrange(no_websites)])
	
	while True:
		current_p = numpy.ones(no_websites) * ((1-d)/no_websites) + \
		    d*numpy.transpose(numpy.transpose(A)*numpy.transpose(prev_p))
		if (current_p - prev_p)[0].sum() < eps:
			# The error is reasonable
			return {list_websites[i]: current_p[0, i] for i in xrange(no_websites)}
		prev_p = current_p
		
		
prd = page_rank(links)