El proyecto se encuentra en https://cs50.harvard.edu/ai/2020/projects/2/pagerank/
Aquí se deben hacer dos implementaciones para calcular el Pagerank:
- La primera implementación es el Modelo del Surfista Aleatorio (Random Surfer Model). En resumen, el algoritmo debe iterar a través de todas las páginas, escoger una de las páginas enlazadas, y contar cuántas veces se escogió cada página. Las reglas de cómo se debe escoger cada página están en la función transition_model, que devuelve la probabilidad con la que se debe escoger cada página. Los valores devueltos por la función transition_model deben sumar 1, para esto se tienen dos conjuntos de valores, las páginas enlazadas desde una página determinada (el conjunto de páginas que se está evaluando), y todas las otras páginas. Si una página pertenece al conjunto de páginas que estamos evaluando, la distribución de probabilidad es el factor damping_factor/Número de páginas en el conjunto. Si una página no está en el conjunto, la probabilidad es de (1 - el factor damping_factor)/el total de páginas que no pertenecen al conjunto. Lo que debe devolver esta función es una proporción, por ello al final se dividen los resultados entre el total de páginas.
La función transition_model es:
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.
"""
N = len(corpus[page])
M = len(corpus)
distr = { }
if N == 0:
distr = { c: 1 / M for c in corpus.keys() }
else:
for p in corpus.keys():
if p in corpus[page]:
distr[p] = damping_factor / N
else:
distr[p] = (1 - damping_factor) / (M - N)
return distr
La función para esta primera implementación es:
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.
"""
pageranks = {p : 0 for p in corpus.keys()}
page = random.choice(list(corpus.keys()))
trans = transition_model(corpus, page, damping_factor)
pageranks[page] = 1
for _ in range(1, n):
links = []
weights_ = []
for p in trans.keys():
links.append(p)
weights_.append(trans[p])
page = random.choices(links, weights = weights_, k = 1)
pageranks[page[0]] += 1
trans = transition_model(corpus, page[0], damping_factor)
return {p : pageranks[p] / n for p in pageranks.keys()}
- La segunda implementación es el Método Iterativo, el cual escoge una página cualquiera para empezar a calcular el valor de Page_rank mediante la fórmula:
La iteración se detiene cuando la diferencia entre PR(p) calculado en la iteración actual (variable pagerank) y el PR(p) calculado en la iteración anterior (variable pagerank2) es muy pequeña. La variable temp almacena el valor dentro de la sumatoria (cantidad de páginas enlazadas desde la página p). Si el valor resulta cero (no hay páginas enlazadas) se le asigna el valor 1/N.
La función en este caso es iterative_pagerank:
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.
"""
N = len(corpus)
pagerank = { p : 1 / N for p in corpus.keys() }
pagerank2 = { p : 0 for p in corpus.keys() }
stop = False
while not stop:
for p in corpus.keys():
temp = 0
for i in corpus:
if p in corpus[i]:
temp += pagerank[i] / len(corpus[i])
if temp == 0:
temp = 1 / N
pagerank[p] = (1 - damping_factor) / N + temp * damping_factor
stop = True
for p in corpus.keys():
if abs(pagerank[p] - pagerank2[p]) > 0.001:
stop = False
break
pagerank2 = copy.deepcopy(pagerank)
return pagerank
