User Tools

Site Tools


chicoutimi_2016:modele_masses_ressorts_separabilite_noack

Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / May 6, 9am course

Modèle masses-ressorts et séparabilité

L'une des qualités recherchées d'un algorithme de dessin basé sur le modèle de masses-ressorts, est sa capacité à exhiber la structure du graphe. C'est-à-dire à faire ressortir les sous-groupes de sommets qui sont plus proches les un des autres – cette notion demande à être précisée, mais restons pour l'instant sur ce qu'elle évoque intituivement. Appelons ces groupes (que l'on recherche) des clusters.

C'est ce qu'a étudier Andreas Noack dans un article qui mérite d'être lu et relu. Il n'a pas à mon sens eu l'impact qu'il mérite, et nombre d'auteurs continuent à implémenter des modèles usés (moi y compris).

  • Noack, A. (2003). An Energy Model for Visual Graph Clustering. 11th International Symposium on Graph Drawing (GD 2003), Lecture Notes in Computer Science 2912, pp. 425-436.
  • Noack, A. (2003). Energy Models for Drawing Clustered Small-World Graphs, Computer Science Reports, Technical University Cottbus.

Pour faire simple, on aimerait pouvoir mesurer une distance entre deux sous-groupes d'un graphe, et que cette distance soit exhibée dans le dessin: que des sous-groupes qui sont connectés par peu d'arêtes se trouve à bonne distance (euclidienne) l'un de l'autre.

  • Soit un graphe et désignons par des sous-ensembles (et formant une bipartition: ; ).
  • On désigne par l'ensembles des arêtes de qui connectent des sommets l'un dans , l'autre dans
  • La densité associé à la bipartition est:

Les “bonnes” bipartitions, celles que tout algorithme cherche à calculer (à commencer par l'un des inventeurs du langage C (!) – Kernighan, B. W. and S. Lin (1970). “An Efficient Heuristic Procedure for Partitioning Graphs.” Bell System Technical Journal 49: 201-307), sont celles pour lesquelles la densité est minimale.

Lorsque le graphe est dessiné, c'est-à-dire qu'on a une position pour tout sommet , on peut alors associer à une bipartition une quantité évaluant combien les ensembles V_2$ sont “bien” séparés dans l'espace euclidien.

On peut ainsi définir un ensemble de distance entre et , comme par

qui calcule la distance minimum atteinte par une paire de sommets incidents et .

qui calcule la distance moyenne entre deux sommets incidents, c'est-à-dire la longueur moyenne des arêtes dans .

qui calcule la longueur harmonique moyenne des arêtes de la bipartition .

Force, énergie et potentiel

Les forces agissant sur les sommets, et prescrites par le modèle utilisé pour simuler les modèle de “masses et de ressorts” sont dérivées du potentiel associé à ces forces (que l'on peut voir comme un champ vectoriel – voir ici pour plus de détail).

Ainsi, dans les bon cas, on peut décrire de manière analytique, comme pour les forces, le potentiel en question, dont l'intégrale donne un scalaire représentant l'énergie qui y est associé, et qui varient en fonction des positions des sommets du graphe.

Noack remarque que la plupart des modèles “d'énergie” (calculé depuis l'ensemble des positions des sommets) sont de la forme:

Noack considère des potentiels s'exprimant tous sous la forme:

où correspond à l'intégrale (l'énergie) associée à l'action des force d'attraction, et correspond à l'intégrale (l'énergie) associée aux forces de répulsion.

Sous certaines conditions satisfaites par et , la fonction admet toujours un minimum global. Lorsque ce minimum est atteint au point , alors on a:

Le modèle initial de Eades

Par exemple, le potentiel associé au modèle présenté dans le cours est

pour lequel on a:

L'article de Noack inclus aussi d'autres modèles masses-resorts populaires (souvent implémentés). Il introduit aussi un modèle nouveau, le modèle LinLog définit par:

dont les forces associées sont relativement simple. La force d'attraction agit de manière constante, alors que la force de répulsion est inversement proportionnelle à la distance entre les sommets.

La trouvaille de Noack

Théorème. Soit un graphe connexe , un dessin dans (oui, en une dimension !) d'énergie LinLog minimale. Soit une bipartition de telle que les positions des sommets de sont toutes inférieures aux positions des sommets de . Alors:

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/modele_masses_ressorts_separabilite_noack.txt · Last modified: 2016/05/05 20:27 by melancon