Télécharger le fichier original (Mémoire de fin d’études)

PAGERANK

Notions préliminaires

Dans la suite le web est représenté par le graphe orientéG = (V, E), appeléle graphe du web, dont l’ensemble V contient n nœuds qui représentent les identifiants URL (Uniform Resour ce Lo-cator) des documents web, et l’ensemble E ⊂ V 2 contient les arcs représentant les liens hypertextes entre ces pages. Les documents web sont des documents HTML, XML, PDF, etc.
A chaque page i on associe les variables suivantes :
– xi : le score d’importance de la page i
– in(i) : l’ensemble des pages qui ont un lien vers i
– out(i) : l’ensemble des pages vers lesquelles la page i a un lien
– out deg(i) : le nombre de liens sortants de i (out deg(i) = |out(i)|)
– indeg(i) : le nombre de liens qui référencent la pagei (indeg(i) = |in(i)|)
La matrice de transition associée au graphe du web, notée parL, est une matrice non-négative (L ≥ 0) dont l’élément ji sur la ligne j et la colonne i représente la partie de l’importance de la page i qui est donnée à la page j. Les valeurs de l ji sont différentes suivant l’algorithme de calcul d’importance considéré.

Modèle

L’algorithme de PAGERANK est utilisé par le moteur de recherche GOOGLE[84] afin de classer les pages web retournées comme réponses à l’utilisateur. Enréalité, les score d’importance des pages ne prend pas seulement en considération le score PAGERANK, mais aussi d’autres facteurs, comme des mesures utilisées dans la recherche d’information (IR), la proximité sémantique et le texte des liens hypertextes entre les pages ([168, 40]). Ces autres paramètres et la façon dont ils sont combinés entre eux ne sont pas connus publiquement.
Il existe deux versions du calcul de PAGERANK qui sont utilisées dans la littérature. Brin et Page ont proposé une première équation qui a été ensuite modifiéeourp modéliser la marche aléatoire d’un utilisateur sur le graphe du web.

Première version dePAGERANK

Dans la première version de PAGERANK [41] l’importance x j d’une page j est proportionnelle à l’importance des pages i qui la référencent et inversement proportionnelle au nombre total de pages vers lesquelles i a des liens :
x j = d × å xi + (1 − d)
out deg(i)
i∈in( j)
où d ∈ (0, 1) est le facteur de décroissancedont la valeur est choisie comme étant 0.85. En représentant toutes les valeursx j par un vecteur x ∈n×1, l’importance des pages web peut être calculée comme étant la solution du système linéaire suivant : x = d × L × x + (1 − d) × In×1 (2.1) où In×1 = [1, . . . , 1] est le vecteur identité et la valeur de chaque élémentji sur la ligne j et la colonne i dans la matrice L est égale à 1/out deg(i) si i a des liens sortants et 0 dans le cas contraire. La matrice L n’est pas stochastique sur les colonnes (la somme des éléments sur chaque colonne n’est pas 1) s’il existe des pages sans liens sortants.
La solution de ce système peut être calculée itérativement epartant d’une approximation ini-tiale de l’importance x0 et en calculant à chaque pas k une nouvelle approximation xk en fonction de l’importance au pas (k − 1) : xk = d × L × x(k−1) + (1 − d) × In×1 (2.2)
Le système 2.1 a une solution unique et la séquence{xk } 2.2 converge vers cette solution, puisque d < 1 et dans ce cas le rayon spectral de la matrice d × L (la valeur propre de valeur maximale) est inférieur à 1 [31]. Le calcul d’importance correspond à l’algorithme itératif de Jacobi pour la résolution des systèmes linéaires.
Interprétation du calcul d’importance : Nous pouvons modéliser le calcul d’importance par la marche aléatoire de plusieurs utilisateurs sur le graphe duweb [31]. Ainsi, l’importance d’une page j calculée avec l’équation 2.1 représente lenombre d’utilisateurs estimé de la page j aux pas k > K, pour un K suffisamment grand. Les utilisateurs qui arrivent sur la pag e j sont ceux qui suivent les liens existants dans les autres pages et qui mènent à cette page, ainsi que les utilisateurs qui choisissent directement cette page.
A chaque pas k du calcul itératif 2.2, sur chaque page j il existe (1 − d) utilisateurs qui com-mencent leur navigation sur cette page. Un utilisateur qui se trouve au pas (k − 1) sur la page j peut exécuter les actions suivantes au pask :
– avec une probabilité constante (1 − d) il peut arrêter sa navigation, sinon
– il continue à naviguer (avec la probabilité d) en suivant les liens sortants, chaque lien sortant étant choisi avec une probabilité de /1out deg( j) ;
– si j est une page sans liens sortants (« dangling page ») alors avec une probabilité de 1 l’uti-lisateur arrête sa navigation.
Cette première méthode de calcul de PAGERANK ne correspondait pas à la sémantique que ses auteurs voulait donner au calcul d’importance. Le calcul de PAGERANK est décrit par la marche aléatoire d’un seul utilisateur (à la différence de la première proposition), qui visite infiniment chaque page web en suivant les liens hypertextes. Ainsi, une nouvelle définition de PAGERANK a été proposée par la suite [40, 144].

