Envoyer un mail à l’auteur
xavier at ultra-fluide.com

Ressources

• Marquage sémantique XSLT
• CSS
• XHTML
• Extensions Firefox
• TrustRank, anti-spam
  • Introduction
  • Préliminaires
  • Fonction de confiance
  • Amortissement de la confiance
  • Echantillon initial
  • Résultats
  • Conclusion
• Datamining
• Divers web

Combattre le spamdexing avec le TrustRank.

[Remarque : cette page nécessite un navigateur pourvu d'un moteur de rendu MathML pour visualiser les formules mathématiques.]

2 Préliminaires

2.1 Modélisation du web

Figure 1: exemple de graphe web simple

Nous modélisons le web comme un graphe G=(V,E) consistant en un ensemble V de N pages (sommets du graphe) et un ensemble E de liens orientés (arcs du graphe) qui connectent les pages. Dans la réalité, une page p peut avoir plusieurs hyperliens vers une autre page q. Dans ce cas l'ensemble de ces liens de p vers q forme une classe qui est élément de E, (p,q)∈E. Les liens d'une page sur elle-même ne sont pas pris en compte. La figure 1 présente un graphe simple de quatre pages et quatre liens. Lors de nos expérimentations chapitre 6, nous travaillons avec des sites web en lieu et place de pages web. Modèle et algorithmes sont adaptés à la situation ou les sommets du graphe sont des sites entiers.
Chaque page a des liens entrant "inlinks", et des liens sortant "outlinks". Le nombre de liens entrant d'une page p est son "taux entrant" τ(p), alors que le nombre de liens sortant sera désigné "taux sortant" ω(p). Par exemple le taux entrant de la page 3 figure 1 est de un alors que son taux sortant est de 2.
Les pages n'ayant pas de liens entrant sont des "pages sans références". Les pages sans liens sortant sont des "pages ne référençant pas". Les pages à la fois sans références et ne référençant pas sont des "pages isolées". La page 1 de la Figure 1 est une page sans référence, tandis que la page 4 ne référence pas.
Nous introduisons deux représentations matricielles d'un graphe web qui auront un rôle important dans la suite. La première est la "matrice de transition" T :

$T(p,q)=\{\begin{array}{cc}0\hfill & \hfill \text{si }(q,p)\notin E\hfill \\ 1/\omega \left(q\right)\hfill & \hfill \text{si }(q,p)\in E\hfill \end{array}$

La matrice de transition correspondant au graphe de la Figure 1 est la suivante :

$T=\left(\begin{array}{cccc}0& 0& 0& 0\\ 1& 0& \frac{1}{2}& 0\\ 0& 1& 0& 0\\ 0& 0& \frac{1}{2}& 0\end{array}\right)$

Nous définissons également la "matrice de transition inverse" :

$U(p,q)=\{\begin{array}{cc}0\hfill & \hfill \text{si }(p,q)\notin E\hfill \\ 1/\tau \left(q\right)\hfill & \hfill \text{si }(p,q)\in E\hfill \end{array}$

Notons que $U\ne T^T$. La matrice de transition inverse correspondant au graphe de la Figure 1 est la suivante :

$T=\left(\begin{array}{cccc}0& \frac{1}{2}& 0& 0\\ 0& 0& 1& 0\\ 0& \frac{1}{2}& 0& 1\\ 0& 0& 0& 0\end{array}\right)$

2.2 PageRank

Le PageRank est un algorithme bien connu utilisant l'information véhiculée par les liens pour calculer une notoriété à chaque page du web. Nos algorithmes reposant sur le PageRank, nous proposons donc maintenant un rappel sur cette notion.
L'idée intuitive véhiculée par le PageRank exprime le fait qu'une page web disposera d'une bonne notoriété dès que d'autres pages web de bonne notoriété pointeront vers elle.
Corrélativement, le PageRank repose sur le renforcement mutuel entre pages : la notoriété d'une page influence et est influencée par la notoriété d'autres pages.

Le PageRank d'une page p est défini comme suit :

$r\left(p\right)=\alpha \sum _{q:(q,p)\in E}\frac{r\left(q\right)}{\omega \left(q\right)}+(1-\alpha )\frac{1}{N}$

ou α est un facteur de décroissance (en fait il y a de nombreuses définitions du PageRank [12] qui diffèrent dans leur formulation mathématique et dans les résultats numériques, mais qui conduisent au même classement relatif entre pages). L'équation matricielle équivalente est de la forme :

$r=\alpha Tr+(1-\alpha )\frac{1}{N}{1}_N$

Le score d'une page p est donc la somme de deux composantes : l'une provenant des pages pointant vers p, l'autre statique est une constante identique pour toutes les pages.
Le PageRank peut être calculé par itération, en appliquant par exemple la méthode de Jacobi [3]. Dans une vision purement mathématique, les itérations doivent être appliquées jusqu'à la convergence, dans la pratique il est courant de se fixer un nombre M d'itérations.

Il est important de noter que l'algorithme classique du PageRank introduit un terme statique constant sur l'ensemble des pages, mais qu'une version biaisée du PageRank pourrait rompre avec cette règle. Dans cette équation matricielle

$r=\alpha Tr+(1-\alpha )d$

le vecteur d est une distribution arbitraire de la composante statique formée de valeurs positives ou nulles dont la somme vaut 1. Le vecteur d peut être utilisé pour assigner une composante statique non nulle à un ensemble spécifique de pages. Du coup le score de ces pages se diffuse pendant les itérations aux pages vers lesquelles elles pointent.