PageRank python est un algorithme utilisé par Google Search pour classer les sites Web dans les résultats de leurs moteurs de recherche. PageRank est un moyen de mesurer l’importance des pages de site Web.
Introduction :
Ce n’est pas le seul algorithme utilisé par Google pour ordonner les résultats des moteurs de recherche, mais c’est le premier algorithme utilisé par la société, il est le plus connu.
Le PageRank d’une page est calculé à partir de la somme du PageRank des pages avec un lien entrant à la page calculée que l’on divise par le nombre de pages sortantes de cette dernière, on applique un facteur d’atténuation pour symboliser la probabilité que l’utilisateur surfe sur une autre page.
Implémentation pagerank python :
J’installe networkx, c’est un package Python pour la création, la manipulation et l’étude de la structure, de la dynamique et des fonctions de réseaux complexes.
Networkx fournit des structures de données et des méthodes pour stocker des graphes que j’utilise pour l’algorithme pagerank.
import networkx as nx
import numpy as np
graphe=nx.DiGraph()
tableauPages = ["A","B","C"] #Exemple de page rank avec 3 pages
graphe.add_nodes_from(tableauPages) #Ajout des sommets du graphe
#on ajoute des arcs, on a :
#la page A a un lien vers B
#la page B a un lien vers C
#la page C a un lien vers B
#la page C a un lien vers A
# la page B a 2 lien entrant
# la page C a un lien entrant 2 liens sortant
# la page A a un lien entrant un lien sortant
graphe.add_edges_from([('A','B'), ('C','A'),('B','C'), ('C','B')])
print("Sommets du graphe : ")
print(graphe.nodes())
print("Arrêtes du graphe : ")
print(graphe.edges())
#Si on considere un facteur d'attenuation de 0.85 = d
# la formule du page rank est :
#PR(p) = (1-d)/n + d * Somme de toutes les pages(PR(i) des lien entrants à p/nombre de lien sortant de la page qui reference p)
# PR(A) = (1-0,85)/3 + 0,85 * (PR(C)/2)
# PR(B) = (1-0,85)/3 + 0,85 * (PR(A)/1 + PR(C)/2)
# PR(C) = (1-0,85)/3 + 0,85 * (PR(B)/1)
pagerank = nx.pagerank(graphe)
print(pagerank)
Pagerank python liens externes :
https://fr.wikipedia.org/wiki/M%C3%A9thode_des_k_plus_proches_voisins
https://www.educative.io/blog/python-algorithms-coding-interview