User Tools

Site Tools


delesse_valette:alexandre_delesse_joris_valette

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Alexandre Delesse & Joris Valette's corner

Project Simmelian backbone of a network

Lien vers article : http://www.inf.uni-konstanz.de/algo/publications/nlcb-sb-13.pdf

Auteurs de l'article : Bobo Nick, Conrad Lee, Padraig Cunningham et Ulrik Brandes

Lien vers l'archive de notre code

Si besoin, lien vers le jeu de données complet, Facebook100 :

https://archive.org/details/oxford-2005-facebook-matrix

Introduction

L’usage de plus en plus important des réseaux sociaux permet de récolter un grand nombre de données : les informations personnelles des utilisateurs, leurs relations amicales ou professionnelles, leurs centres d'intérêt. Il est donc devenu nécessaire de pouvoir modéliser les réseaux et leurs interactions. Les auteurs de notre article ont basé leurs recherches sur les relations triangulaires, en se basant sur les travaux du sociologue allemand Georg Simmel sur l’appartenance des individus à un groupe, et le rôle crucial de ces relations triangulaires dans la définition des communautés. Les “Simmelian backbones” sont donc des graphes caractérisés par la mise en évidence de relations triangulaires fortes (Simméliennes), c’est à dire, des relations reliant fortement trois personnes :

C’est cela qui permet de déduire la colonne vertébrale simmélienne (Simmelian backbone), qui représente les interactions des communautés réduites à l'essentiel. Cet algorithme fonctionne notamment sur Facebook, puisque la méthode a été testée sur ce réseau.

Présentation du jeu de données Facebook100

Tout au long de l’article, divers exemples montrent les résultats de leur algorithme. Ils utilisent pour cela le jeu de données Facebook100 dataset, que nous avons trouvé après quelques recherches sur Internet. Une fois récupéré, le problème s’est posé de savoir sous quel format et comment lire les données fournies, ce qui n’était pas précisé.

Le jeu est constitué principalement de fichiers Matlab. Sont présents :

  • Un groupe de 100 fichiers, un par université, contenant chacun 2 matrices :
    • Une première, nommée A, contient les relations d’amitié entre tous les étudiants de l'université. Il s’agit d’une matrice creuse (sparse matrix), comme nous le verrons après.
    • Une seconde, nommée local_info, contient une ligne par élève avec les informations suivantes dans leur ordre respectif : sexe, année d'obtention du diplôme, dortoir, 1ère matière majeure, 2ème matière majeure, lycée, et statut d’étudiant.
  • Un fichier contenant le nom des lycées d’origine des élèves (schools.mat).
  • Un fichier Readme qui explique notamment les structures de données A et local_info
  • Un fichier pdf décrivant plus en détail Facebook100.

Implémentation

1) Initialisation du graphe

Afin d’utiliser le jeu de données sous Tulip, c’est-à-dire d’importer les matrices d’une université dans notre code Python, nous avions au départ choisi d’extraire les données au format CSV. Étant donné que l’opération s'avérait trop fastidieuse pour une centaine de fichiers, nous avons trouvé une bibliothèque permettant de lire des matrices Matlab en python : Numpy.

La matrice A (amitiés) est une matrice creuse et a nécessité quelques astuces pour être lue correctement, trouvées dans la documentation de la librairie Scipy/Numpy.

On définit Ego et Alter, une relation d’amitié entre deux utilisateurs, avec Ego la première personne et Alter la seconde, quand il est utile de les prendre dans un ordre (à partir de l’étape B l’ordre est important). La relation d’”amitié” que nous utilisons dans le rapport se comprend au sens d’amitié sur un réseau social, c’est-à-dire une simple connexion entre 2 personnes.

Pour obtenir le graphe initial, nous créons simplement un noeud pour chaque étudiant de l’université, et des arêtes pour représenter les amitiés. On notera que le graphe est directionnel, et que chaque amitié est représentée par deux arêtes, l’une allant de Ego vers Alter et l’autre allant d’Alter vers Ego. Ce doublage des arêtes est utile pour la suite.

2) Algorithme

Nous procédons ici à l’implémentation de l’algorithme présenté dans l’article. Toutes les étapes de l'algorithme s'appliquent à chaque arête.

A) Poids / Force : Il s’agit du poids que l’on va attribuer à l'arête entre Ego et Alter. Nous calculons pour cela le nombre d’amis communs à Ego et Alter. Sur l'image suivante Ego et Alter ont deux amis en commun, leurs arêtes ont donc un poids de 2.

B) Rang : On trie les amis d'Ego selon le poids des arêtes sortantes, en ordre décroissant. Le rang de chaque arête sortant d’Ego est affecté du rang entre Ego et l’ami de l’autre côté de l’arête. Sur l'image suivante des poids arbitraires (en rouge) ont été définis. Les poids triés se suivent ainsi : 6, 4, 2, 1. Pour son ami Alter qui a un poids de 2, Ego le classe donc 3ème et l'arête obtient un rang de 3 (en vert).

C) Redondance : On définit un paramètre k, au-dessus duquel on considère qu'un rang est faible. Dans le graphe obtenu en B, où on ne va prendre en compte que les arêtes de rang ⇐ k, on compte les voisins partagés par Ego et Alter. C'est ce nombre qui donne la redondance de l'arête. Sur l'image suivante, des rangs arbitraires (en vert) ont été ajoutés, et on prend k = 5. Pour l'ami commun A, les rangs du triplet sont tous inférieurs à 5 (3, 4, 2), on ajoute +1 à la redondance. Pour l'ami commun B, deux des rangs du triplet sont supérieurs à 5, on ne change pas la redondance. Au final elle vaut 1 ici et est ajoutée à l'arête Ego→Alter (en bleu).

