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

Pour la dernière activité du cours, on va calculer une recommandation à partir de notre réseau crée au début du cours et harmonisé à partir d'un format et vocabulaire commun. Le voici consolidé en un seul document :

Réseau harmonisé et consolidé, sans les propriétés, en format d'une double liste d'adjacence

Instructions

Donnée

On va considérer le réseau comme un réseau orienté entre les éléments décrits dans vos activités C, où deux éléments sont connectés s'ils apparaissent dans la même phrase <élément A> <propriété X> <élément B>, peu importe la propriété qui les lie. On constate qu'il y a deux types de nœuds dans ce réseau:

les participants du cours, en tant que sujets des phrases
les éléments de nos récits, en tant qu'objets des phrases

On commence par représenter le réseau sous la forme d'une double liste d'adjacence, c'est-à-dire : dans une première section sortante le document liste pour chaque nœud les nœuds auxquels il se connecte ; dans une deuxième section entrante le document liste pour chaque nœud les nœuds qui se connectent à lui. Comme dans notre réseau tous les liens vont d'une personne à un élément de son récit, la première section aura seulement une liste par personne, et la deuxième section seulement une liste pour chaque élément qui apparaît dans l'un des récits.

Note: Comme on verra, ce format facilitera notre exécution de l'algorithme. On a vu au long du cours que le choix de format peux rendre plus facile ou difficile certaines opérations.

Enrichir la donnée si nécessaire

Avant de commencer le calcul, vous allez regarder si parmi vos objets il y a au moins trois dont vous partagez avec un collègue. Cela se fait facilement avec le document du réseau consolidé : allez dans la liste sortante qui vous correspond, puis pour chaque objet allez regarder s'il y a d'autres personnes dans la liste entrante que lui correspond. Si vous ne comptez pas trois objets partagées avec d'autres :

Trouvez un élément dans la liste entrante qui n'est pas dans votre liste mais correspond à un élément dans votre liste dans un niveau plus élevé d'abstraction - c'est-à-dire, ils appartiennent au même genre de musique, ou au même pays etc. Vous allez alors travailler comme si ces deux éléments étaient le même.
Répétez jusqu'à ce que vous aurez au moins trois objets que vous partagez avec au moins un collègue.

Algorithme

On a vu dans le cours que les algorithmes de recommandation, qu'on appelle aussi du « filtrage collaboratif », partent d'une similarité entre personnes établie par leur rapport aux éléments de récit à recommander, éléments auxquels on appellera « activités ». Cette similarité est en suite utilisé pour construire un score entre la personne et chaque activité possible de recommander. L'algorithme qu'on va suivre ici réduit à l'essentiel cette démarche pour qu'on puisse l'exécuter manuellement.

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é.
- On ne veut pas recommander des activités déjà connues de p, donc pas besoin de calculer le score pour chaque activité a à laquelle le participant p se trouve déjà lié.
- Le score r(p, a), pour recommander au participant p une activité a, est la somme de la similarité s(p, q) pour chacun des voisins entrants q de a.
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 entrants.
      - 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 double liste d'adjacence, on peut profiter de certains raccourcis pour les calculs:

Pour s(p, q):

Sous la liste sortante du participant p on voit les activités auxquelles il est connecté.
- On peut alors chercher la liste entrante pour chacune de ses activités.
  - Dans chacune de ces listes, on voit qui sont les autres participants q qui partagent l'activité avec p, et alors il suffit de sommer 1 à la similarité s(p, q) de chacun de ces participants.

Pour r(p, a):

Dans la liste entrante d'une activité a, on voit qui sont les participants q qui s'y connectent et il suffit de sommer ses similarités s(p, q) pour obtenir le score r(p, a).

.~´