Deuxième version dePAGERANK

L’importance d’une page j dépend comme précédemment, de l’importance des pagesiqui la référencent :
x j = å xi
out deg(i)
i∈in( j)
Si x ∈n×1 est le vecteur qui regroupe toutes les valeurs d’importance x j , alors l’importance peut être écrite comme étant : x = L × x où chaque élémentji de L représente la probabilité que l’utilisateur choisisse de isiterv la page j lorsqu’il se trouve sur la page i. La marche aléatoire d’un utilisateur sur le graphe du web est modélisée par une chaîne de Markov avec la matrice de transiton L dont les états sont lesn nœuds représentant les pages dans le graphe du web. L’utilisateurchoisit initialement avec une probabilité de x0j une page j parmi les n pages du graphe. À chaque pas (k −1) il se trouve sur une page i avec une probabilité dex(ik−1) et choisit au pas k de suivre un des liens sortants de i avec une probabilité de 1/oudeg(i). L’évolution de la chaîne de Markov est exprimée par l’équation suivante qui calcule la distribution de probabilité au pask en fonction de la probabilité au pask − 1 en partant d’une distribution de probabilité initialex0 : xk = L × x(k−1) (2.3)
Dans le cas où ||x||1 = 1 (|| || 1 est la norme de 1), chaque valeur x j converge vers la probabilité stationnaire que l’utilisateur se trouve sur la page j lorsqu’il continue sa marche aléatoire à l’infini. Le calcul est arrêté lorsque la différence des approximations à différentes itérations est inférieure à un donné (||xk − x(k−1) ||1 ≤).
Afin que le calcul d’importance converge il est nécessaire que la chaîne de Markov ait une pro-babilité stationnaire unique. Ceci se traduit par le fait que le graphe de la marche aléatoire doit être fortement connexe et apériodique, ce qui correspond à neu matrice de transition irréductible et primitive. Du point de vue de la marche aléatoire, afin que le calcul d’importance converge il faut que l’utilisateur puisse visiter toutes les pages du web infi niment souvent. Brin et al. [40, 144] ont identifié deux situations qui empêchent l’utilisateur de visiter toutes les pages :
(i) lorsqu’il existe des pages sans liens sortants (« dangling pages »), l’utilisateur ne peut pas continuer sa visite des pages et il sort du système. Dans ce cas les valeurs sur la colonne de la matrice L correspondant à cette page sont zéro ;
(ii) lorsque l’utilisateur qui suit les liens entre les pages arrive sur un ensemble de pages qui ont des liens seulement entre elles, sans avoir de liens vers l’extérieur. Dans ce cas, l’utilisateur va « être attrapé » par ces pages et va choisir infiniment seulement les pages dans cet en-semble (ces pages forment ce qu’on appelle un « rank sink »).
Nous allons présenter dans la suite plusieurs méthodes qui nto été proposées pour modifier la matrice L et le graphe du web afin d’assurer les conditions nécessaires pour la convergence.
(i) Éliminer les pages sans liens sortants : Les documents sans liens sortants peuvent être par exemple les fichiers PDF, les images, les pages qui n’ont pas e ncore été explorées par le navigateur, celles qui sont protégées, etc. Plusieurs méthodes ont étéro posées pour éliminer les pages sans liens sortants. La méthode la plus utilisée a été proposéer pa[137, 144, 98, 110]. Elle consiste à modifier la matrice L en remplaçant chaque colonne i de L qui correspond à une page sans liens sortants par un vecteur vn×1 = (1/n, . . . , 1/n). Le graphe du web est ainsi modifié en concordance en ajoutant à partir de chaque pages sans liens sortants des l iens de poids 1/n vers toutes les pages du web. La nouvelle matrice obtenue après cette modification peut s’écrire comme étant : L = L + v × R où R1×n = [r1, . . . , rn]T est tel que ri = 1 si i est une page sans liens sortants et ri = 0 dans le cas contraire. La matrice L obtenue est une matrice stochastique suivant les colonnes, c’est à dire que la somme des valeurs sur toutes les colonnes est 1. Nous observons maintenant, sur le nouveau graphe du web correspondant à L, que lorsque l’utilisateur se trouve sur une page terminale il ne sort plus du système, mais il choisit avec une probabilité uniforme n’importe quelle page du graphe.
Dans la littérature il existe d’autres méthodes pour éliminer les pages sans liens sortants. Ainsi, les auteurs de PAGERANK proposent initialement dans [143] d’enlever les nœuds sans liens sor-tants du graphe du web et de calculer ensuite les scores d’importance sur ce graphe, la raison étant que ces pages n’ont pas d’influence sur le classement des page s web. La même proposition a aussi été faite par [95]. Une autre méthode suggérée par [143] est renormaliserd L × x(k−1) afin que la norme du vecteur xk reste toujours 1, et de redistribuer de cette manière le score « perdu » à cause des pages sans liens sortants parmi toutes les pages du graphe web. À chaque pas k du calcul itératif, le vecteurxk est calculé après la normalisation comme étant : xk = d × L × x(k−1) + v × (||x(k−1)||1 − ||d × L × x(k−1) ||1) (2.4) où le score « perdu » (||x(k−1)||1 − ||d × L × x(k−1) ||1) est redistribué parmi les nœuds du graphe suivant le vecteur de distribution vn×1 comme précédemment. [71] montre que l’effet des pages sans liens sortants sur le classement des pages web est significatif et qu’elles constituent une large fraction du web. Si l’on enlève les nœuds sans liens sortants ceci amène à modifier les scores pour les nœuds restants, puisque les poids sur les liens sortants des pages sont modifiés pour refléter l’absence de liens vers les nœuds terminaux. De plus, [121] m ontre que le fait d’ignorer les nœuds sans liens sortants n’accélère pas la convergence du calculet propose un calcul de PAGERANK en deux étapes :(i) dans la première étape l’importance est obtenue en utilisan un graphe modifié dans lequel toutes les pages sans liens sortants sont combinées dans un seul nœud et (ii) dans une deuxième étape l’importance est calculée sur un graphe ansd lequel seulement les nœuds qui ont des liens sortants sont combinés entre eux. Les deux scores d’importance ainsi obtenus sont ensuite concaténés pour obtenir le score de AGEPRANK final. [109] suggère d’enlever les pages sans liens sortants pendant le calcul et de les réinsérer pendant les dernières itérations. Les auteurs mentionnent aussi une autre méthode pour éliminer le problème des nœuds sans liens sortants, en considérant que lorsque l’utilisateur se trouve sur un nœud terminal il choisit avec une probabilité de 1 aléatoirement une page du graphe. Une autre possibilitéest d’ajouter un lien sortant de chaque page terminale vers soi-même et d’ajuster ensuite le score PAGERANK après la fin du calcul [104].
La matrice et le graphe obtenus après la modification des page s sans liens sortants ne satisfont pas les conditions nécessaires pour la convergence. Le graphe du web doit être à nouveau modifié pour éliminer les groupes de pages sans liens sortants.
(ii) Éliminer les groupes de pages sans liens sortants : En ajoutant des liens sortants de chaque page dans le graphe vers toutes les autres pages, y compris soi-même, on obtient un graphe de transition complet (qui est donc fortement connexe). La matrice de transition L qui correspond à ce graphe est une matrice irréductible et est obtenue en partant de la matrice L comme suit : L = d × L + (1 − d) × v × I1×n où vn×1 et d sont définis comme précédemment. Le vecteurv s’appelle vecteur de personna-lisation et il montre la manière dont l’importance de chaque page est distribuée aux autres pages du système. Différentes valeurs ded donnent des vitesses de convergence et des classements dif-férents [119]. Par exemple [32] montre que sid est 1, le score d’importance des nœuds importants (ceux qui se trouvent au centre du graphe) devient 0, le score d’importance se concentrant alors sur les nœuds pas importants. La valeur « standard » choisie e st de 0.85 qui est un bon compromis entre l’obtention d’une convergence rapide avec des perturbations minimales du classement.
La matrice de transition L est primitive et la chaîne de Markov associée estapériodique. En effet, pour qu’une chaîne de Markov soit apériodique, il estnécessaire que chaque nœud ait une période de 1, la période d’un nœud étant définie comme étant leplus grand diviseur commun de tous les cycles dans le graphe qui passent par ce nœud. Comme c haque nœud dans le graphe correspondant à la matrice L à un arc vers soi-même de poids(1 −d)/n, le plus petit diviseur commun de tous les cycles qui passent par chaque nœud est 1 et la chaîn e de Markov est donc apériodique.
Ces modifications correspondent à une nouvelle marche aléat oire pendant laquelle l’utilisateur exécute les actions suivantes lorsqu’il se trouve sur le page i :
– si la page i n’est pas une page terminale (sans liens sortants) :
(i) avec la probabilitéd il choisit de suivre un lien sortant de la page ; chaque page j réfé-rencée pari est choisie avec la probabilité 1/out deg(i) ;
(ii) avec la probabilité(1 − d) il choisit n’importe quelle page de graphe web, chaque page j ayant une probabilité dev j d’être choisie ;
– si i est une page terminale, alors l’utilisateur choisit une page j du graphe web, chaque page
ayant la probabilité d’être choisie donnée parv.
xk = × x(k−1) (2.5)
L = (d × (L + v × R) + (1 − d) × v × I1×n) × x(k−1)
ce qui correspond au calcul de la distribution stationnaire de la chaîne de Markov qui est aussi le vecteur dominant de la matrice L. L’équation 2.5 est la méthode de la puissance pour détermi-ner la plus grande valeur propre et le vecteur propre dominant de la matrice L. Le calcul itératif est démarré avec une distribution de probabilité initialex0 (||x0||1 = 1) et répété jusqu’à ce que la condition de convergence soit satisfaite. Nous observons qu’à n’importe quel pas k de l’algo-rithme la somme des scores d’importance est toujours 1, l’importance n’étant plus « perdue » par le système. Puisque la matrice est irréductible et primitive, le vecteur de probabilité stationnaire de la chaîne de Markov existe et est unique et la méthode de la puissance converge vers ce vecteur indépendamment dex0.
(iii) Autre méthode pour assurer la marche aléatoire à l’infini : Une méthode équivalente pour garder la somme des scores d’importance constante pendant le calcul, sans modifier la matrice de transition initiale L a été proposée par les auteurs deAGEPRANK [40]. Nous allons présenter cette méthode et montrer qu’elle calcule les mêmes scores d’importance que l’équation 2.5. L’algo-rithme suivant garde la norme du vecteur x à 1 en redistribuant l’importance « perdue » du système aux pages du web, en concordance avec le vecteur de personnalisation v :
xk = d × L × x(k−1)
a = ||x(k−1)||1 − ||xk ||1
xk = xk + × v
Nous observons que l’importance xk est calculée avec la formule dans l’équation 2.4. Après la multiplication d × L × x(k−1) , une partie du score total d’importance ||x(k−1)||1 dans le système est
« perdu » de la manière suivante :
– seulement la partie d du score x(ik−1) des pages i qui ne sont pas des pages terminales est redistribué à nouveau dans le système, le score(1 − d)x(ik−1) étant perdu ;
– le score x(ik−1) des pages terminales est perdu entièrement, n’étant redistribué à aucune autre page.
En notant par T l’ensemble de pages terminales (sans liens sortants) du système, le score total
qui est « perdu » du système peut par conséquent être calculéommec étant :
||x(k−1) − d × L × x(k−1) ||1 = å xi(k−1) + (1 − d) × å xi(k−1)
i∈T i∈S
= (1 − d) + d × å xi(k−1)
i∈T
Comme d ×åi∈T x(ik−1) peut être réécrit comme étantd×R ×x(k−1) et I1×n ×x(k−1) = 1, l’équa-tion 2.4 peut être transformée en équation 2.5 comme suit :
xk = d × L × x(k−1) + v × (||x(k−1)||1 − ||dLx(k−1) ||1)
= d × L × x(k−1) + v × ((1 − d) + d × R × x(k−1) )
= (d × (L + v × R) + (1 − d) × v × I1×n) × x(k−1)