D) Filtrage : On seuille, c’est à dire que l’on supprime toutes les arêtes dont le rang est trop grand, puis dont la redondance est trop faible. On définit ainsi un paramètre maximum pour le rang (rangmax), et un paramètre de redondance minimum (redondmin). Le sous-graphe obtenu est le simmelian backbone.

Code et instructions d’utilisation

Afin d’économiser de l’espace car les fichiers peuvent être lourds, jusqu’à plusieurs mégaoctets, nous avons fourni notre code avec une version de Facebook100 largement réduite et suffisante pour obtenir des résultats. Parmi les universités, nous n’avons laissé que Caltech, l’un des exemples utilisés dans l’article. Cependant, si nécessaire, un lien vers le téléchargement complet du jeu de données est proposé ici.

Lien vers l'archive de notre code

Si besoin, lien vers le jeu de données complet, Facebook100 :

https://archive.org/details/oxford-2005-facebook-matrix

Pour tester le code, on effectuera les opérations suivantes :

  • Lancer le projet Tulip “simmelian.tlpx”
  • Lancer l’un des scripts suivants :
    • baseGraph.py : Calcule le graphe initial (avant l’algorithme)
    • fbgraph.py : Calcule le graphe simmélien (obtenu grâce à l’algorithme)
  • Choisir une méthode de visualisation (par exemple GRIP).

N.B. : nous avons parfois rencontré des problèmes à l’utilisation d’un chemin relatif, pour sélectionner l’université à traiter. Si cela pose problème, il peut être utile d’essayer le chargement du fichier université avec un chemin absolu.

Visualisation et résultats obtenus

Note importante : Dans toute cette section, les données présentés sont celles obtenues grâce aux relations d’amitiés de l'université California Institute of Technology (Caltech36.mat). Il est utile de préciser également qu’à l’instar de l’article, seules les données d’amitié sont considérées dans le calcul du “simmelian backbone”. Les informations récupérées dans la variable local_info (dortoir, genre, etc.) ne sont pas prises en compte.

Influence des paramètres

Pour obtenir un graphe lisible, il a fallu déterminer quels étaient les paramètres que l’on allait donner à l’algorithme. L’article en lui même ne définit pas de rang ou de redondance idéale, laissant aux lecteurs le soin de définir la meilleure combinaison. Dans l’exemple du tableau ci-dessous (obtenu avec nos propres tests), on remarque déjà la forte diminution du nombre des arêtes grâce à notre algorithme. Il semblerait également qu’à rang égal, la redondance minimale a un impact significatif.

Nombre d’arêtes
Graphe d’origine 33 312
rangmax = 10 et redondmin = 1 6289
rangmax = 8 et redondmin = 2 4276
rangmax = 10 et redondmin = 5 3091

rangmax : valeur maximale du rang

redondmin : minimum de redondance des les liens d’amitié

Choix du layout

L’article ne précise pas comment il organise les données à l’affichage après avoir effectué toutes les opérations. Nous avons donc testé plusieurs approches proposées par Tulip, quatre d’entre elles faisant partie du groupe “Force directed”. Elles donnent un visuel esthétique et s’approchent du rendu de l’article :

  • Fast Multipole Embedder
  • FM ^3
  • Frutcherman Reingold
  • GRIP (Graph dRawing with Intelligent Placement)

Ce dernier étant celui que nous avons retenu, notamment pour les deux dernières captures d’écran ci-dessous.

Résultats obtenus par les auteurs pour le graphe des amis Facebook de l'université Caltech. À gauche, le graphe initial avec tous les liens d'amitiés. À droite, le graphe réduit au simmelian backbone, avec une redondance supérieure à 5 parmi le top 10 du rang des voisins. Les couleurs représentent les dortoirs.

Notre graphe initial de la même université, également coloré selon les dortoirs, en exécutant notre script python “baseGraph.py” avec le layout GRIP. Certains point isolés apparaissent, il s'agit de personnes sans amis. Ces noeuds ont probablement été enlevés par les auteurs dans leurs résultats.

Notre graphe simmélien avec l'algorithme, toujours avec le layout GRIP mais en exécutant “fbgraph.py” . Pour cet exemple nous avons défini les paramètres rangmax à 10 et redondmin à 5. Ici aussi nous n’avons pas supprimé l’affichage des noeuds sans arêtes qui se retrouvent donc sur le côté de l’image.

Conclusion

L'algorithme Simmelian backbone nous a permis de visualiser un réseau social selon des critères minimalistes, formant un squelette. Nous en avons implémenté une version fonctionnelle et complète. L’un des points que nous n’avons pas pris en compte est la variante du calcul de la redondance proposée par les auteurs, qui n’utilise pas de paramètre k. Les rendus visuels obtenus sont toutefois satisfaisants puisqu'ils sont proches des résultats des auteurs de l’article, même s'il est délicat de les comparer puisque nous ne savons pas quel algorithme de visualisation ils ont utilisé. On constate également que l'un des objectifs du graphe simmélien est atteint, montrer les communautés, puisque l'on voit de forts liens d'amitié au sein de mêmes dortoirs.

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/delesse_valette/alexandre_delesse_joris_valette.txt · Last modified: 2014/01/17 01:47 by jvalette