-
Notifications
You must be signed in to change notification settings - Fork 0
/
pagerank.py
167 lines (139 loc) · 4.93 KB
/
pagerank.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
import os
import random
import re
import sys
import numpy
from collections import Counter
DAMPING = 0.85
SAMPLES = 10000
def main():
#if len(sys.argv) != 2:
# sys.exit("Usage: python pagerank.py corpus")
ff = 'C:/Users/iTTaste/Desktop/CS50Beyond/pagerank/corpus0'
corpus = crawl(ff)
ranks = sample_pagerank(corpus, DAMPING, SAMPLES)
print(f"PageRank Results from Sampling (n = {SAMPLES})")
for page in sorted(ranks):
print(f" {page}: {ranks[page]:.4f}")
ranks = iterate_pagerank(corpus, DAMPING)
print(f"PageRank Results from Iteration")
for page in sorted(ranks):
print(f" {page}: {ranks[page]:.4f}")
def crawl(directory):
"""
Parse a directory of HTML pages and check for links to other pages.
Return a dictionary where each key is a page, and values are
a list of all other pages in the corpus that are linked to by the page.
"""
pages = dict()
# Extract all links from HTML files
for filename in os.listdir(directory):
if not filename.endswith(".html"):
continue
with open(os.path.join(directory, filename)) as f:
contents = f.read()
links = re.findall(r"<a\s+(?:[^>]*?)href=\"([^\"]*)\"", contents)
pages[filename] = set(links) - {filename}
# Only include links to other pages in the corpus
for filename in pages:
pages[filename] = set(
link for link in pages[filename]
if link in pages
)
print('Corpus: ',pages)
transition_model(pages, '3.html', DAMPING)
return pages
def transition_model(corpus, page, damping_factor):
"""
Return a probability distribution over which page to visit next,
given a current page.
With probability `damping_factor`, choose a link at random
linked to by `page`. With probability `1 - damping_factor`, choose
a link at random chosen from all pages in the corpus.
"""
page_prob_dict = dict()
page_prob = (1 - damping_factor) / (len(corpus[page]) + 1)
prob_links = damping_factor / len(corpus[page]) + page_prob
page_prob_dict[page] = page_prob
for link in corpus[page]:
page_prob_dict[link] = prob_links
return page_prob_dict
def sample_pagerank(corpus, damping_factor, n):
"""
Return PageRank values for each page by sampling `n` pages
according to transition model, starting with a page at random.
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.
"""
page_rank = dict()
page = '3.html'
transition_matrix = transition_model(corpus,page,damping_factor)
#print('Transition matrix',transition_matrix)
pages = list(corpus.keys())
hits = []
for i in range(n):
#Make a random move
r = random.random()
total = 0.0
for j in range(0, len(transition_matrix.values())):
#Find interval containing r
total += list(transition_matrix.values())[j]
if total > r:
page = list(transition_matrix.keys())[j]
break
hits.append(page)
#Write the page ranks
page_rank = Counter(hits)
for p in page_rank:
page_rank[p] = page_rank[p] / len(hits)
return page_rank
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.
"""
rank = dict()
repeat = True
#calculate pages initial rank
total_pg = total_pages(corpus)
for page in corpus:
rank[page] = 1 / len(corpus.keys())
# calculate the first portion of formula
first_portion = (1-damping_factor) / total_pg
#calculate page rank based on formula
while repeat is True:
old_rank = rank.copy()
for pg in corpus:
new_rank = first_portion + calc_second_portion(pg, rank, corpus)
rank[pg] = new_rank
for key in rank:
if key in old_rank:
if (abs(rank[key] - old_rank[key]) <= 0.001):
repeat = False
return rank
def total_pages(corpus):
return len(corpus.keys())
def pr(page, corpus):
relevant_links = []
for key, links in corpus.items():
for link in links:
if link == page:
relevant_links.append(key)
return relevant_links
def num_liks(corpus, page):
page_degree = len(corpus[page])
return page_degree
def calc_second_portion(page, rank, corpus):
#Calculate second portion of the formula
pr_i = pr(page, corpus)
sum = 0.0
for i in pr_i:
sum += rank[i] / num_liks(corpus,i)
second_portion = DAMPING * sum
return second_portion
if __name__ == "__main__":
main()