Description

Dans un graphe temporel, chaque arête n'est disponible qu'aux moments spécifiques, et une marche doit prendre des arêtes en ordre croissant de temps. Par exemple, les graphes temporels peuvent être utilisés pour modéliser un réseau de transport public avec une connaissance exacte des horaires. Un autre exemple est la diffusion d'information par relai. Tout comme pour les graphes statiques classiques, les graphes temporels aléatoires et leurs propriétés sont désormais étudies.

Dans le projet proposé, nous cherchons à étendre la compréhension fondamentale du comportement général des graphes temporels aléatoires, au moins au niveau des résultats asymptotiques et sans modéliser les détailles des applications spécifiques.

De nombreuses questions qui sont simples pour les graphes statiques (par exemple, « quelle est la plus grande composante connexe ? » — qui ne demande que du temps linéaire) deviennent beaucoup plus difficiles (dans ce cas, NP-complète et difficile à approximer) pour les graphes temporels.

Même les notions les plus simples deviennent plus nuancées. Par exemple, si un graphe a un sommet accessible depuis chaque sommet et si tous les sommets sont accessibles depuis ce sommet choisi, ce n'est pas suffisant pour que chaque sommet soit accessible depuis tous les autres sommets.

Un exemple de question qui devient compliquée est la taille maximale d'une composante connectée dans le graphe, c'est-à-dire le nombre de sommets tous accessibles les uns depuis les autres. Dans le cas statique, cette question peut être résolue en temps linéaire, tant pour les graphes dirigés que pour les graphes non dirigés. Dans le cadre des graphes dynamiques, cependant, il ne suffit pas que A atteigne B et que B atteigne C pour que A atteigne C. Il est possible que la première marche de A à B arrive en B trop tard pour pouvoir continuer vers C. En particulier, le problème de la composante connexe maximale devient aussi difficile que la question de la taille maximale de la clique, c'est-à-dire NP-complète (et NP-difficile à approximer avec un facteur constant d'erreur).

Casteigts et al. ont étudié les propriétés des graphes aléatoires d'Erdős-Rényi avec des ordres aléatoires des arêtes, et ont établi plusieurs seuils de densité pour lesquels certaines propriétés sont atteintes. Ces propriétés comprennent la connexité temporelle et l'existence d'une squelette temporelle de taille linéaire, l'existence d'une source temporelle, etc. D'autres travaux menés avec un groupe plus important de coauteurs ont également permis d'établir un seuil précis pour l'existence d'une grande composante connexe dans le sens temporel. Cependant, les propriétés classiques étudiées pour les graphes statiques aléatoires sont beaucoup plus nombreuses que les propriétés étudiées pour les graphes temporels aléatoires. Plus récemment, Broutin et al. ont étudié le diamètre en termes de nombre de pas.

Une partie de la direction de recherche proposée consiste à étudier d'autres propriétés telles que, par exemple, la k-connexité, la distribution des degrés et la fréquence des petits sous-graphes. Le comportement des mesures structurelles telles que la largeur de l'arbre, la largeur du chemin ou le nombre chromatique pourrait également être intéressant.

Une autre question est similaire aux questions hors ligne et en ligne pour les graphes statiques : que pouvons-nous dire sur un graphe s'il nous est donné en une seule fois et que pouvons-nous dire sur le graphe si seulement une partie des arêtes est donnée. Par exemple, pour les graphes temporels aléatoires, nous disposons d'un ordre naturel de révélation des arêtes et nous pouvons donc poser des questions sur les distributions de certaines variables aléatoires conditionnelles aux arêtes déjà révélées. Par exemple, au lieu de demander la longueur d'une marche temporelle de A à B, nous pourrions nous intéresser à la distribution des distances attendues vers B conditionnellement aux arêtes révélées par un certain temps T.

Compétences requises

Une compétence incontournable, c'est la théorie (basique) de probabilités, compréhénsion d'indépendance dans le sens probabiliste et volonté de développer l'intuition sur l'indépendence approximative. Les directions à priviliger dans le projet ne vont pas utiliser de calcul fragile ou des outils probabilistes exotiques. La conaissance de théorie de graphes n'est pas demandé, mais peut être appliquée dans ce projet. Pareil pour la complexité algorithmique : cette connaissance n'est pas demandée, mais elle peut être appliqueée.

Bibliographie

Ruben Becker, Arnaud Casteigts, Pierluigi Crescenzi, Bojana Kodric, Malte Renken, Michael Raskin, Viktor Zamaraev. Giant Components in Random Temporal Graphs.

Nicolas Broutin, Nina Kamčev, Gábor Lugosi. Increasing Paths In Random Temporal Graphs. (preprint)

Sandeep Bhadra, Afonso Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks.

Richard T. Bumby. A Problem with Telephones.

Arnaud Casteigts, Michael Raskin, Malte Renken, Viktor Zamaraev. Sharp Thresholds in Random Simple Temporal Graphs.

Yves Mocquard, Bruno Sericola, Emmanuelle Anceaume. Probabilistic Analysis of Rumor-Spreading Time.

John W. Moon. Random exchanges of information.

Mots clés

Graphes temporels, Graphes aléatoires, Réseaux de transport, Diffusion d'information