Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
On s'intéresse dans ce manuscrit à des problèmes d'inférence dans des graphes aléatoires de grande taille. Dans un premier temps, on étudie le problème des arbres plantés, où un arbre de forme connue est "caché" dans un graphe d'Erdös-Rényi peu dense. Dans le cas où l'arbre est un chemin, on détermine l'intégralité du paysage de transition de phase, qui a une forme inhabituelle par rapport à d'autres problèmes proches.On s'intéresse ensuite à la détection de communautés, et plus précisément aux algorithmes spectraux pour cette tâche. Ces algorithmes sont connus pour être peu robustes à des faibles perturbations du graphe. Malgré cela, on introduit un nouvel algorithme spectral basé sur une matrice différente, et l'on montre que cet algorithme est bien moins sensible aux perturbations: on peut rajouter ou enlever jusqu'à une petite puissance de n arêtes sans que sa performance ne soit affectée.Dans un troisième temps, on étudie des variantes du problème de détection de communautés : avec une distribution de degrés prescrite, des arêtes dirigées ou encore des étiques sur des arêtes. Toutes ces variantes font partie d'un modèle extrêmement général, sur lequel on prouve des résultats spectraux précis concernant la matrice non-rebroussante. Cela permet de proposer un algorithme à la fois très général et très performant pour tous ces problèmes à la fois. ; This manuscript deals with inference problems on large, usually sparse, random graphs. We first focus on a planted tree problem, where a tree with known shape is planted inside a sparse Erdös-Rényi graph. When this tree is a path, we provide a complete characterization of the phase transition landscape, which differs from other related problems.We then move on to the problem of community detection, and the spectral algorithms designed to tackle this task. These algorithms are known for their sensitivity to adversarial noise in the graph. In contrast, we introduce a new spectral method based on a distance matrix and show that it performs equally well when the number ...