Équivalence entre les deux algorithmes de calcul de PAGERANK

La première version de PAGERANK décrite par l’équation 2.1 produit le même classement des pages que la deuxième version qui est présentée dans l’équation 2.5, lorsque le vecteur de personnalisation est v = 1n ×In×1 [31]. De plus, si l’on note par x le vecteur d’importance x calculé par l’équation 2.5, celui-ci est obtenu après la normalisation du vecteur x calculé par l’équation 2.1 dans la première version de PAGERANK : x = ||x||1
Ceci montre que, si nous nous intéressons seulement au classement des pages et non pas aux valeurs particulières de l’importance, nous pouvons utiliser les deux méthodes de calcul de PA-GERANK de façon interchangeable. La première version ne demande pas des modifications sur la matrice web, ce qui est d’autant plus utilise si nous calculons des scores d’importance en distribué.

Méthode de la puissance

La méthode suggérée initialement pour calculer les scores edPAGERANK se nomme la mé-thode de la puissance. L’importance est calculée « off-line», indépendamment des requêtes, à l’aide du calcul itératif de l’équation 2.5 sur le graphe du web construit avec les pages trouvées par le crawler et les liens entre elles. Le calcul d’importance est arrêté lorsqu’on obtient une approxima-tion suffisamment bonne de l’importance. En pratique, les it érations sont arrêtées lorsque l’erreur ||x(k) − x(k−1) ||1 < e, pour un e donné.

