Actualités du LIPN

Éric Mermet présentera ses travaux le 2 décembre à 14h15 dans la salle de séminaires LITIS/LMAH à UFR ST du Havre

Un réseau de transport repose sur la trame d’un système spatial dont le rôle est de mettre en relation des lieux sur un territoire. C’est aussi un objet géographique complexe qui peut être étudié de plusieurs façons. Une analyse dite thématique ou fonctionnelle permet d’extraire de nombreuses informations (enquêtes ménage déplacement, études de flux migratoires, etc.) mais demande un accès, souvent difficile, à des données hétérogènes. Une analyse structurelle, si elle ne substitue pas à une analyse thématique, permet néanmoins de dégager de l’information et notamment la part investie par le réseau dans la compréhension d’un phénomène. Elle repose sur la construction et l’analyse d’indicateurs basés sur les relations proposées par le réseau et ne demande donc pas d’avoir accès à des données particulières. Ces indicateurs relationnels, comme la centralité, l’accessibilité, les chemins de contournement locaux, etc., permettent d’expliciter en quoi la structure, l’organisation spatiale et topologique des composantes du réseau prédisposent à la mise en relation plus ou moins aisée de lieux de l’espace. Or, ce type d’analyse engendre trois complexités :

  - une complexité combinatoire liée au nombre de relations Origine-Destination existantes sur le réseau,
   - une complexité algorithmique liée aux calculs mathématiques des indicateurs,
   - et une complexité visuelle liée à la mise en valeur d’informations pertinentes par une cartographie aisément compréhensible.

Le modèle proposé dans cette thèse vise à contrôler les complexités décrites et, in fine, à faciliter l’analyse de la structure d’un réseau aux utilisateurs (urbanistes, gestionnaires de réseaux, aménageurs, chercheurs). Cette analyse repose sur la création de cartes exploratoires ciblées et donc liées à un phénomène particulier que l’on cherche à analyser. Pour cela, un langage graphique informatique a été mis en place dans lequel il est possible de combiner visuellement ces cartes à l’aide de différents opérateurs. L’analyse n’est alors plus linéaire mais devient arborescente, rapprochant ce raisonnement du processus de pensée de l’utilisateur. Ces aspects ont été développés dans un outil logiciel baptisé GeoGraphLab.

Le séminaire OCAD recevra le 6 avril Damien Regnault (ATER au LIF-CMI, Marseille).

Cet exposé commence par la présentation rapide de la règle Minorité stochastique et de ses particularités. Ensuite, je présenterai une application de cette règle pour modéliser la formation de quasi-cristaux.

Considérons un graphe où chaque sommet reçoit la couleur noire ou blanche. Une arête contient une erreur si elle relie deux sommets de la même couleur. Minorité est une dynamique stochastique minimisant rapidement l’énergie. Sous cette dynamique, un sommet, chosi aléatoirement et uniformément parmi l’ensemble des sommets, peut changer d’état si au moins la moitié des arêtes qui lui sont adjacentes sont erronées.. Cette dynamique est sensible à la topologie du graphe et son analyse fine s’est révélée compliquée.

En physique, dans les années 70, il était conjecturé que toutes les structures ordonnées soient périodiques. En 1984, un contre-matériaux fût découvert et reçu le nom de quasi-cristal. Dès 1974, Penrose avait présenté un structure théorique ordonnée et apériodique. Le but de notre projet est de présenter un modèle pour expliquer la formation d’une telle structure. Pour cela, nous considérons le modèle des pavages par coupe et projection (qui contient le pavage de Penrose). En définissant une notion d’erreur et d’énergie sur ces pavages, la règle Minorité procédant par flips permet de converger rapidement expérimentalement vers une structure ordonnée qui selon la famille de pavages par coupe et projection considérée est soit périodique, soit apériodique. Je présenterai nos résultats expérimentaux ainsi que notre analyse de cette dynamique pour les pavages 2 vers 1 (mots sur deux lettres).