Réseaux spatiaux : modèles, classification et flux

Thèse soutenue par Guillaume Guex le 7 avril 2016, Institut de géographie et durabilité (IGD)

Un réseau spatial est une structure constituée d’objets appelés noeuds, localisés dans l’espace, et possédant des connexions de différentes nature appelées arêtes. Cette définition comprend un large panel de structures. Les réseaux routiers, aériens, ferroviaires, de lignes électriques, de rivières, etc. ne sont que quelques exemples de réseaux spatiaux que nous côtoyons tous les jours.

Contrairement aux réseaux usuels, qui ne possèdent pas de composante spatiale, maintenir une connexion entre deux noeuds d’un réseau spatial requiert un coût qui va dépendre de la distance séparant ces noeuds, et la structure du réseau tout entière est alors intimement liée à l’espace. L’analyse du rapport existant entre l’espace et la structure du réseau n’est pas chose aisée et les approches permettant d’y arriver sont nombreuses. Ce travail se concentre sur la création de modèles mathématiques facilitant cet objectif, en particulier à l’aide de modèles de flux.

Un flux peut être interprété comme une quantité de matière créée par un certain nombre de noeuds appelés sources, naviguant sur les arêtes du réseaux pour finalement être absorbée par d’autres noeuds, appelés cibles. Le comportement adopté par le flux lors de sa navigation est généralement dicté par la minimisation d’une fonction, et en choisissant judicieusement cette dernière, il est possible d’obtenir des flux permettant une exploration particulière de la structure du réseau. L’ingrédient principal de cette thèse sera un modèle de flux inédit, appelé le flux de transport randomisé. Ce flux, dont le comportement peut être ajusté par un paramètre, est à la croisée entre le flux de transport optimal et le flux aléatoire. Lorsque le paramètre est bas, ce flux permettra de transporter la matière dont il est constitué des sources jusqu’aux cibles en minimisant les coûts.

A l’opposé, lorsque le paramètre est élevé, ce flux suivra une marche aléatoire, explorant la totalité du réseau avant d’être absorbé. Ces deux extrêmes contiennent des flux qui ont été étudiés dans la littérature, mais nous verrons ici que lorsque la température est intermédiaire, le flux de transport randomisé adoptera alors un comportement inédit, permettant d’appréhender la structure du réseau de manière plus complète. Ce flux nous permettra de construire de nouveaux indices de centralité, de nouvelles dissimilarités et offrira une solution numérique efficiente à la résolution du problème de transport optimal dans un réseau.

Ce nouvel objet soulèvera également quelques questions fondamentales, dépassant largement le cadre des réseaux spatiaux. Un chapitre sur la création de modèles de réseaux spatiaux, similaires aux réseaux existants, viendra compléter l’analyse obtenue par les flux. Si le flux permet, entre autres, d’obtenir de l’information sur la position des noeuds dans l’espace grâce à la structure du réseau, ce dernier chapitre bouclera la boucle en faisant le travail en sens inverse : déduire l’information sur la structure d’un graphe spatial à partir de la position des noeuds dans l’espace.

Cette thèse, constituée d’articles “peer-reviewed” insérés au milieu d’un manuscrit rédigé à la suite de ceux-ci, présente deux niveaux de lecture. En lisant le manuscrit, un lecteur pourra comprendre les enjeux, le contexte et la problématique de notre approche sur l’analyse des réseaux spatiaux, tout en se familiarisant avec le formalisme. Cette lecture s’adresse ainsi à un large public, cependant familier avec les notations mathématiques. La lecture des articles, moins accessible, présente la réalité du travail scientifique accompli durant cinq années. Ces articles ne seront pas toujours parfaitement cohérents les uns par rapport aux autres, et les idées exposées évoluent au fil du temps. Néanmoins, leur lecture permet d’avoir les démonstrations et les résultats les plus significatifs, complétant ainsi le contexte donné par le manuscrit sous la forme d’avancées faites dans le domaine.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *