Estimer des paramètres de graphes par des marches aléatoires

Jeudi 21 février 14:00-15:00 - Anna Ben-Hamou - LPSM

Résumé : L’inférence statistique sur les graphes est devenue un enjeu crucial à une époque où quantités d’informations proviennent de réseaux dont la taille ne cesse de croître. La recherche d’informations sur de tels réseaux peut devenir très difficile, et les méthodes déterministes, comme les parcours en longueur ou en profondeur, s’avèrent souvent bien trop coûteuses en temps. L’enjeu devient alors de savoir s’il est possible d’élaborer des procédures d’exploration aléatoires permettant d’extraire des informations sur le graphe en un temps relativement court. Dans cet exposé, nous considérerons une procédure d’exploration fondée sur des marches aléatoires indépendantes parties d’un même sommet et construirons des estimateurs optimaux pour le nombre de sommets, le nombre d’arêtes, ainsi que pour le temps de mélange de la marche aléatoire. Il s’agit d’un travail effectué en collaboration avec Roberto Oliveira et Yuval Peres.

Estimer des paramètres de graphes par des marches aléatoires  Version PDF