Distributed Social Graph Embedding - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2010

Distributed Social Graph Embedding

Résumé

Content recommendation is becoming central in the Web 2.0 to leverage the growing information on users available today. In this paper we propose a decentralized gossip-based algorithm called SoCS (Social Coordinate Systems) that achieves efficient distributed social graph embedding for content recommendation purposes. Social graph embedding embeds a graph into a d-dimensional Euclidean coordinate space. SoCS relies on a force-based graph embedding technique to extract communities from a graph. We explore here a distributed algorithm for it (i) scales to large dynamic graph, aggregating the computing power of individual nodes and, (ii) avoids a central entity controlling users sensitive data such as relations and preferences. We evaluate SoCS using two different force-based models and compare them in the context of a generated Kleinberg small-world topology. More specifically, we show that the SoCS graph embedding enables to clearly distinguish between short and long-range links. We also evaluate SoCS against a real DBLP data set, showing that removed links are correctly predicted. Finally, we show that our gossip-based algorithm is extremely resilient to dynamics.
La recommandation de contenu est devenue un élément central de l'Internet moderne pour permettre aux utilisateurs de naviguer parmi la masse d'information à leur disposition. Dans ce papier, nous proposons un algorithme décentralisé appelé \textsc{SoCS (Social Coordinate Systems}) qui permet de plonger un graphe social dans un espace Euclidien afind'effectuer des recommandations. Nous utilisons un algorithme de dessin de graphe basé sur un modèle de forces afin de mettre en évidence les communautés présentes dans un graphe. Nous présentons ici une solution décentralisée car cela \textit{(i)} passe à l'échelle dans des systèmes dynamiques rassemblant plusieurs milliers d'utilisateurs, et \textit{(ii)} permet d'éviter qu'une entité centrale ait accès à toutes les données privées des utilisateurs. Nous évaluons \textsc{SoCS} à travers deux modèles de force différents et les comparons dans le contexte d'une topologie petit-monde issue du modèle de Kleinberg. En particulier, nous montrons que \textsc{SoCS} permet de clairement différencier les liens courts des liens longs. Nous évaluons également \textsc{SoCS} sur des données réelles issues de DBLP, et montrons que des liens retirés peuvent être prédits grâce à notre algorithme. Enfin, nous montrons que notre algorithme est extrêmement résistant aux perturbations.
Fichier principal
Vignette du fichier
RR-7327.pdf (307.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00495250 , version 1 (25-06-2010)

Identifiants

  • HAL Id : inria-00495250 , version 1

Citer

Anne-Marie Kermarrec, Vincent Leroy, Gilles Tredan. Distributed Social Graph Embedding. [Research Report] RR-7327, INRIA. 2010. ⟨inria-00495250⟩
173 Consultations
648 Téléchargements

Partager

Gmail Facebook X LinkedIn More