Convergence

La vitesse à laquelle l’erreur ||x(k) −x(k−1) ||1 s’approche de 0 représente le taux de convergence. Pour la méthode de la puissance, ce taux est de|l2|/|l1|, où |l1| est la valeur propre maximale de la matrice L, c’est à dire pour cette matrice une valeur de 1, et l2 est la valeur propre qui est la deuxième plus grande aprèsl1. [97] montre que la valeur de l2 est le d de PAGERANK , et par conséquent le taux de convergence de la méthode de la puissance est d. Ceci implique donc que le mécanisme introduit afin d’assurer les propriétés de la matrice de transition détermine le taux de convergence car la vitesse de convergence devient plus lente lorsque |l2| est très proche de |l 1|. La valeur de d utilisée par Google est de 0.85 et le nombre d’itérations estimées poure = 10−6 est de 50-100 [119]. Des résultats similaires sur la convergence ont été annoncés par [95, 144], qui ont trouvé expérimentalement un nombre d’itérations de 52 pourun graphe de 322 militons de pages. Par la suite, [31] a montré que le nombre d’itérations pour laconvergence est en fait indépendant de la taille du graphe, et que le nombre d’itérationsk afin que l’erreur devienne plus petite qu’un seuil pouvait être estime comme étantk ≥ log((1 − d))/log(d) ≈ log(1/).

