La physique pratique et l'art des graphs

Publié le 11 Juin 2008

Well... je n'ai toujours pas fait ma partie 2 sur les chaines de Markov, pourquoi ?
Et pourquoi je fais joujou avec des attracteurs et des répulseurs à la place, d'abord ?
Pour la partie 2 de mon article, je voudrai créer un graph, comme celui du hamster.
Mais si on remplace les "etats" par des "mots" ca fait un paquet de noeuds, un gros, plusieurs milliers. Et même avec quelques douzaines c'est déjà pas facile.

Quel est le problème ?

Pour faire un graph on va poser des "noeuds" sur une page, et relier ces noeuds avec... des "liens".
La question qui se pose très rapidement est "comment disposer mes noeuds de facon optimale pour eviter que ca soit le gros bordel ?"

Il existe plusieurs méthodes, qui font appel à la physique.

Prenez un tableau noir.
Posez y delicatement vos noeuds.
Considerez chaques noeuds comme un répulseur à noeuds.
Ajoutez un peu de force de frottement.
Chacuns des noeuds vont se repousser les un les autres, la force de frottement les forcant à s'arreter une fois que la force de répulsion (qui est inversement proportionelle au carré de la distance) deviens trop faible.

Voila, vos noeuds s'organisent tout seuls.
Et même mieux, à chaque fois que vous allez rajouter un noeud sur le tableau, l'équilibre des forces va s'en trouver perturbé et les noeuds vont se déplacer jusqu'à trouver un nouvel équilibre.

Mais... ce n'est n'est pas complet.
Il manque les liens.

Les noeuds sont disposés de facon plus ou moins uniforme, mais ne tiennent pas comptent des liens, on risque de se retrouer avec un enorme tas de spaghettis avec des liens dans tous les sens.

Pour régler ce problème, afin d'éviter 50000 chevauchements qui rendraient la lectere du graph impossible, on va tenter d'avoir les liens les plus courts possibles. Plus ils sont courts, moins ils se chevaucheronts.

On va utiliser des ... ressorts ! Objet physique connu du commun des mortels.
Un ressort a une longeur fixe au repos et si on l'etire ou le compresse, il va essayer de retrouver sa longueur de repos.
Si on relie 2 noeuds eloignés l'un de l'autre, la force du ressort va les rapprocher (et raccourcir la longueur du lien).
Si les noeuds sont trop proches, la force du ressort va les eloigner l'un de l'autre, jusqu'à obtenir un equilibre.

Bilan :
- nous aurons des noeuds disposés de facon assez uniforme pour être lisible
- les noeuds reliés entre eux auront tendances à se regrouper.
- les noeuds qui ne sont pas reliés entre eux auront tendances à se repousser.
- Et voila ! ou presque ...

Imaginons :

Et si on considère que ces noeuds ne sont plus des mots, mais une identité numérique, et qu'on renomme pompeusement ce graph en "reseau social" ?
Et les particules dans tout ca ? Qu'est ce qu'on pourrait bien en ... *buzzzz*... oups... en faire ?
Et quel rapport avec Markov dans tout ca ?

Ha ! On vera bien !!

Résolution N°3 : Du teasing, je ferai aussi.

google info : Fruchterman-Reingold force-directed graph

Rédigé par kerunix Flan

Publié dans #y'a de l'idée

Repost 0