Le graphe dévoile le paradigme sous les liens sponsorisés

Par 26 septembre 2008
Mots-clés : Smart city

Yahoo! Research a mis au point des algorithmes capables de dessiner rapidement les hyperstructures propres à des larges volumes de données. Une avancée applicable aussi bien aux réseaux sociaux qu'à la recherche sponsorisée.

Trouver un schéma d'organisation - ou métadonnées ou paradigme - sous-tendant des ensembles de plusieurs millions de données n'est pas une mince affaire. L'intérêt est pourtant grand : trouver les lignes de cohérence dans des réseaux sociaux, ou dans des comportements d'achat de liens sponsorisés. Et par la suite, suggérer des phrases aux annonceurs qui pourraient être potentiellement plus profitables, réécrire des liens parrainés à la volée, permettre à des économistes et statisticiens de tester des théories économiques, etc. Un groupe de travail de l'unité de R&D de Yahoo! semble avoir trouvé un moyen rapide de traiter le problème en passant non pas à des graphes mais à des grappes de graphes.
Des modèles de dépense
Kezako ? Un graphe est une représentation d'un ensemble d'objets informatiques - les nœuds - et des relations entre ces objets - les liens. Dans un réseau social, les nœuds représentent les membres et les liens la forme de relation ou d'interaction entre eux. Si l'on s'intéresse à la publicité, un graphe peut aussi représenter les modèles de dépense dans le domaine de la recherche sponsorisée. Les nœuds représentent cette fois les phrases et les annonceurs, et le lien va par exemple indiquer que l'annonceur a dépensé de l'argent sur cette phrase. Problème : des graphes comme ceux-là peuvent contenir 100 millions de nœuds. Pas facile de trouver un algorithme performant... Heureusement, les chercheurs ont trouvé leur salut dans les grappes de graphe. Les grappes ou cluster résultent de la partition des noeuds en groupes qui partagent un trait commun.
Le salut dans les grappes
Même avec des graphes étendus, le nombre de ces ensembles logiques ne dépasse pas le million. Et là Yahoo! reprend les deux exemples précédemment cités. Dans un réseau social, le cluster correspondrait à un ensemble de personnes qui interagissent plus entre eux qu'avec le reste de la communauté. Et dans la recherche sponsorisée, chaque grappe serait un sous marché représentant d'un groupe spécifique d'annonceurs qui font en majorité des dépenses sur un groupe de phrases. Bref, Yahoo! Research a basé ses développement sur le traitement des graphes via les clusters, ce qui lui permet d'obtenir un algorithme dont le temps de traitement est proportionnel au nombre de grappes - donc au résultat du traitement - et non pas à la taille du graphe injecté initialement.

Mentions légales © L’Atelier BNP Paribas