Could social web be a graph?

Yoan Blanc — Wed, 24 Jan 2007 — , , ,

While I’m playing with LinkedIn there are some questions that comes to me.

  • How to play with all these relations?
  • Is it hard to know at which level is this person from me?
  • Or if he/she is in my network at any level?
  • Is this kind of Semantic Web? Or be expressed this way? (obviously yes, be easily, I can’t tell)

I remembered the math lessons from two or three years ago, I love mathematics more than ever now. Hard to pratice during lunch time. Friendship is a graph, instead of RDF not directed. And friendship could represented as a Simple Graph. So I tried to do a graph Graphviz that is cool for displaying them and Ruby because I need to more (and more) about it and the way you can hack things with it.

For the math part, I started with the Adjacency Matrix that is a pretty simple 0 or 1 n✕n matrix.

Next step is to generate a .dot file to GraphViz. This is easy.

A rich information should be at which level from the given node are the others? What I need is a function that gives me the levels of the nodes from the current one. It require only a few minutes of braining, and more to code it (especially with my poor experience, but I’m working on it, with Ruby).

And the result could be, this nice picture. Use this script this way (remove the tube part to see the .dot file): 

./graph.rb 26 .93 | dot -Tgif -o graph.gif

Parameters are 26 nodes and 93% chance of unknowing another node.

My conclusion is that even with only few connections by node, the depth of the friend’s friend is very low and that it’s hard to obtain deep levels. I think that people in a modest town can reach everybody in it with only 3 or 4 levels.

Alors que je joue avec LinkedIn tout un tas de questions me viennent à l’esprit, spécialement en matière de web social et de réseau (ce dernier ne fait que du réseautage et depuis peu du social avec partimonie).

  • Comment font-ils pour jongler avec toutes ces relations ?
  • Est-ce complexe de savoir à quel niveau se trouve telle ou telle personne de moi ? Voire connaître si elle fait partie de mon réseau ou non ?
  • Ceci peut-il être fait en passant par le Web Sémantique ? Si oui, comment de manière légère, SPARQL (via FOAF) me semblant lourd, l’est-il ?

Cogitant avec tout ça, j’ai ressorti les vieilles mathématiques du tiroir, j’apprécie beaucoup les maths mais c’est difficile d’en faire régulièrement une fois sorti d’un cadre scolaire je trouve. Spécialement, si on ne veut pas être considéré comme une espèce d’autiste (l’autisme étant bien évidemment complétement différent dans 99.9% des case)

Le modèle de base de relations entre personnes est le graphe, dit graphe simple car sans boucle ni multiple liens. Ce graphe peut être représenté par sa matrice d’adjacence qui se compose de 0 et de 1, un 1 indiquant un lien entre les deux noeuds.

Une fois ce modèle identifié, mon idée a été de pouvoir générer des graphes et les visualiser simplement. L’outil de visualisation a coulé de source : Graphviz qui est aussi simple que flexible. Ensuite, j’ai choisi le langage Ruby pour générer le format lu par ce dernier, nommé DOT. Ruby car, j’ai du travail de dégrossissage avec ce langage là pour commencer à en faire un bon usage.

Le système fonctionne ne trois étapes.

  1. Génération d’une matrice d’adjacence ;
  2. Calcul des profondeurs respectives des noeuds vis-à-vis d’un noeud choisi ;
  3. Génération d’un fichier au format DOT.

Un résultat est visible ici. Il a été généré via ce script avec le jeu de commandes suivant qui va générer un graphe de 26 noeuds qui ont chacun 93% de chance de ne pas avoir de relation avec un autre noeud donné. 

./graph.rb 26 .93 | dot -Tgif -o graph.gif

En conclusion de cette petite expérimentation je dirais qu’il n’est pas si compliqué de jouer avec ses relations (tout en restant à des niveaux raisonnables) et que de mettre au point un modèle entité-relation représentant ces principes là ne me semblent pas hors de portée. Autre point intéressant (et plutôt sociologique pur que geek pur) étant qu’il faut malgré tout peu de relations pour que la profondeur soit faible, qu’un noeud puisse atteindre tous les autres rapidement. Je pense que dans une ville de dimension modeste, une personne doit pouvoir en 3 ou 4 niveau atteindre tout le monde.

Plus personnellement, je n’ai jamais aimé en rencontrant quelqu’un et me disant que c’était une personne complètement nouvelle de me rendre compte qu’on a un bon bout de nos d’amis, connaissances qui sont communs. Avoir joué au scientifique fou, va peut-être me rendre plus ouvert pour ces aspects là.