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

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.

Instructions

Données

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

Algorithme

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

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.
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.
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.

Astuces

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):