pagerank.py

import numpy as np
import sys

## initialization

with open('dataset.csv') as f:
    dataset = f.readlines()

edges = sorted([tuple(int(y) for y in x.split('\t')) for x in dataset])

nodes = set()
for i in edges:
    j, k = i
    nodes.add(j)
    nodes.add(k)
nodes = list(sorted(nodes))

numNodes = len(nodes)

in_neighbors = dict()

nodeMap = {}
mapNode = {}
j = 0
for i in nodes:
    nodeMap[i] = j
    mapNode[j] = i # just in case
    j += 1

adj = np.full((numNodes, numNodes), 0)

for i in edges:
    j, k = i
    adj[nodeMap[j], nodeMap[k]] = 1
    if k in in_neighbors.keys():
        in_neighbors[k].append(j)
    else:
        in_neighbors[k] = [j]

beta = .8

teleport = np.full((numNodes, numNodes),
                   1 / numNodes)

M = np.full((numNodes, numNodes), 0.0)

r = np.full(numNodes, 1 / numNodes)

for j in nodes:
    in_nodes = in_neighbors.get(j)
    if in_nodes == None:
        continue
    for i in in_nodes:
        di = np.sum(adj[nodeMap[i]])
        M[nodeMap[j], nodeMap[i]] = 1 / di

A = beta * M + (1 - beta) * teleport

max_iter = 100
tolerance = 1e-8
for i in range(max_iter): # number of max iterations
    lastR = r
    r = A.dot(r)
    err = np.sum(np.abs(lastR - r))
    if err < tolerance:
        break
else:
    sys.stderr.write('couldn\'t converge after %d iterations.' % max_iter)

res = dict()
for k, v in enumerate(r):
    res[mapNode[k]] = v

res = sorted(res, key=(lambda x: res[x]), reverse=True)