Discussion:Modélisation des Réseaux (M1, 2018)

Bienvenue à l'espace de discussion de notre cours. Ici vous pouvez poser des questions et suggérer des thématiques et lectures pour les rencontres. (N'oubliez pas de signer vos contributions !)

Questions

9/12/2018

points et traits

Je ne comprends aucun graphique des slides : pourquoi ce sont des points avec des traits ?

Les lignes sont l'écart type sur l'ordonnée au tour d'une valeur moyenne. Elles s'affichent quand il y a plusieurs points avec la même valeur sur l'abscisse. Afficher l'écart type ne sera pas demandé dans l'examen. --Solstag (discussion) 9 décembre 2018 à 23:29 (UTC)

corrélation combinée

Quand on calcule une corrélation combinée, j’ai compris qu’on va mettre la première mesure/propriété dans la première colonne, et si plusieurs nœuds ont la même valeur pour cette mesure/propriété, on peut réunir cette valeur dans une même ligne. Et dans la deuxième colonne on met la deuxième mesure/propriété, et pour chaque ligne réunissant plusieurs nœuds ayant une même valeur, on devra calculer la moyenne de leurs valeurs respectives de la deuxième mesure/propriété.

Donc je me pose la question suivante : dans les graphiques, la propriété dont on calcule les moyennes (donc la deuxième) doit-elle forcément être mise en ordonnée et non pas en abscisse?

Oui, normalement on met sur l'abscisse la moyenne de valeurs correspondants à une même valeur sur l'ordonnée. C'est une convention. Rien n'empêche de faire l'envers, mais c'est rare. Si on affiche aussi l'écart type, à l'envers ça ferait des traits à l'horizontal.

On peut aussi choisir de ne pas faire une moyenne, et de mettre dans le graphique tous les points avec une même valeur pour l'ordonnée, avec leurs différentes valeurs pour l'abscisse. Ça s'appelle un graphique nuage de points. Les deux formes sont valables et chacune à ses points forts et faibles pour visualiser la donnée.

--Solstag (discussion) 9 décembre 2018 à 23:29 (UTC)

astuce pour l'intermédiarité

Je ne comprends pas la fin de votre astuce pour l’intermédiarité. J’ai compris qu’il faut faire la liste de tous les chemins les plus courts entre chaque paire du graphe, puis regarder par quel nœud intermédiaire passe chaque chemin.

Mais ensuite je ne comprends pas comment vous comptabilisez pour obtenir l’intermédiarité (ce que vous appelez « ajouter la fraction correspondante aux nœuds qui les composent »).

Prenons par exemple deux noeuds, A et B. Il peut avoir plus d'un chemin plus court entre ces noeuds. Par exemple, si le chemin plus court a une longueur 3, il peut exister un chemin ACDB et un autre ACEB. Dans ce cas, pour la contribution du pair (A, B) à l'intermédiarité des autres noeuds: on ajoutera à l'intermédiarité de C la valeur 1, car il est dans tous les deux chemins (fraction 2/2), mais on ajoutera à l'intermédiarité de D et E la valeur 0,5, car chacun n'est présent que dans un des deux chemins (fraction 1/2).--Solstag (discussion) 9 décembre 2018 à 23:29 (UTC)

vecteur propre: initialisation

P.19 de l’ensemble 3 des slides, je n’ai pas compris à quoi cela correspond. Visiblement il s’agit d’un calcul des densités pi qui se fait grâce à la division du degré de pi par D la somme des degrés de tous les pi. Mais je ne comprends pas ce que ça représente ni comment l’utiliser  vu que ça ne donne pas les mêmes valeurs qu’à la p.18.

La page 19 c'est le cas non-orienté. Dans le cas orienté, page 18, la proposition est d'initialiser le vecteur p_i en distribuant également la matière, donc 1/4. On est libre de choisir comme on initialise de vecteur p_i, donc dans le cas non-orienté la proposition est différente. On propose d'initialiser chaque noeud avec son degré, normalisé par la somme de tous les degrés pour respecter la contrainte que la matière totale soit égale à 1. Le but c'était de montrer que, pour le cas non-orienté, ça nous donne déjà l'état d'équilibre. Ça veut dire que pour le cas non-orienté la centralité de vecteur propre e le degré sont équivalents. Ce qui n'est pas du tout le cas pour les graphes orientés. --Solstag (discussion) 9 décembre 2018 à 23:29 (UTC)

vecteur propre: équilibre

Au sujet des vecteurs propres, qu’appelle-t-on « l’état d’équilibre » ? Est-ce que ce sont les densités pi après une infinité d’itérations ?

