Le graphe social implicite de Gmail

Introduction

Quand on écrit un email à quelques amis sur gmail, d'autres contacts sont suggérés. Je me suis longtemps demandé comment ça fonctionnait, car je veux quelque chose de similaire sur epinardscaramel, pour les étiquettes à coller aux billets.

Je pensais faire quelque chose comme ça :

//créer des groupes d'étiquettes; leur donner une note.
//augmenter la note chaque fois qu'ils sont utilisés.
//quand l'utilisateur saisi les étiquettes A et B, chercher les groupes contenant A et B
//suggérer les étiquettes, autres que A et B, qui appartienent au groupe de meilleur note.

Mais, en fouillant un peu, on m'a orienté vers research.google.com, où on trouve un article qui décrit exactement comment l'équipe gmail à implémenté cet algorithme : Suggesting Friends Using the Implicit Social Graph (en anglais).

L'algorithme

L'article commence par suggerer d'utiliser un hypergraphe, où chaque "sommet" serait une adresse email. Chaque fois qu'un email, entrant ou sortant, est émis, google crée une "arête" de l'hypergraphe, en gros un groupe d'adresses email. Jusqu'ici tout va bien.

Les choses se compliquent quand on arrive au calcul de la note "IR" de ce groupe :

C'est beau les maths, hein !  Ne partez pas en courant, je vais expliquer, c'est malin comme formule. On remarque tout d'abord qu'on fait la somme de deux formules identiques, à ceci près que l'une concerne les messages entrants I_in, et l'autre, les messages sortants I_out. Ce calcul est :

Cette partie du calcul s'occupe de la date des messages, avec t_now la date d'aujourd'hui et t(i) la date du message. La différence est divisée par λ, une constante qui représente la "demi-vie" de la note. En effet, si le message vient d'être émis, "t_now - t(i)" sera nul, ainsi que 0 divisé par λ, et la note du message sera donc (½) puissance 0, ce qui fait 1.

Une fois que λ secondes se sont écoulées entre l'emission du message et maintenant, "t_now - t(i)" sera alors égal à λ, λ divisé par lui-même fait 1, et ½ puissance 1 fait ½. Quand 2λ secondes se seront écoulées, la note sera alors de (½)², soit ¼. Ainsi, on voit que la note est divisée par deux à chaque fois que la durée λ s'écoule.

La formule calcule ainsi la note de chaque message, et en fait la somme (symbole Σ). Enfin, pour indiquer que les messages émis sont plus importants que les messages reçus, on multiplie la somme des notes des messages émis par ω_out, une seconde constante.

Prendre en compte le temps passé depuis l'émission du mail est très malin; Gmail considère à juste titre qu'un groupe d'amis récent est plus intéressant qu'un groupe plus vieux.

Suggérer des amis

Maintenant qu'on a une note pour chaque groupe d'adresses email, on est capables de suggérer des adresses email qui iraient bien avec celles que l'auteur a déjà saisies.

Pour ce faire, il ne suffit pas de trouver le groupe qui a la meilleure note, et de suggérer tous les membres de ce groupe : Il faut calculer un score pour chaque adresse, en fonction des groupes et de leurs notes.

L'article propose 5 façons différentes de calculer le score de chaque adresse, je vous laisse les découvrir si vous voulez aller plus loin.

Et pour épinards & caramel ?

En ce qui concerne le site, je veux implémenter l'algorithme pour des groupes d'étiquettes : la formule du calcul de IR sera donc plus simple dans mon cas, puisqu'il n'est pas question de mails entrants ou sortants. Mon hypergraphe aura pour sommets chaque étiquette du site, et la note des arrêtes sera calculée en fonction de la date de publication d'un billet.