Braun, Guillaume
[Author]
;
Université de Lille (2022-.)
[Contributor];
Biernacki, Christophe
[Contributor]
Efficient iterative methods for clustering and matching problems on graphs ; Méthodes itératives efficientes pour des problèmes de classification et d'appariement de graphes
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Electronic Thesis;
E-Book;
Text
Title:
Efficient iterative methods for clustering and matching problems on graphs ; Méthodes itératives efficientes pour des problèmes de classification et d'appariement de graphes
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Des données structurées sous forme de graphe apparaissent naturellement dans de nombreux domaines comme la biologie avec les réseaux d'interaction protéine-protéine, l'écologie avec les réseaux proie-prédateur ou l'économie avec les réseaux financiers. Afin d'extraire une information pertinente de ces réseaux, on a souvent recours à des méthodes de classification qui regroupent entre eux les nœuds ayant un profil de connectivité similaire. Durant les vingt dernières années, de nombreux algorithmes de classification ont été proposés et analysés lorsque le graphe est généré par un modèle à blocs stochastiques (SBM). Mais en pratique, on a souvent accès à de l'information auxiliaire. Il n'est toutefois pas bien compris comment cette information auxiliaire peut-être incorporée par les méthodes existantes, et dans quelle mesure elle peut aider à améliorer les résultats de la classification.Dans un premier temps nous allons résoudre ce problème en s'appuyant sur un modèle génératif simple - le modèle à blocs stochastiques contextuel (CSBM) - qui ajoute à chaque nœud d'un graphe généré par un SBM des covariables gaussiennes. Nous proposons une méthode itérative rapide qui atteint le seuil théorique d'information pour le recouvrement exact des communautés latentes. Notre méthode s'inspire de la méthode de la puissance généralisée (GPM) ainsi que des algorithmes de type EM.Nous étendons ensuite la méthode à des graphes ayant des nœuds avec des degrés hétérogènes ou appartenant à plusieurs communautés, ainsi qu'à des covariables de différentes natures, comme par exemple des réseaux multicouches avec des valeurs manquantes ou des graphes bipartites en grande dimension.Enfin, nous considérons le problème d'appariement de graphes dans lequel le graphe additionnel peut être considéré comme de l'information auxiliaire corrélée. Nous montrons que l'on peut également utiliser une stratégie basée sur GPM pour améliorer de manière significative un appariement initial imparfait. Nous établissons des garanties de consistance de ...