Par définition, un état d'équilibre est un vecteur de densités p_i qui ne change pas quand on applique une itération. Il est en équilibre avec la dynamique, car il reste inchangé par son action. Par conséquence, une fois qu'on atteint ce vecteur, on n'a plus besoin d'itérer car on va jamais "sortir" de lui.

Comme nos matrices représentent une diffusion linéaire dans un graphe fortement connexe, il y a un seul état d'équilibre et le système a tendance à l'approcher. Ça implique qu'une infinité d'itérations nous amène à cet état d'équilibre, mais c'est un cas particulier, ce n'est pas la définition.

calculer pagerank ?

Au sujet de PageRank, doit-on savoir réaliser les étapes, c’est-à-dire  « réduire les densités multipliant par fraction (s < 1) et distribuer l’excédent 1-s également entre les nœuds »), ou simplement être capable de réexpliquer le concept tel que vous l’avez déjà expliqué dans les questions précédentes sur la page de discussion ?

On a travaillé le calcul de la centralité de vecteur propre dans nos activités et en classe, et on a vu le PageRank conceptuellement comme une adaptation de celle-là. Vous n'avez pas besoin de s'entraîner à réaliser les étapes particulières au PageRank. --Solstag (discussion) 9 décembre 2018 à 23:29 (UTC)

ensemble 4

Concrètement que doit-on retenir des slides de l’ensemble 4 ? En particulier pour la partie système de recommandation ? et la partie web/données/interfaces ?

Il y a deux nouveau sujets introduits: le fonctionnement des moteurs de recherche et des systèmes de recommandation. Le premier est décrit dans les diapos, le deuxième on a illustré avec l'activité F.

Les autres diapos de l'ensemble rappellent des idées qu'on a travaillé au long du cours: le rôle de formats et vocabulaires pour les données.

De plus, ça vous aidera de revoir les réponses que j'ai déjà donné ici à propos de ces sujets.

Donc, concrètement, tout, dans la limite de ce que j'ai déjà exclu: les concepts de "open/linked" ne sont pas dans le sujet, et il est inutile de mémoriser l'algorithme de l'Activité F.

--Solstag (discussion) 9 décembre 2018 à 23:29 (UTC)

turtle

Avons-nous quelque chose à apprendre au sujet du format RDF Turtle/l’activité C ? Car nous n’avons pas de cours là-dessus, si ce n’est l’activité C.

Avoir compris le format et comment structurer des données dans ce format, ce qu'on a fait dans l'Activité C. --Solstag (discussion) 9 décembre 2018 à 23:29 (UTC)

7/12/2018

Concernant PageRank, je n'ai toujours pas compris : est-ce qu'avant, le graphe du web n'était pas connexe donc pagerank a fait en sorte que le graphe soit connexe en créant des nouveaux liens avec des % de diffusion correspond à 1-S OU est-ce que pagerank a gardé le graphe du web tel quel mais a juste modifié les coefficients de diffusion ?

Le graphe du web n'est pas fortement connexe. Donc il faut garantir que la matière ne se concentrera pas dans une seule composante. Pour ça, PageRank, à chaque itération, prélève une fraction de la matière de chaque noeud, et la partage également entre tous les noeuds. Ça est équivalent à connecter toutes les noeuds du réseau entre eux, par des liens faibles qui ne permettent passer que une fraction de la matière. --Solstag (discussion) 7 décembre 2018 à 10:49 (UTC)

