Aller au contenu

Modélisation des Réseaux (M1, 2018)/Activité F

Une page de Wikiversité, la communauté pédagogique libre.

Pour la dernière activité du cours, on va se calculer une recommandation à partir de nos réseau du week-end créés et harmonisés depuis le début du cours dans les activités A et C.

Après lire les instructions ci-dessous, allez étudier l'activité de référence (Ale Abdo) où ces instructions se trouvent davantage éclaircies.


On va considérer le réseau du week-end comme un réseau non-orienté entre les éléments décrits dans le document, où deux éléments sont connectés s'ils apparaissent dans la même phrase <elem_1> <prop> <elem_2>, peu importe la propriété qui les lie.

Il y a deux types de noeuds dans ce réseau:

  • participants du cours, normalement les sujets des phrases
  • activités du week-end, normalement les objets des phrases

Pour faciliter les opérations suivantes, on représente le réseau comme une liste d'adjacence, c'est-à-dire que, pour chaque noeud, on liste les noeuds auxquels il est connecté.

Note: Il est importante de comprendre, comme vu pour le calcul du PageRank avec les matrices d'adjacence, que le format dans lequel on stocke la donnée peut rendre plus facile ou difficile certaines opérations.

→ Réseau du week-end consolidé, sans propriétés, en format liste d'adjacence

L'algorithme de recommandation qu'on va suivre consiste de, pour un participant p du cours:

  1. pour chacun des autres participants q, calculer la similarité s(p, q):
    • la similarité s(p, q) est le nombre de voisins communs entre p et q - c'est-à-dire, le nombre de voisins de p qui sont aussi voisins de q.
  2. pour chaque activité a, calculer le score r(p, a):
    • pour expédier le travail, on va considérer uniquement les activités liées au participant à plus haute similarité de p, tirant au sort le participant en cas d'égalité.
    • le score r(p, a) est la somme, pour chacun des voisins q de a, de la similarité s(p, q) qu'on vient de calculer.
    • on ne veut pas recommander des activités déjà faites, donc pas besoin de calculer le score pour les activités déjà liées au participant p.
  3. choisir l'activité à recommander:
    1. exclure les activités déjà liées au participant p.
    2. trouver les activités avec le plus haut score r(p, a).
      • si il n'y a qu'une seule activité avec le plus haut score:
        • recommander cette activité.
      • s'il y a plusieurs activités avec le plus haut score:
        • parmi ces activités à plus haut score, trouver celles avec le plus haut nombre de voisins.
          • si il n'y a qu'une seule activité trouvée:
            • recommander cette activité.
          • s'il y a plusieurs activités trouvées:
            • recommander une parmi elles, au hasard.

Grace au format liste d'adjacence, on peut profiter de certains raccourcis pour les calculs:

Pour s(p, q):

  • rechercher le URI du participant p fait parcourir les activités qui l'ont comme voisin; pour chaque activité, on voit directement qui sont les autres participants qui partagent l'activité avec p et il suffit de sommer 1 à chacun.

Pour r(p, a):

  • pour chaque activité, on voit directement qui sont les participants liés et il suffit de sommer ses similarités s(p, q).

Ale Abdo

MathieuLVQ

Pmrslt

Fiona ARENA

Auriane78

T.SerSo

Agathe Ch.

ouadam16

Tom Flamand

idegiorgio

Juliamthrn

Manel411195

Tanguyngo

JulietteBenhadria

Alicecorreia

Florentine Cuenot

Alexandre_Husltin

Alice.gabay

Léna Weiss

Arnaud Ldl

Julie_Roland-Billecart

ThéoRochaix

Chapch14

AmineLahrichi

Leavigouroux

Marguerite Parmentier

Levyemma

Evahatik

A. Isabelle

Edouard_Ferrero

mehdijibril

Marcsamsam