Cette thèse est décomposée en trois parties disjointes. Les deux premières parties se concentrent sur des modèles de graphes aléatoires croissants de manière dynamique.

 

Dans la première partie, nous inférons des informations sur le passé d'un graphe à partir d'une unique observation dudit graphe. Nous commençons par le problème de la recherche de racine, où l'objectif est de trouver un ensemble de confiance pour la racine. Nous proposons une méthode pour les $ell$-{sc dags} uniformes et analysons ses performances. À notre connaissance, il s'agit de la première méthode réalisant une archéologie du graphe dans des graphes généraux. Nous étendons ensuite naturellement la question de la recherche de racine à celle de la sériation. Étant donné un instantané d'un graphe, est-il possible de récupérer son ordre complet ? Nous présentons une méthode et une garantie statistique sur sa qualité dans le cas des arbres récursifs uniformes et des arbres d'attachement préférentiel linéaire. Pour conclure la section sur l'archéologie de graphe, nous étudions un problème de broadcasting, où l'on ne tente pas de retrouver la racine du graphe mais son état. Dans de tels problèmes, la racine se voit attribuer un bit, qui est ensuite propagé de manière bruité lors de la croissance du réseau. Dans les $ell$-{sc dags}, nous étudions un vote par majorité pour estimer le bit de la racine et identifions trois régimes, dépendants du niveau de bruit.

 

Dans la deuxième partie, nous étudions l'arbre d'amitié aléatoire, qui est un modèle d'arbre récursif aléatoire avec redirection complète. Dans ce modèle apparaît un phénomène de rich-get-richer, mais à la différence du modèle d'attachement préférentiel celui ci découle d'un processus d'attachement local. Nous prouvons des conjectures sur la distribution des degrés, le diamètre et la structure locale.

 

Enfin, nous plongeons dans le monde de l'apprentissage automatique théorique et de l'analyse de données. Nous étudions une approximation aléatoire de la profondeur de Tukey. La profondeur de Tukey est un outil puissant pour la visualisation des données et peut être considérée comme une extension des quantiles en dimension plus élevée (ils coïncident en dimension $1$). Son calcul exact est NP-difficile, et nous étudions les performances d'une approximation aléatoire dans le cas de données échantillonnées à partir d'une distribution log-concave.