Tracé de graphes objets/liens, le début

La deuxième expérience monte le manque de représentation graphique des objets et liens générés.

Suite à la publication d’un projet personnel de Ruslan Enikeev, je me suis intéressé à son travail sur The Internet map :

Théorie

Un des travaux réalisés (CMU-CS-98-189) consiste en une recherche sur le tracer de graphes. Quelques cas particuliers sont abordés, mais une grande partie concerne le cas général et les méthodes pour accélérer les calculs.

Il parle de vertices et d’edges là où nebule parle d’objets et de liens.

Copie du document de référence 2 : CMU-CS-98-189

Deux solutions, soit trouver et utiliser des librairies pour tracer les graphes sans trop me poser de question, soit mettre au point une méthode plus personnelle et plus simple. Rien que de lire le document sans entrer en profondeur dans la réflexion, cela donne des idées.

Voici mon idée…

Graphe de base

Partons d’un graphe simple dont les données sont :
– objets : O={1; 2; 3; 4; 5; 6; 7; 8; 9}
– liens : L={1-2; 1-3; 2-7; 2-8; 2-9; 3-4; 3-5; 3-6}

La représentation graphique que l’on peut en faire à la main :

C’est le graphe d’origine.

Dans le document de référence 2, un des point qui m’a attiré est la représentation en projection sur un cercle ou sur une boule. Au lieu de partir des données et d’essayer de reconstruire le tracé du graphe (que j’appellerais graphe pour simplifier), essayons plutôt de partir du tracé et de le faire converger vers les données que l’on connaît.

Projection sur un cercle

La première étape est donc de projeter le graphe sur un cercle :

Déjà, je ne peut pas centrer le cercle sur le graphe, parce que sinon on ne peut projeter l’objet 1 sur le cercle, et aussi parce que les objets 2 et 8 ainsi que 3 et 5 seraient superposés.
En fait, c’est une simplification. Mais il ne serait peut-être pas intéressant plus tard de redonner à l’objet 1 la position centrale.

On voit que les objets ont une place bien définie (et symétrique) sur le cercle. Représentons le cercle à plat, ça donne ça :

9 8 2 7 1 4 3 5 6

Cette forme est à prendre comme circulaire donc, le 9 est aussi à côté du 6. Et cette forme est optimale dans le sens où les distances entre objets liés sont les plus courtes. On y reviendra.

Reconstruction du graphe depuis le cercle

Comment reconstruire le graphe à partir des objets projetés sur le cercle ?

Les objets les plus au centre du graphe d’origine sont ceux qui ont le plus d’importance, en fait ceux qui ont le plus d’objets autour, et donc de liens. On va faire une sorte de gravitation qui prend comme masse le nombre de liens des objets.

O M
1 2
2 4
3 4
4 1
5 1
6 1
7 1
8 1
9 1

Max=4, Min=1, masse totale=16

On répartit équitablement les objets autour du cercle en respectant leur ordre. L’objet 1 reste en bas, il va nous servir de référence.

Sommairement, cela donne ça :

On a un graphe assez lisible. Il n’y a ni concentration exagérée d’objets, ni liens qui se croisent.

On constate aussi que les objets sont placés naturellement sur des cercles concentriques en fonction de leur masse.

Mais l’objet 1 est un peu repoussé du centre alors qu’il était en position centrale dans le graphe d’origine. En ne prenant en compte en masse que le nombre de lien directs d’un objet, il ne bénéficie pas des objets qui gravitent un peu plus loin autour de lui. On peut essayer d’en tenir compte.

Reconstruction du graphe depuis le cercle v2

En première approximation, on reprend le calcul des masses des objets mais en additionnant les liens directs, dits de niveau 1, et les liens des objets voisins proches, dit de niveau 2.

O M
1 10
2 9
3 9
4 5
5 5
6 5
7 5
8 5
9 5

Max=10, Min=5, masse totale=58

Sommairement, cela donne ça :

Il faudra affiner le calcul de la masse, peut-être en prenant en compte plusieurs niveaux arborescents mais avec une pondération dégressive. Peut-être ajouter une pondération subjective par objet dans le calcul de leur masse.

Calcul de positionnement dans le graphe

Le déplacement peut être calculé en tenant compte de la masse calculée des objets, mais aussi en tenant compte de la masse maximum et de la masse minimum.

Il est inutile de recalculer la position des objets dont la masse est la plus faible, ceux-ci resteront sur le cercle le plus extérieur. La valeur de Min devient ainsi une référence.

Comme on a dit que l’on ne plaçait rien en position centrale, la valeur Max doit être sur le cercle le plus intérieur mais pas au centre.

Proposition de formule :

Max - Min
Dn = (Mn - Min) x ---------------                  
1 + Max - Min

Organisation optimal des objets sur le cercle

Le pré-positionnement des objets est important. C’est cette étape qui, en triant les objets en fonction de leurs liens, va permettre un arrangement harmonieux et surtout qui va permettre d’éviter autant que possible le croisement de liens.

Reprenons l’arrangement issue du graphe d’origine :

9 8 2 7 1 4 3 5 6

Tous les liens sont posés entre deux objets à distance de 1 ou de 2 l’un de l’autre. Aucun lien n’est fait à une distance de plus de 2.

Mais cet arrangement était déjà trouvé depuis le graphe d’origine, qui est ce que l’on cherche. Reprenons les objets dans un ordre différent (ou aléatoire) :

1 2 3 4 5 6 7 8 9

Cet arrangement semble à peu près optimal pour les objets 1 à 5. Mais pour les suivants ce n’est pas du tout le cas. L’objet 9 est à une distance de 8 de l’objet 1, on peut difficilement faire pire.

Dans le document de référence 2, il est beaucoup question de trie d’objets à partir de modèles physiques, c’est à dire par attraction/répulsion avec des fonctions linéaires ou exponentielles ou par polynômes.

A compléter …

Questions en attente

1 РAm̩liorer/affiner le calcul de masse des objets pour leur positionnement dans la construction du graphe en tenant compte des objets proches.
2 РD̩finir et int̩grer une pond̩ration dans le calcul de masse des objets pour leur positionnement dans la construction du graphe.
3 – Calculer l’organisation optimale des objets sur le cercle.

Références

1 – The Internet map
2 – CMU-CS-98-189