Si j'ai bien compris le succès de Google repose sur Page Rank et l'efficacité de PageRank réside en ce que l'algorithme classe les pages selon le nombre de fois que la page en question est référencée par d'autres sites web ? (cf. la phase d'analyse des crawleurs avant la requête qui sont ensuite indexé)

Non, PageRank classe les pages selon la centralité de vecteur propre corrigé par un facteur de redistribution. Le "nombre de fois que la page en question est référencée par d'autres sites web" correspondrait au degré entrant de la page, et pas au PageRank. La centralité de vecteur propre prend en compte plus que le degré du noeud. Par exemple, il ne suffit pas d'avoir un haut degré entrant si tes voisins sortants sont très faibles, car ils n'auront pas beaucoup de matière à te donner. Le PageRank est une mesure dynamique qui ne peut pas être réduite à une mesure structurale comme le degré. --Solstag (discussion) 7 décembre 2018 à 10:49 (UTC)

Concernant le "après", est-ce qu'il s'agit d'une phase de machine learning où le moteur étudie le comportement de la personne qui a fait la requête selon les retours (clics, si la personne refait une recherche après etc.) ?

L'après correspond à la troisième colonne du diapositif 6 de l'ensemble 4. Parmi les points dans cette colonne il y a en effet l'étude du comportement de l'utilisateur. Pourtant la façon dont ça ser apris en compte, si par apprentissage automatique, par analyse statistique, par évaluation qualitative, peut varier selon le cas. L'objectif reste quand-même de savoir, à partir de ses comportements, si l'utilisateur a trouvé les résultats utiles, et comment pourrait-on les améliorer. Par exemple si 90% des utilisateurs qui font une même requête finissent pour cliquer le 8ème résultat, ça peut suggérer fortement qu'il faut régler les moteur de recherche pour qu'il lui donne plus d'importance. --Solstag (discussion) 7 décembre 2018 à 10:49 (UTC)

Quel rapport entre activité F et PageRank ?

Dans l'Activité F on a trouvé des recommandations à partir de deux mesures: la similarité entre l'utilisateur cible et les autres utilisateurs et, en suite, le score de chaque activité, score qui correspond informellement à une "popularité pondéré par la similarité". Ce score ne s'agissait pas juste du nombre de voisins d'une activité (i.e. de combien de personnes l'on faite, autrement dit le degré du noeud), mais de la somme de la similarité de ses voisins, similarité qui dépend de qui est l'utilisateur cible. Il s'agit alors d'une mesure très ciblé à l'utilisateur à qui on recommande.

Le PageRank, à sa fois, est une mesure qui prend en compte tous les liens du réseau, normalement des liens entre pages du Web, et traite chaque lien de façon équivalente. La valeur du PageRank, c'est-à-dire la distribution de matière à l'équilibre, est calculé en fonction uniquement de ces liens. Donc il s'agit d'une mesure générique et pas du tout ciblé à l'utilisateur qui fait la requête. Au même temps, il faut se rappeler que, dans un moteur de recherche, le PageRank n'est pas le seul signal employé pour classer les pages en réponse à une requête. Autres mesures, y compris mesures ciblés à l'utilisateur ou à la requête, peuvent être combinés avec le PageRank pour arriver aux résultats.

Du coup, Activité F: ciblé à l'utilisateur; PageRank: générique.

Une autre dimension plus subtile dans laquelle l'activité F diffère du PageRank c'est que les mesures de l'Activité F sont structurales (i.e. on compte des éléments du réseau, dans ce cas des voisins et des voisins en commun, mais ça pourrait être des chemins, distances etc), tandis que le PageRank est une mesure dynamique (i.e. on observe le résultat d'une transformation, dans ce cas la diffusion de matière dans le réseau).

--Solstag (discussion) 7 décembre 2018 à 11:24 (UTC)

Pourriez-vous clarifier les notions de "Open" "Linked" et "OpenLinked" dans le diapo 4 ?

On a vu ça très rapidement dans les dernières minutes de la dernière séance de contenu du cours, donc je vous avance que ça ne sera pas dans le sujet de l'examen.

Pourtant, je le vous explique un peu mieux, avec des liens pour les concepts sur Wikipédia si ça vous intéresse :

Open data : quand on publie la donnée avec une licence qui permet son utilisation par le public, et dans un format ouvert, c'est-à-dire un format publiquement documenté et licencié au public.

Linked data : quand le contenu de la donnée s'exprime à travers un vocabulaire contrôlé, ce vocabulaire étant explicitement défini par une ontologie partagé; ce qui permet à un autre jeux de donné de remployer ce même vocabulaire, rendant les deux jeux de donnée interopérables.

Linked Open data : les deux conditions précédentes, plus le fait que l'ontologie, et donc le vocabulaire, soit aussi disponible publiquement sous un format et licence ouverts.

Chacune de nos Activités C est un exemple de Linked Open data, car elles sont:

• rendues en format RDF-Turtle, qui est un format ouvert
• utilisent le vocabulaire Wikidata plus un vocabulaire publié sur la page de l'Activité C
• les données comme le vocabulaire ont été publiés sous la licence de contenu de Wikiversity, qui est permissive

Bon, strictement on devrait parler de presque-exemple, parce que on n'a pas été stricts avec toutes les formalités, mais l'essence est là.

--Solstag (discussion) 7 décembre 2018 à 12:47 (UTC)

4/12/2018

Je n'ai pas très bien saisi la différence entre un graphe connexe et un graphe fortement connexe. Je pensais qu'il s'agissait d'une distinction qui faisait sens pour les graphes non-orientés/orientés, néanmoins dans l'activité B, la dernière question, on parle de graphe non-orienté qui peut être fortement connexe...

Le graphe de l'activité B est orienté. La dernière question parle de "ignorer l'orientation des liens" et en suite de "composantes connexes", donc oui ça fait sens. --Solstag (discussion) 4 décembre 2018 à 19:59 (UTC)

La distinction, encore, c'est que quand on parle de composantes connexes on ne prend pas en compte l'orientation des liens, c'est-à-dire on considère le graphe comme non-orienté. Et quand on parle de composantes fortement connexes on prend en compte l'orientation des liens, et par conséquence la direction des chemins: il faut avoir des chemins de A à B et aussi de B à A, entre tous les noeuds d'un groupe, pour que ce groupe soit considéré une composante fortement connexe. --Solstag (discussion) 4 décembre 2018 à 19:59 (UTC)

À propos de l'activité B

Il peut nous avoir arrivé une confusion car, en classe au début du cours, j'avais corrigé une version simplifié de l'activité B, où au lieu de considérer le réseau avec les éléments et propriétés de l'activité A comme noeuds, j'avais considéré un réseau plus simple, avec uniquement les éléments comme noeuds, liés entre eux. J'avais omis les propriétés ou les gardé comme qualités des liens (je m'en souviens plus que ça). En tout cas, peu importe comme vous l'avez fait, l'important c'est de comprendre les concepts de l'ensemble 1 de diapos. Et pour info l'activité de référence répond bien aux questions comme elles sont posés, sans simplification. --Solstag (discussion) 4 décembre 2018 à 19:59 (UTC)

