Travail noté sur les algorithmes topologiques |
 |
Consignes du travail noté 5
Vous devez rédiger un court rapport (en format « pdf », « Word 97/2000/XP », « RTF », « OpenDocument » ou « texte ») que vous transmettrez, par courriel, à votre personne tutrice. L’objet de votre courriel doit commencer par « [INF6460][TRAVAIL5] », afin de permettre à la personne tutrice de classer rapidement ses messages. Dans le corps de votre message ainsi que dans votre rapport, vous devez bien indiquer votre nom, votre numéro d’étudiant ainsi que le numéro du travail.
Le travail est noté sur 10 points.
Question 1 (5 points)
Considérons un « web » avec 5 pages qui contiennent respectivement un lien vers chaque autre page [1]. Supposons, de plus, que l’une des pages contient un lien vers une autre page qui, elle-même, ne contient aucun lien. Le « web » contient donc un total de 6 pages. En utilisant la version simplifiée de PageRank, calculez le PageRank de chaque page avec la convention que la somme des PageRank doit être 1. Justifiez votre réponse en fournissant les matrices et vecteurs utilisés dans votre calcul. Vous n’avez cependant pas à faire le calcul à la main : il vous est permis d’utiliser un programme pour les calculs.
Que pouvez-vous dire du cas où il y aurait non pas 5 pages, mais 50 pages dans la clique ?
Indice. La page X a des liens vers toutes les autres pages, sauf elle-même. La page Y n’a aucun lien. Toutes les autres pages comptent 4 liens.
Question 2 (5 points)
Utilisez la même configuration qu’à la question 1. Nous avons 5 pages qui contiennent respectivement un lien vers chaque autre page et où une page X contient un lien vers une page Y qui ne contient aucun lien.
Supposez qu’un utilisateur fait une recherche pour un certain mot-clé qui ne se trouve que dans la page X. Calculez les coefficients « authority » et « hub » pour chaque page. Justifiez votre réponse en fournissant la matrice et les vecteurs utilisés pour vos calculs. Encore une fois, vous n’avez pas à faire les calculs à la main. Que « recommande » l’algorithme HITS à l’utilisateur ?
Indice. Vérifiez bien que votre matrice A est correcte : $A_{i,j}$ a la valeur 1 si et seulement si la page $j$ a un lien vers la page $i$. Ainsi, la somme des composantes d’une colonne donne le nombre de liens présent sur la page correspondante. Si une page n’a aucun lien, alors la colonne correspondante ne devrait contenir que des zéros.
Les travaux du cours INF 6460 ne sont pas sous une licence Creative Commons.
[1] En théorie des graphes, on appelle une telle configuration, une clique.
