Ce document décrit un script Python permettant de calculer le PageRank d'un ensemble de pages à partir d'une liste de liens, en prenant en compte l'attribut nofollow qui empêche la transmission de PageRank.

Vous pouvez trouvez le code fonctionnel et utilisable directement depuis ce Notebook Google Colab

Dépendances

Le script repose sur les bibliothèques suivantes :

pandas : pour manipuler les données tabulaires.
networkx : pour la gestion des graphes dirigés.

Installer les dépendances avec pip

pip install pandas networkx

import pandas as pd
import networkx as nx
from google.colab import data_table

Fonction `calcul_pagerank`

La fonction calcul_pagerank prend en entrée :

data (dict) : un dictionnaire contenant les relations entre les pages (source, cible, et nofollow).
iterations (int, par défaut 100) : le nombre d'itérations pour l'algorithme.
damping_factor (float, par défaut 0.85) : le facteur de téléportation du PageRank (classiquement fixé à 0.85).

Elle renvoit en sortie un dataframe contenant le Pagerank de de chaque noeud.

Étapes du calcul de la fonction

def calcul_pagerank(data, iterations=100, damping_factor=0.85):

1. Création d'un DataFrame à partir des données et conversion de `nofollow` en booléen

  df = pd.DataFrame(data)
  df["nofollow"] = df["nofollow"].astype(bool)

2. Initialisation du graphe orienté `DiGraph` avec `networkx`

  G = nx.DiGraph()

3. Ajout des nœuds pour garantir que toutes les URLs sont présentes

  for url in pd.concat([df["source"], df["target"]]).unique():
      G.add_node(url)

4. Initialisation des valeurs de PageRank

Chaque page commence avec une valeur initiale égale à 1 / nombre de pages.

  initial_pr = 1 / len(G.nodes)
  pagerank = {node: initial_pr for node in G.nodes}

5. Boucle d'itération du PageRank

L'algorithme s'exécute pendant iterations cycles pour assurer la convergence.

  for _ in range(iterations):
      new_pagerank = {node: (1 - damping_factor) / len(G.nodes) for node in G.nodes}  # Facteur de téléportation

6. Calcul du PageRank pour chaque nœud

Pour chaque page (nœud), on :

Identifie ses liens sortants.
Vérifie si elle a des liens nofollow.
Redistribue son PageRank uniquement aux liens follow.

      for node in G.nodes:
          outgoing_links = df[df["source"] == node]
          total_links = len(outgoing_links)

          if total_links > 0:
              pr_to_distribute = pagerank[node] * damping_factor  # Part à redistribuer
              follow_links = outgoing_links[~outgoing_links["nofollow"]]
              nb_follow_links = len(follow_links)

              if nb_follow_links > 0:
                  share_per_link = pr_to_distribute / nb_follow_links  # Partage équitable entre les liens follow
                  for _, row in follow_links.iterrows():
                      new_pagerank[row["target"]] += share_per_link  # Attribution du PageRank

7. Mise à jour des valeurs pour l'itération suivante

      pagerank = new_pagerank

8. Retour du résultat sous forme de DataFrame

  return pd.DataFrame(pagerank.items(), columns=["URL", "PageRank"])

Exécution du script

Un jeu de données de test est défini pour illustrer le fonctionnement de la fonction :

data = {
    "source": ["home", "home", "B", "C"],
    "target": ["B", "C", "home", "home"],
    "nofollow": [0, 0, 0, 0]  # 1 = nofollow (le lien ne transmet pas de PageRank)
}

Le calcul du PageRank est lancé et les résultats sont affichés :

pri = calcul_pagerank(data)

Code complet :


import pandas as pd
import networkx as nx

def calcul_pagerank(data,iterations=100,damping_factor=0.85):
  df = pd.DataFrame(data)
  df["nofollow"] = df["nofollow"].astype(bool)

  # 2. Initialisation du graphe
  G = nx.DiGraph()

  # Ajout des noeuds pour assurer que toutes les URLs sont bien présentes
  for url in pd.concat([df["source"], df["target"]]).unique():
      G.add_node(url)

  # 3. Calcul du PageRank en prenant en compte le nofollow
  initial_pr = 1 / len(G.nodes)  # Répartition initiale égale

  # Initialisation des scores de PageRank
  pagerank = {node: initial_pr for node in G.nodes}

  # Boucle d'itération pour convergence (type algo Power Iteration)
  for _ in range(iterations):  # 100 itérations suffisent pour converger en général
      new_pagerank = {node: (1 - damping_factor) / len(G.nodes) for node in G.nodes}  # Restart (facteur téléportation)

      for node in G.nodes:
          outgoing_links = df[df["source"] == node]
          total_links = len(outgoing_links)

          if total_links > 0:
              pr_to_distribute = pagerank[node] * damping_factor  # Part qui va partir de cette URL

              follow_links = outgoing_links[~outgoing_links["nofollow"]]
              nb_follow_links = len(follow_links)

              if nb_follow_links > 0:
                  share_per_link = pr_to_distribute / nb_follow_links  # Partage sur les liens follow
                  for _, row in follow_links.iterrows():
                      new_pagerank[row["target"]] += share_per_link  # On crédite uniquement les liens follow

      pagerank = new_pagerank  # Mise à jour pour la prochaine itération

  # 4. Conversion en DataFrame et affichage avec Google Colab
  return pd.DataFrame(pagerank.items(), columns=["URL", "PageRank"])

data = {
    "source": ["home", "home", "B", "C"],
    "target": ["B", "C", "home", "home"],
    "nofollow": [0, 0, 0, 0]  # 1 = nofollow (le lien ne transmet pas de PageRank)
}
pri = calcul_pagerank(data)
print(pri)