L'intermediarité est-elle indifférente de l'orientation/non-orientation d'un graphe ? Dans le sens où dans un graphe orienté, il n'est pas nécessaire de calculer l'intermediarité entrante/sortante comme vous l'avez fait dans l'activité E.

L'intermédiarité mesure le besoin de passer par un noeud pour prendre le chemin le plus court entre les autres noeuds. Donc le noeud en question n'est pas le départ ni l'arrivé de ces chemins, qui vont rentrer et sortir de lui. Donc il n'a pas de sense "sortante/entrante" pour l'intermédiarité, il y a juste l'intermédiarité. Il faut comprendre quand-même que l'intermédiarité est sensible à l'orientation des liens, déjà car dans un graphe orienté il faut considérer les deux directions entre chaque pair de noeuds, voire (a...b) et (b...a). --Solstag (discussion) 4 décembre 2018 à 19:59 (UTC)

L'examen portera-t-il sur l'activité F (i.e créer un algorithme d'harmonisation) ?

L'algorithme de l'activité F est spécifique à cette activité. Vous n'avez pas besoin de le mémoriser pour l'examen. Son but était de vous illustrer en pratique une façon de mettre en ouvre un système de recommandation représentatif qui on pouvait faire tourner manuellement. --Solstag (discussion) 4 décembre 2018 à 19:59 (UTC)

Que sous-entendez vous par ontologie ?

Une ontologie est un vocabulaire de concepts, qui peuvent être des éléments ou des propriétés. Les propriétés expriment relations entre concepts ( <poire> <mangé par> <ver> . ), qui peuvent être des relations hiérarchiques ( <poire> <sous-classe de> <fruit> . ) et même des relations entre ou avec des propriétés ( <mangé par> <est un cas de> <propriété biologique> . ). --Solstag (discussion) 4 décembre 2018 à 19:59 (UTC)

Je n'ai pas compris ce que vous attendez (et entendez) par "dans les moteurs de recherche et systèmes de recommandation". Ni le fonctionnement de pagerank

Pour les moteurs de recherche: dans l'ensemble 4 de diapos, les colonnes du diapo 6 montrant chacune des trois étapes d'un moteur de recherche: avant, en réponse, après. --Solstag (discussion) 4 décembre 2018 à 19:59 (UTC)

Pour les systèmes de recommandation: dans l'ensemble 4 de diapos, le diapo 7, et comprendre l'idée générale de l'activité F. --Solstag (discussion) 4 décembre 2018 à 19:59 (UTC)

Le PageRank est expliqué à la fin de l'ensemble 3 de diapos. C'est la centralité de vecteur propre avec un facteur de redistribution pour éviter le problème de manque de connexité forte qu'on a pu constater dans l'activité E. Le PageRank est calculé sur le réseau de liens entre pages web, collectés par le crawleur du moteur de recherche. Il fournit une signal de l'importance d'une page par rapport à la tendance de chaque page à accumuler une matière qui circule entre les pages par leurs liens. C'est le signal qui a fait de Google un moteur de recherche supérieur à la concurrence de l'époque, mais qui aujourd'hui se trouve dans la plupart des moteurs de recherche. --Solstag (discussion) 4 décembre 2018 à 19:59 (UTC)