Métrologie des graphes de terrain, application à la construction de ressources lexicales et à la recherche d'information

Cette these s'organise en deux parties : une premiere partie s'interesse aux mesures de similarite entre sommets d'un graphe, une seconde aux methodes de clustering de graphe biparti. Une nouvelle mesure de similarite entre sommets basee sur des marches aleatoires en temps courts est introduite. Cette methode a l'avantage, en particulier, d'etre insensible a la densite du graphe. Il est ensuite propose un large etat de l'art des similarites entre sommets, ainsi qu'une comparaison experimentale de ces differentes mesures. Cette premiere partie se poursuit par la proposition d'une methode robuste de comparaison de graphes partageant le meme ensemble de sommets. Cette mesure est mise en application pour comparer et fusionner des graphes de synonymie. Enfin une application d'aide a la construction de ressources lexicales est presentee. Elle consiste a proposer de nouvelles relations de synonymie a partir de l'ensemble des relations de synonymie deja existantes. Dans une seconde partie, un parallele entre l'analyse formelle de concepts et le clustering de graphe biparti est etabli. Ce parallele conduit a l'etude d'un cas particulier pour lequel une partition d’un des groupes de sommets d’un graphe biparti peut-etre determinee alors qu'il n'existe pas de partitionnement correspondant sur l’autre type de sommets. Une methode simple qui repond a ce probleme est proposee et evaluee. Enfin Kodex, un systeme de classification automatique des resultats d'une recherche d'information est presente. Ce systeme est une application en RI des methodes de clustering vues precedemment. Une evaluation sur une collection de deux millions de pages web montre les avantages de l'approche et permet en outre de mieux comprendre certaines differences entre methodes de clustering.