inria-00495250, version 1

Distributed Social Graph Embedding

Anne-Marie Kermarrec () ^a, 1, Vincent Leroy () ^b, 1, Gilles Tredan () ^c, 2

N° RR-7327 (2010)

• a –  INRIA
• b –  Institut National des Sciences Appliquées de Rennes
• c –  Deutsche Telekom
• 1:  ASAP (INRIA - IRISA)
• http://www.inria.fr/equipes/asap
  CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1 Campus de Beaulieu 35042 Rennes cedex France
• 2:  Deutsche Telekom Laboratories (DT Lab)
• http://www.laboratories.telekom.com/ipws/English/Pages/Willkommen.aspx
  Deutsche Telekom Laboratories Quality & Usability Lab, TU Berlin, Ernst-Reuter-Platz 7, 10587 Berlin, Germany Germany

Bibliographic reference

• Type of document: Research reports
• Domain:

  Computer Science/Distributed, Parallel, and Cluster Computing

  Computer Science/Information Retrieval

• Title: Distributed Social Graph Embedding
• Abstract: 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.
• Abstract in french: 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.
• ACM Classification: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.4: Distributed Systems
• Full text language: English
• Report type: Research Report
• Publication date: 2010-06
• Keywords: peer-to-peer – gossip – social networks – embedding
• Writing date: 2010-06
• Internal note: RR-7327

Attached file list to this document: 

• inria-00495250, version 1
• http://hal.inria.fr/inria-00495250
• oai:hal.inria.fr:inria-00495250
• From: Vincent Leroy <>
• Submitted on: Friday, 25 June 2010 13:03:58
• Updated on: Tuesday, 29 June 2010 09:08:57