Méthodes pour accélérer la convergence

Le calcul d’importance de PAGERANK ( [41]) peut prendre plusieurs jours sur des graphes avec plusieurs milliards de nœuds. Le web change rapidement et pl us de 25% des liens sont changés et 5% de « nouveau contenu » est créé pendant une semaine [56]. Cerésultat signifie que les moteurs de recherche doivent mettre à jour les scores basés sur les liens (comme PAGERANK) très souvent et un score dont l’ancienneté est d’une semaine ne reflète pas très bien l’importance des pages. De plus, plusieurs vecteurs d’importance doivent être calculés dans le cas du calcul des scores PAGERANK personnalisés.
Les méthodes proposées accélèrent le calcul deAGEPRANK soit en considérant l’équation proposée initialement par Google [144], soit en modifiant le graphe du web. Les méthodes d’ex-trapolation [110, 98] s’encadrent dans la première catégorie. En considérant comme vecteur initial d’importance une combinaison linéaire des vecteurs propres de la matrice L, x0 = u1 +2u2 + . . . +mum, le vecteur d’importance calculé à l’itérationk peut être exprimé comme étant : xk = Ak x0 = u1 +2n2u2 + . . . +mnmum où1, . . . ,m sont les valeurs propres de la matrice. [110, 98] présententdifférentes méthodes qui expriment le vecteur d’importance obtenu à une itération du calcul en fonction des vecteurs d’importance obtenus aux itérations précédentes. Les algorithmes d’extrapolation accélèrent le calcul d’importance et calculent une approximation du vecteur principal de la matrice de transition.
Les auteurs de [110] présentent trois méthodes d’extrapolation. Les deux premières repré-sentent l’application de la méthode de Aitken2 [6] utilisée pour l’accélération des séries conver-gentes et de celle de l’accélération epsilon [192] à chaque lément du vecteurx(k−2). A la différence des deux premières méthodes, dans lesquellesx(k−2) est exprimé comme une combinaison linéaire des deux premiers vecteurs propres, dans la troisième méthode d’extrapolation, appelée méthode quadratique, x(k−3) est exprimé commme une combinaison linéaire des trois premiers vecteurs propres. L’accéleration du calcul déduite expérimentallement avec l’extrapolation quadratique est de 59% pour un graphe de 80 million de nœuds. [98] propose une m éthode d’extrapolation qui se base sur le fait que la matrice de transition peut avoir plusieurs valeurs propres de module d, et que ces valeurs propres peuvent être exprimées comme étantdi oùi sont les racines d’un ordre b de 1. Le vecteur d’importance au pas k est exprimé comme une combinaison linéaire des + 1 premier vecteurs propres, correspondant aux + 1 valeurs propres qui peuvent être exprimées de cette manière. Ceci permet d’approximer xk en fonction du vecteur calculé au pask − d. L’accélé-ration du calcul est de 30% sur un graphe de 80 millions de nœud s. Les techniques d’extrapolation sont appliquées de temps en temps pendant le calcul d’importance.
D’autres modèles accélèrent le calcul d’importance en faisant des transformations sur le graphe du web et en utilisant ensuite certaines propriétés du graphe obtenu. [109] observent qu’en permu-tant la matrice de Google en triant lexicographiquement ses URL la structure du graphe du web est sous forme de blocs : la majorité des liens est entre les pages du même domaine et les blocs ont peu de liens vers l’extérieur. Ils calculent un vecteur PAGERANK de l’importance des pages à l’intérieur d’un domaine, sans considérer les liens avec d’autres blocs. Ensuite ils calculent le classement des blocs en construisant le graphe des blocs. Ils pondèrent chaque valeur de PAGE-RANK locale par l’importance du bloc. Ensuite ils appliquent l’algorithme PAGERANK en utilisant comme vecteur initial le résultat précédent. De manière simlaire, [42] partitionne les nœuds du graphe du web en classes équivalentes, chaque classe contenant les pages d’un même domaine. Ils calculent les vecteurs de distribution stationnaires des marches aléatoires sur toutes ces classes. A la différence de la méthode précédente, ces scores ne sont spautilisés comme vecteur initial dans le calcul de PAGERANK, mais ils sont agrégés pour calculer une approximation de AGEPRANK.
Une autre méthode [121] divise le calcul de PAGERANK en deux sous-problèmes :(i) dans un pre-mier temps ils calculent des scores de PAGERANK en combinant toutes les pages terminales dans un seul nœud, et (ii) un deuxième score est calculé en combinant toutes les pages qui ont des liens sortants dans un seul nœud. Le vecteur P AGERANK est obtenu en combinant les deux vecteurs ainsi obtenus. Sur un graphe d’approximativement 400.000 nœuds, le temps de calcul est réduit de 80%.
Dans [108], les auteurs proposent d’accélèrer le calcul en observant que les scores d’importance des pages web ne convergent pas à la même vitesse. Les pages qui convergent moins vite sont celles qui sont les plus importantes. Les auteurs proposent l’algorithme Adaptive PAGERANK dans le-quel le PAGERANK des pages qui ont déjà convergé ne sont pas recalculés pendant les itérations suivantes. Les résultats expérimentaux montrent que la vitesse de convergence est améliorée de 30%.

