According to the specifications, the iterative PageRank function given corpus0 should return the following:
PageRank Results from Iteration
1.html: 0.2202
2.html: 0.4289
3.html: 0.2202
4.html: 0.1307
My code returns
PageRank Results from Iteration
1.html: 0.2199
2.html: 0.4292
3.html: 0.2199
4.html: 0.1310
I've attached my code below for the iterative function, and I would appreciate any feedback! Thank you so much in advance!
def iterate_pagerank(corpus, damping_factor):
"""
Return PageRank values for each page by iteratively updating
PageRank values until convergence.
Return a dictionary where keys are page names, and values are
their estimated PageRank value (a value between 0 and 1). All
PageRank values should sum to 1.
"""
# Assign each page with rank of 1/n
page_rank = dict()
for page in corpus:
page_rank[page] = 1/(len(corpus))
# Iterate through all pages and calculate page rank
prev_page_rank = copy.deepcopy(page_rank)
anticorpus = make_anti(corpus)
page_rank = iterate_formula(corpus, anticorpus, damping_factor, prev_page_rank)
while dict_diff_over_threshold(prev_page_rank, page_rank, 0.0001):
prev_page_rank = copy.deepcopy(page_rank)
page_rank = iterate_formula(corpus, anticorpus, damping_factor, prev_page_rank)
# Make sure the numbers add up to basically 1
total = round(sum(page_rank.values()), 3)
if total != 1:
print(page_rank)
raise Exception(f"Distribution sum is {total} instead of 1")
return page_rank
def dict_diff_over_threshold(dict1, dict2, threshold):
'''
Returns true if the difference between any two corresponding values
in the two dictionaries exceed the threshold
Otherwise returns False
'''
if len(dict1) != len(dict2) or dict1.keys() != dict2.keys():
raise Exception("You messed up")
new_dict = dict()
for key in dict1:
new_dict[key] = abs(dict1[key] - dict2[key])
if sum(new_dict.values()) > threshold:
return True
return False
def make_anti(corpus):
'''
Creates a dictionary whose keys are pages and values are the pages that
link to keys
'''
for key in corpus:
# If page has no links
if not corpus[key]:
# Make page have links to all pages in corpus
corpus[key] = set(link for link in corpus)
# Find all pages that link to passed page
anticorpus = dict()
# Creates opposite of corpus: each key's value is the set of pages that links to that key
for page in corpus:
for backlink in corpus:
# Check if backlink is a link in the forelink's page
if backlink in corpus[page]:
# Check if set has already been made
if backlink in anticorpus:
anticorpus[backlink] = anticorpus[backlink].union([page])
# Given set doesn't exist yet, make the set
else:
anticorpus[backlink] = set([page])
return anticorpus
def iterate_formula(corpus, anticorpus, damping_factor, current_rank):
'''
Finds the pages that link to a given page and their pagerank
Uses these pageranks to calculate the new pagerank
'''
# Get sum of pagerank/numlinks of backlinks
total_prob = dict()
# Iterate through backlinks and add pagerank/num of links on page
for backlink in anticorpus:
for page in anticorpus[backlink]:
# If backlink already exists in total_prob
if backlink in total_prob:
total_prob[backlink] += current_rank[page]/len(corpus[page])
else:
total_prob[backlink] = current_rank[page]/len(corpus[page])
# Plug into formula
page_rank = dict()
for prob in total_prob:
page_rank[prob] = ((1 - damping_factor)/(len(corpus))) + (damping_factor * total_prob[prob])
# Return the distribution
return page_rank
