Brevet FR2861480A1 — publié le 20050429

La présente invention se rapporte au domaine des télécommunications et en particulier au domaine des moteurs de recherche pour la recherche de pages électroniques. Actuellement, les méthodes de recherche de pages sur un réseau de télécommunication tel le réseau Internet dit Web, peuvent être classées en deux familles. Une première famille qui regroupe les méthodes de recherche par pertinence et une seconde famille qui regroupe les méthodes de classement par rang. La première famille fait l'objet de peu de publication sauf en ce qui concerne les travaux axés sur une recherche d'information par mots clefs. La seconde famille fait l'objet de nombreuses publications. Parmi celles-ci, il est possible de citer les documents suivants, "What can you do with a Web in your pocket ?" Data Engineering Bulletin, 1998 ayant pour auteurs S.Brin, R.Motwani, L.Page et T.Winograd, "Efficient Computation of PageRank", Technical report, Computer Science Department, Stanford University, 1999 ayant pour auteur T.Haveliwala, "Authoritative Sources in Hyperlinked Environment", Proceedings of the 9h Annual ACM-SIAM symposium on Discrete Algorithms, pages 668-677, 1998, "The PageRank Citation Ranking: Bringing Order on the Web", Technical report, Computer Science Departement, Stanford University, 1998 ayant pour auteurs L.Page, S.Brin, R.Motwani et T. Winograd. Bien qu'elles fassent l'objet de peu de publications, les méthodes de recherche de pages exploitant la notion de pertinence pour une requête donnée sont les plus courantes. Les algorithmes correspondant font partie de nombreux moteurs de recherche, certains bien connus sous leur nom commercial tels que "Alta Vista", "Voilà", "Lycos". Ces algorithmes s'appuient sur le fait qu'une page est d'autant plus pertinente pour une requête donnée qu'elle comporte un grand nombre d'occurrences des mots formulant la requête et que ces mots ont dans le texte de la page un enchaînement proche de celui formulé dans la requête. L'inconvénient majeur de ces algorithmes est qu'ils peuvent être détournés par des personnes mal intentionnées qui désirent voir figurer leurs pages en tête du classement. A cette fin, il leur suffit de faire figurer dans leurs pages un très grand nombre de fois les mots pouvant être utilisés dans les requêtes formulées par les internautes et pour lesquelles ces personnes veulent que leurs pages soient sélectionnées. Cette pratique est connue sous le terme anglo-saxon spamming. Un autre moteur de recherche bien connu, dont le nom commercial est "Google" exploite le classement par rang. Le rang d'une page est une fonction numérique du nombre de pages qui pointent sur cette page et du rang de ces pages. Le rang d'une page d'indice p est donné par la formule suivante: p(p)=K a E P(P) +(l a)E(p) ,Er-(p) 8 (P) dans laquelle K est une constante de normalisation qui permet de s'assurer que p(p)est une probabilité. a est un facteur qui permet en fonction de sa valeur de privilégier soit le fait que beaucoup de pages pointent sur la page p, soit de donner une forte importance à la page p elle-même. r- (p) désigne l'ensemble des pages pointant sur p. 8 + (q) est le nombre de page sur lesquelles la page q pointe. E (p) représente la probabilité d'être sur la page p. Cette méthode de classement des pages est connue sous le terme anglo-saxon "PageRank". Un point sensible de cette méthode est la détermination de l'importance qu'il faut donner à la somme des rangs pointant sur la page p dans le calcul du rang de celle-ci, autrement dans le choix de la valeur à donner au paramètre a. Aussi, le problème technique à résoudre par l'objet de la présente invention est de proposer un procédé de classement de pages électroniques accessibles sur un réseau de télécommunication et appartenant à un graphe G,V donné d'ordre n qui soit indépendant de la sémantique, c'est-à-dire qui n'utilise pas la notion de pertinence et qui soit indépendant d'un classement par rang. Une solution au problème technique posé consiste, selon la présente invention, en ce que ledit procédé est tel qu'il comprend les étapes qui consistent: à déterminer une clique K du graphe G,, au moyen d'un processus de calcul de clique de cardinalité maximum, à déterminer un graphe expansif qui comprend la clique précédente et ce, au moyen d'un algorithme qui, dans une boucle et à chaque itération i de la boucle, i étant initialisé à 0, détermine le contenu d'un graphe courant comme étant composé d'un graphe G,=(V;, E;) déterminé à l'itération précédente et des voisins de ce dernier graphe G; (V;, E;) parmi les sommets du graphe Gw, le graphe Go de la première itération étant initialisé au contenu de la clique K et la boucle étant parcourue tant que la distance entre la distribution de probabilité d'une marche aléatoire dans le graphe courant et la distribution uniforme est inférieure à un seuil donné, le graphe expansif étant le graphe obtenu lors de la dernière itération, - à classer les pages électroniques du graphe expansif en positionnant en tête les pages correspondant aux sommets de Vo, suivies des pages correspondant aux sommets de VI et ainsi de suite jusqu'au pages correspondant aux sommets du dernier graphe et, pour un même sommet V;, à classer les pages électroniques à l'aide d'un tirage aléatoire. Le procédé conforme à l'invention résout le problème posé. En effet, le procédé repose uniquement sur les propriétés topologiques d'un graphe: le procédé utilise les propriétés de la distribution stationnaire d'une marche aléatoire, démarrée dans un sous-ensemble de sommets particuliers qui correspond à une clique Go de cardinalité maximum. Le procédé exploite le fait que les membres d'une communauté thématique du Web, ou de tout autre réseau, ont des pages qui pointent essentiellement vers les pages des autres membres de la communauté. L'ensemble de ces pages forme un graphe dont les sommets sont les pages et dont les arêtes sont les liens entre pages, ce graphe se comporte comme un graphe expansif lors d'une marche aléatoire démarrée dans ce graphe. Un procédé selon l'invention permet avantageusement de s'affranchir des problèmes liés au "spamming". Selon un mode particulier de mise en oeuvre d'un procédé selon l'invention, le graphe G,U est composé des pages électroniques du réseau Internet ou Web. Selon un mode particulier de mise en oeuvre d'un procédé selon l'invention, le graphe Gw est un graphe obtenu à l'issue d'une recherche de composantes connexes dans un sous-graphe du réseau Internet. Selon un mode particulier de mise en oeuvre, le procédé est associé à un moteur de recherche ce qui permet de présenter à un utilisateur les pages les plus intéressantes en réponse à une requête préalablement formulée. Selon ce mode, le graphe Gw est composé des pages électroniques sélectionnées à l'issue d'une recherche thématique effectuée à l'aide du moteur de recherche. D'autres caractéristiques et avantages de l'invention apparaîtront lors de la description qui suit faite en regard de figures annexées données à titre d'exemples non limitatifs. La figure 1 est un organigramme d'un procédé selon l'invention. La figure 2 est un schéma d'un algorithme mis en oeuvre par un procédé selon l'invention. Un procédé selon l'invention dont un organigramme est donné par la figure 1 détermine les pages centrales d'un graphe G,, composé de pages électroniques. Les pages sont centrales du point de vue d'une communauté thématique. A cette fin, un procédé 1 selon l'invention effectue un classement de pages électroniques accessibles sur un réseau de télécommunication et qui appartiennent au graphe G,y, d'ordre n. Par exemple, le graphe G,, comprend toutes les pages du Web. Pour effectuer ce classement le procédé comprend les étapes décrites ci-après. Dans une première étape 2, le procédé détermine une clique K du graphe G , au moyen d'un processus de calcul de clique de cardinalité maximum. Une clique ou graphe complet est un graphe Go = (Vo, Eo) dont tout sommet i Vo est relié par au moins une arête à tout sommet j e Vo {i{ . Il existe différents processus connus de tel calcul. Citons par exemple, les heuristiques rapides et performantes telles que décrites dans les articles "A fast and simple randomized parallel algorithm for the maximal independent set problem", Journal of Algorithms, 7, 1986 des auteurs N. Alon, L.Babai et A.Itai, "Finding a maximum clique in an arbitrary graph", SIAM Journal on Computing, 14:1054-1068, 1986, des auteurs E.Balas et C. S. Yu, "A greedy heuristic for the ser-covering problem", Mathematics of Operations Research, 4:233-235, 1979 de l'auteur V.Chvâtal. Cette clique K correspond à un noyau composé des pages centrales d'une communauté thématique. En effet les membres d'une communauté thématique du Web ont des pages qui pointent essentiellement vers les pages des autres membres de la communauté. Le nombre de ces pages dites centrales et qui sont très fortement reliées entre elles, est assez petit par rapport au nombre total de pages de la communauté. Le graphe constitué des pages, pour ce qui est des sommets, et des liens pour ce qui est des arêtes, induit par cette clique K, peut être assimilé à un graphe régulier et expansif. Un graphe est dit régulier si tous ses sommets ont le même degré, c'est-à-dire le même nombre d'arêtes incidentes. Un graphe G = (V, E) régulier est dit expansif si pour tout sous-ensemble de sommets S c V tel que ISI Le nombre de sommets du graphe qu'il est possible d'atteindre en k étapes en partant d'un sommet quelconque du graphe croît très rapidement avec k, cette expansion justifie l'appellation graphe expansif. Cet accroissement du nombre de sommets accessibles depuis un sommet de départ se mesure par une quantité h (G) = Min r S) ,S c V appelée facteur d'expansion du graphe. La détermination d'un minorant et d'un majorant de h(G) est effectuée au moyen du calcul des valeurs propres de la matrice A d'adjacence du graphe G = (V, E) . A un graphe G = (V, E) est associé une matrice A dite d'adjacence. Elle est définie de la manière suivante. Les lignes et les colonnes de la matrice A sont indexés par les sommets du graphe, l'élément a vaut 1 si le sommet i est relié au sommet j par une arête (i est voisin de j) et 0 sinon. La matrice A est symétrique. Par suite, elle possède n = IVI valeurs propres réelles 15: ,uo,u1... . En outre, la somme des coefficients de chaque ligne et de chaque colonne vaut d, d étant le degré de chaque sommet car le graphe G est supposé régulier. Ceci permet d'écrire duo = d. Soit, = Max l, alors le théorème suivant donne un encadrement du facteur d'expansion: d 2 L'établissement des théorèmes précédents est présenté dans le document "Expander graphs and their applications, Lecture 3: Random Walks on Expander Graphs", Notes prises par Boaz Barak et Udi Wieder, March 2002, suite à un cours donné par Nati Linial and Avi Wigderson à l'Université hébraïque, Israel. La périphérie de la clique K comprend des sommets qui, de même que les sommets de K, pointent sur un nombre sensiblement équivalent de pages de la communauté. Les sommets associés à ces pages et ceux de la clique K ont donc des degrés égaux. Ceci permet de considérer que le graphe induit par l'ensemble constitué de la clique K et de 2861480 7 ce nouvel ensemble de sommets, L, est un graphe régulier expansif. Les pages de l'ensemble L ne pointent pas uniquement sur des pages appartenant à la clique K. Elles peuvent pointer sur des pages plus excentrées et former des cliques dans certains sous-ensembles de L. A la périphérie de la communauté, il y a des pages qui ont beaucoup moins de liens avec les pages des niveaux antérieurs. L'ensemble de ces pages est noté E et le graphe induit par K u L u E n'est pas un graphe expansif: les pages qui ne sont pas centrales pour la communauté ne font pas partie du graphe expansif K u L car elles ne pointent pas sur un nombre sensiblement équivalent de pages de la communauté. Dans une deuxième étape 3, le procédé détermine le graphe expansif K u L qui comprend la clique K précédente, c'est-à-dire déterminée lors de la première étape. La détermination de K u L s'effectue au moyen d'un algorithme illustré par la figure 2 qui, dans une boucle et à chaque itération i de la boucle, i étant initialisé à 0, détermine le contenu d'un graphe courant. Ce graphe courant est composé d'un graphe G,=(V;, E;) déterminé à l'itération précédente et des voisins de ce dernier graphe G; =(V;, E;) parmi les sommets du graphe G,, . L'algorithme peut s'écrire de manière algorithmique sous la forme suivante: étape 3.1: Go = K, no = KI étape 3.2: vo = n (1,...1) étape 3.3: initialiser ko. étape3.4: i=0 étape 3.5: Tant que Âkv, ui (a) V+, = V U [USEv.r; (s)] (b) nt+1 = V+1 (c) Gr+, =G[V+,] (d) calculer Â;+1 (e) / 3 i + 1 = M a x {1/4+1 1, (f) ki+1 =f (kk) Le graphe expansif K u L est le graphe obtenu lors de la dernière itération. Dans une troisième étape 4, le procédé classe les pages électroniques en positionnant en tête les pages correspondant aux sommets de Vo. A la suite, le procédé classe les pages correspondant aux sommets de VI et ainsi de suite jusqu'aux pages correspondant aux sommets du dernier graphe. Pour un même sommet V;, le procédé classe les pages électroniques à l'aide d'un tirage aléatoire. REVENDICATIONS 1. Procédé (1) de classement de pages électroniques accessibles sur un réseau de télécommunication et appartenant à un graphe Gw donné, qui comprend les étapes qui consistent: - à déterminer (2) une clique K du graphe Gw au moyen d'un processus de calcul de clique de cardinalité maximum, à déterminer (3) un graphe expansif qui comprend la clique K précédente et ce, au moyen d'un algorithme qui, dans une boucle (3.5) et à chaque itération i de la boucle, i étant initialisé à 0, détermine le contenu d'un graphe courant comme étant composé d'un graphe G; (V;, E;) déterminé à l'itération précédente et des voisins de ce dernier graphe G; (V;, E;) parmi les sommets du graphe G,v, le graphe Go de la première itération étant initialisé au contenu de la clique K et la boucle étant parcourue tant que la distance entre la distribution de probabilité d'une marche aléatoire dans le graphe courant et la distribution uniforme est inférieure à un seuil donné, le graphe expansif étant le graphe obtenu lors de la dernière itération et à classer (4) les pages électroniques du graphe expansif en positionnant en tête les pages correspondant aux sommets de Vo, suivies des pages correspondant aux sommets de V1 et ainsi de suite jusqu'au pages correspondant aux sommets du dernier graphe et, pour un même sommet V;, à classer les pages électroniques à l'aide d'un tirage aléatoire. 2. Procédé (1) de classement de pages électroniques selon la revendication 1 dans lequel le graphe G,v est composé des pages électroniques du réseau Internet. 3. Procédé (1) de classement de pages électroniques selon la revendication 1 dans lequel le graphe G% est un graphe obtenu à l'issue d'une recherche thématique à l'aide d'un moteur de recherche dans un graphe du réseau Internet. 4. Procédé (1) de classement de pages électroniques selon la revendication 1 dans lequel le graphe G,v est un graphe obtenu à l'issue d'une recherche de composantes connexes dans un graphe du réseau Internet.