# PageRank example
# CS 121 A'15
#
# This file contains the functions necessary to compute the PageRank of nodes
# in a graph where nodes represent websites and edges represent links
# between websites.
#
# You can import the individual functions, or run pagerank.py as a program:
#
# python3 pagerank.py <-r or -m>
#
# Where:
#
# - Specify "-r" to use the random surfer model, or "-m" to use Markov chains.
# - is the name of the file containing the graph
# - is the number of steps to take in the simulation.
#
import sys
import random
def read_graph(filename):
'''
Reads a graph from a file, and returns a matrix of counts (as a
list-of-lists, where each entry (i,j) is the number of links from
node i to j, and a list with the out-degrees of each node.
Inputs:
filename: (string) name of file containing the graph
Returns: tuple w/
List of lists of int with matrix of link counts
List of integers with out-degrees of each node.
'''
try:
f = open(filename)
except (OSError, IOError) as e:
print("Error opening file {}: {}".format(filename, e))
sys.exit(1)
try:
n = int(f.readline())
out_degree = [0]*n
counts = []
for i in range(n):
counts.append([0]*n)
tokens = f.read().strip().split()
assert(len(tokens) % 2 == 0)
while len(tokens) > 0:
u = int(tokens.pop(0))
v = int(tokens.pop(0))
out_degree[u] += 1
counts[u][v] += 1
except (OSError, IOError) as e:
print("Error reading file {}: {}".format(filename, e))
sys.exit(1)
f.close()
return counts, out_degree
def compute_transition(counts, out_degree):
'''
Compute the transition matrix for the graph. This matrix tells
us, for each (i,j), the probability that, if the random surfer is
in node i, the next page they visit is j.
Inputs:
counts: (list of lists of int) matrix of link counts
out_degree: (list of integers) out-degrees of each node.
Returns: list of lists of floats representing the transition matrix
'''
n = len(out_degree)
transition_matrix = []
for i in range(n):
transition_matrix.append([0]*n)
for i in range(n):
for j in range(n):
transition_matrix[i][j] = (0.9 * counts[i][j]/out_degree[i]) + (0.1 * 1/n)
return transition_matrix
def make_one_move(transition_matrix, page):
'''
Compute the next page for the random surfer based on the current
page and the transition matrix
Inputs:
transition_matrix: (list of lists of floats)
page: (int) The current page the random surfer is on
Returns: (int) next page the random surfer will visit
'''
n = len(transition_matrix)
r = random.uniform(0.0, 1.0)
psum = 0.0
for j in range(n):
psum += transition_matrix[page][j]
if psum >= r:
return j
return n
def random_surfer(transition_matrix, num_steps):
'''
Simulate the random surfer using the given transition matrix for
the specified number of steps
Inputs:
transition_matrix (list of lists of floats) representing the
transition matrix
num_steps: (int) number of steps to run the simulation
Returns: Nothing (prints out the rank of each page)
'''
n = len(transition_matrix)
page = 0
times_visited = [0]*n
for t in range(num_steps):
page = make_one_move(transition_matrix, page)
times_visited[page] += 1
for count in times_visited:
v = count / num_steps
print("{:.3f}".format(v), end=" ")
print()
# Not discussed in Sections 1 and 3.
def markov_mixing(transition_matrix, num_steps):
'''
Compute the page ranks using num_steps vector-matrix
multiplications.
Inputs:
transition_matrix: (list of lists of floats) representing the transition matrix
num_steps: (int) Number of matrix multiplications to perform
Returns: Nothing (prints out the rank of each page)
'''
n = len(transition_matrix)
rank = [0]*n
rank[0] = 1.0
for t in range(num_steps):
new_rank = [0]*n
for i in range(n):
for j in range(n):
new_rank[i] = new_rank[i] + rank[j] * transition_matrix[j][i]
rank = new_rank
for r in rank:
print("{:.3f}".format(r), end=" ")
print()
if __name__ == "__main__":
if len(sys.argv) != 4 or sys.argv[1] not in ("-r","-m"):
print("Usage: {} <-r or -m> ".format(sys.argv[0]))
sys.exit(1)
counts, out_degree = read_graph(sys.argv[2])
transition_matrix = compute_transition(counts, out_degree)
num_steps = int(sys.argv[3])
if sys.argv[1] == "-r":
random_surfer(transition_matrix, num_steps)
elif sys.argv[1] == "-m":
markov_mixing(transition_matrix, num_steps)