{"id":196,"date":"2012-08-06T04:01:32","date_gmt":"2012-08-06T02:01:32","guid":{"rendered":"http:\/\/blog.nebule.org\/?p=196"},"modified":"2016-03-29T19:05:02","modified_gmt":"2016-03-29T17:05:02","slug":"trace-de-graphes-objetsliens","status":"publish","type":"post","link":"http:\/\/blog.nebule.org\/?p=196","title":{"rendered":"Trac\u00e9 de graphes objets\/liens, le d\u00e9but"},"content":{"rendered":"

La deuxi\u00e8me exp\u00e9rience monte le manque de repr\u00e9sentation graphique des objets et liens g\u00e9n\u00e9r\u00e9s.<\/p>\n

Suite \u00e0 la publication d’un projet personnel de Ruslan Enikeev<\/em>, je me suis int\u00e9ress\u00e9 \u00e0 son travail sur The Internet map<\/a> :<\/p>\n

\"\"<\/a><\/p>\n

<\/p>\n

Th\u00e9orie<\/h2>\n

Un des travaux r\u00e9alis\u00e9s (CMU-CS-98-189<\/a>) consiste en une recherche sur le tracer de graphes. Quelques cas particuliers sont abord\u00e9s, mais une grande partie concerne le cas g\u00e9n\u00e9ral et les m\u00e9thodes pour acc\u00e9l\u00e9rer les calculs.<\/p>\n

Il parle de vertices et d’edges l\u00e0 o\u00f9 nebule parle d’objets et de liens.<\/p>\n

Copie du document de r\u00e9f\u00e9rence 2 : CMU-CS-98-189<\/a><\/p>\n

Deux solutions, soit trouver et utiliser des librairies pour tracer les graphes sans trop me poser de question, soit mettre au point une m\u00e9thode plus personnelle et plus simple. Rien que de lire le document sans entrer en profondeur dans la r\u00e9flexion, cela donne des id\u00e9es.<\/p>\n

Voici mon id\u00e9e…<\/p>\n

Graphe de base<\/h2>\n

Partons d’un graphe simple dont les donn\u00e9es sont :
\n– objets : O={1; 2; 3; 4; 5; 6; 7; 8; 9}
\n– liens : L={1-2; 1-3; 2-7; 2-8; 2-9; 3-4; 3-5; 3-6}<\/p>\n

La repr\u00e9sentation graphique que l’on peut en faire \u00e0 la main :<\/p>\n

\"\"<\/a><\/p>\n

C’est le graphe d’origine<\/em>.<\/p>\n

Dans le document de r\u00e9f\u00e9rence 2, un des point qui m’a attir\u00e9 est la repr\u00e9sentation en projection sur un cercle ou sur une boule. Au lieu de partir des donn\u00e9es et d’essayer de reconstruire le trac\u00e9 du graphe (que j’appellerais graphe<\/em> pour simplifier), essayons plut\u00f4t de partir du trac\u00e9 et de le faire converger vers les donn\u00e9es que l’on conna\u00eet.<\/p>\n

Projection sur un cercle<\/h2>\n

La premi\u00e8re \u00e9tape est donc de projeter le graphe sur un cercle :<\/p>\n

\"\"<\/a><\/p>\n

D\u00e9j\u00e0, 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\u00e9s.
\nEn fait, c’est une simplification. Mais il ne serait peut-\u00eatre pas int\u00e9ressant plus tard de redonner \u00e0 l’objet 1 la position centrale.<\/p>\n

On voit que les objets ont une place bien d\u00e9finie (et sym\u00e9trique) sur le cercle. Repr\u00e9sentons le cercle \u00e0 plat, \u00e7a donne \u00e7a :<\/p>\n

9 8 2 7 1 4 3 5 6<\/pre>\n
Cette forme est \u00e0 prendre comme circulaire donc, le 9 est aussi \u00e0 c\u00f4t\u00e9 du 6. Et cette forme est optimale dans le sens o\u00f9 les distances entre objets li\u00e9s sont les plus courtes. On y reviendra.<\/p>\n
Reconstruction du graphe depuis le cercle<\/h2>\n
Comment reconstruire le graphe \u00e0 partir des objets projet\u00e9s sur le cercle ?<\/p>\n
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<\/em> le nombre de liens des objets.<\/p>\n
O M<\/strong>\n1 2\n2 4\n3 4\n4 1\n5 1\n6 1\n7 1\n8 1\n9 1<\/pre>\n
Max=4, Min=1, masse totale=16<\/p>\n
On r\u00e9partit \u00e9quitablement les objets autour du cercle en respectant leur ordre. L’objet 1 reste en bas, il va nous servir de r\u00e9f\u00e9rence.<\/p>\n
Sommairement, cela donne \u00e7a :<\/p>\n
\"\"<\/a><\/p>\n
On a un graphe assez lisible. Il n’y a ni concentration exag\u00e9r\u00e9e d’objets, ni liens qui se croisent.<\/p>\n
On constate aussi que les objets sont plac\u00e9s naturellement sur des cercles concentriques en fonction de leur masse.<\/p>\n
Mais l’objet 1 est un peu repouss\u00e9 du centre alors qu’il \u00e9tait 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\u00e9n\u00e9ficie pas des objets qui gravitent un peu plus loin autour de lui. On peut essayer d’en tenir compte.<\/p>\n
Reconstruction du graphe depuis le cercle v2<\/h2>\n
En premi\u00e8re approximation, on reprend le calcul des masses<\/em> des objets mais en additionnant les liens directs, dits de niveau 1, et les liens des objets voisins proches, dit de niveau 2.<\/p>\n
O M<\/strong>\n1 10\n2 9\n3 9\n4 5\n5 5\n6 5\n7 5\n8 5\n9 5<\/pre>\n
Max=10, Min=5, masse totale=58<\/p>\n
Sommairement, cela donne \u00e7a :<\/p>\n
\"\"<\/a><\/p>\n
Il faudra affiner le calcul de la masse<\/em>, peut-\u00eatre en prenant en compte plusieurs niveaux arborescents mais avec une pond\u00e9ration d\u00e9gressive. Peut-\u00eatre ajouter une pond\u00e9ration subjective par objet dans le calcul de leur masse<\/em>.<\/p>\n
Calcul de positionnement dans le graphe<\/h2>\n
Le d\u00e9placement peut \u00eatre calcul\u00e9 en tenant compte de la masse<\/em> calcul\u00e9e des objets, mais aussi en tenant compte de la masse<\/em> maximum et de la masse<\/em> minimum.<\/p>\n
Il est inutile de recalculer la position des objets dont la masse<\/em> est la plus faible, ceux-ci resteront sur le cercle le plus ext\u00e9rieur. La valeur de Min devient ainsi une r\u00e9f\u00e9rence.<\/p>\n
Comme on a dit que l’on ne pla\u00e7ait rien en position centrale, la valeur Max doit \u00eatre sur le cercle le plus int\u00e9rieur mais pas au centre.<\/p>\n
Proposition de formule :<\/p>\n
Max - Min\nDn<\/em> = (Mn<\/em> - Min) x ---------------               \u00c2\u00a0\u00c2\u00a0\u00c2\u00a0\n1 + Max - Min<\/pre>\n
Organisation optimal des objets sur le cercle<\/h2>\n
Le pr\u00e9-positionnement des objets est important. C’est cette \u00e9tape qui, en triant les objets en fonction de leurs liens, va permettre un arrangement harmonieux et surtout qui va permettre d’\u00e9viter autant que possible le croisement de liens.<\/p>\n
Reprenons l’arrangement issue du graphe d’origine :<\/p>\n
9 8 2 7 1 4 3 5 6<\/pre>\n
Tous les liens sont pos\u00e9s entre deux objets \u00e0 distance de 1 ou de 2 l’un de l’autre. Aucun lien n’est fait \u00e0 une distance de plus de 2.<\/p>\n
Mais cet arrangement \u00e9tait d\u00e9j\u00e0 trouv\u00e9 depuis le graphe d’origine, qui est ce que l’on cherche. Reprenons les objets dans un ordre diff\u00e9rent (ou al\u00e9atoire) :<\/p>\n
1 2 3 4 5 6 7 8 9<\/pre>\n
Cet arrangement semble \u00e0 peu pr\u00e8s optimal pour les objets 1 \u00e0 5. Mais pour les suivants ce n’est pas du tout le cas. L’objet 9 est \u00e0 une distance de 8 de l’objet 1, on peut difficilement faire pire.<\/p>\n
Dans le document de r\u00e9f\u00e9rence 2, il est beaucoup question de trie d’objets \u00e0 partir de mod\u00e8les physiques, c’est \u00e0 dire par attraction\/r\u00e9pulsion avec des fonctions lin\u00e9aires ou exponentielles ou par polyn\u00f4mes.<\/p>\n
A compl\u00e9ter …<\/p>\n
Questions en attente<\/h2>\n
1 – Am\u00e9liorer\/affiner le calcul de masse des objets pour leur positionnement dans la construction du graphe en tenant compte des objets proches.
\n2 – D\u00e9finir et int\u00e9grer une pond\u00e9ration dans le calcul de masse des objets pour leur positionnement dans la construction du graphe.
\n3 – Calculer l’organisation optimale des objets sur le cercle.<\/p>\n
R\u00e9f\u00e9rences<\/h2>\n
1 – The Internet map<\/a>
\n2 – CMU-CS-98-189<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
La deuxi\u00e8me exp\u00e9rience monte le manque de repr\u00e9sentation graphique des objets et liens g\u00e9n\u00e9r\u00e9s. Suite \u00e0 la publication d’un projet personnel de Ruslan Enikeev, je me suis int\u00e9ress\u00e9 \u00e0 son travail sur The Internet map :<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[83,6,24],"tags":[],"_links":{"self":[{"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/posts\/196"}],"collection":[{"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=196"}],"version-history":[{"count":1,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/posts\/196\/revisions"}],"predecessor-version":[{"id":2356,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=\/wp\/v2\/posts\/196\/revisions\/2356"}],"wp:attachment":[{"href":"http:\/\/blog.nebule.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=196"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=196"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.nebule.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=196"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}