Stabilité

Dans le contexte dynamique du web, un autre problème concernant le calcul d’importance est sa stabilité. Un algorithme est stable lorsque des petites perturbations de son entrée ne modifient pas beaucoup sa sortie (dans le cas du classement la sortie est constituée de l’ensemble des va-leurs d’importance [124]). Le graphe du web change constamment, car de nouvelles pages et de nouveaux liens sont ajoutés, supprimés ou modifiés. La stabil té du vecteur d’importance reflète la manière dont le vecteur d’importance x est influencé par le changement du coefficient de décrois-sance ou du vecteur de personnalisation, ou par l’ajout ou la suppression de liens dans la matrice de transition. La stabilité est utile surtout dans le contexte du search engine spamming, quand les algorithmes de calcul d’importance ne doivent pas être influencés par les liens utilisés pour pro-mouvoir certains sites. Cette stabilité peut être estimée l’aideà des valeurs propres. Ainsi plus la différence|1| − |2| est grande, plus le résultat est stable aux perturbations [97].

Table des matières

1 Introduction 
1.1 Contexte
1.2 Problématique
1.3 Notre Approche
2 État de l’art 
2.1 Introduction
2.2 PAGERANK
2.2.1 Modèle
2.2.2 Méthode de la puissance
2.2.3 Systèmes linéaires
2.2.4 Algorithmes de classement distribués
2.2.5 Méthodes dérivées de PAGERANK
2.3 Applications du calcul sur les liens
2.3.1 Hypertext Induced Topic Search(HITS)
2.3.2 Recherche par mots-clés dans des bases de données
2.3.3 Classement de données sémantiques
2.3.4 Détection de « spam»
2.3.5 Calcul de réputation
2.3.6 Rafraîchissement et découverte de documents
2.3.7 Identification des pages non-maintenues
2.4 Conclusion
3 Modèle d’importance de services 
3.1 Utilisation de services
3.1.1 Enregistrement de l’utilisation
3.1.2 Graphe d’utilisation de services
3.2 Modèle de contribution
3.2.1 Contribution directe
3.2.2 Contribution indirecte
3.2.3 Contribution totale
3.2.4 Importance de service
3.3 Analyse du calcul d’importance
3.3.1 Système linéaire
3.3.2 Calcul itératif
3.3.3 Vitesse de convergence
3.3.4 Exactitude du calcul
3.4 Calcul d’importance
3.4.1 Calcul centralisé
3.4.2 Principes de la distribution
3.4.3 Calcul distribué synchrone
3.4.4 Calcul distribué asynchrone
3.4.5 Convergence du calcul distribué
3.4.6 Terminaison du calcul distribué
3.5 Conclusion
4 Classement de services basé sur les appels 
4.1 Introduction
4.1.1 Présentation de l’approche
4.1.2 Travaux existants
4.2 Modèle
4.2.1 Contribution statique
4.2.2 Utilisation de service
4.2.3 Utilisation d’appel
4.2.4 Contribution effective et importance
4.3 Évaluation expérimentale
4.3.1 Génération des graphes de services
4.3.2 Résultats expérimentaux
4.4 Application WEBCONTENT
4.4.1 Présentation de WEBCONTENT
4.4.2 Principe du modèle de classement
4.5 Conclusion
5 Stratégies de cache distribué 
5.1 Introduction
5.1.1 Approche et contribution
5.1.2 Travaux existants
5.2 Évaluation de requêtes basée sur le cache
5.2.1 Modèle de cache
5.2.2 Chemins d’évaluation de requête
5.3 Optimisation du coût total des requêtes
5.3.1 Coût d’une requêtes
5.3.2 Influence du cache sur le coût
5.3.3 Politiques de remplacement de cache
5.4 Stratégie de cache locale
5.5 Stratégie de cache globale
5.5.1 Application du modèle générique
5.5.2 Scores d’utilité sur un chemin
5.5.3 Bénéfice global
5.6 Comparaison des deux stratégies
5.7 Implantation
5.8 Évaluation expérimentale
5.8.1 Configuration expérimentale
5.8.2 Expériences
5.9 Conclusion
6 Classement de services basé sur les données 
6.1 Introduction
6.1.1 Présentation de l’approche
6.1.2 Travaux existants
6.2 Documents et services
6.2.1 Modèle de documents
6.2.2 Services et requêtes
6.2.3 Sémantique des requêtes
6.3 Modèle de contribution
6.3.1 Application du modèle générique
6.3.2 Contribution des données
6.3.3 Contribution des sources
6.4 Calcul d’importance
6.4.1 Importance des noeuds
6.4.2 Importance des services
6.5 Contribution indirecte
6.6 Implantation
6.7 Classement de services RSS
6.8 Conclusion
7 Conclusion et perspectives 
Résumé

Télécharger le rapport complet