Les graphes sont des structures mathématiques constituées de sommets et d'arêtes représentant les liens ou connexions entre les sommets du graphe. A cause de leurs puissantes propriétés, les graphes sont utilisés pour modéliser les données dans de nombreux applications du monde réel : sociologie, transport, réseaux informatiques, biologie, chimio-informatique et traitement d'images. Dans beaucoup de ces applications, il y a un besoin crucial d'une mesure quantitative précise et rapide représentant la similarité entre les graphes. Cependant, le calcul d'une telle similarité entre deux graphes dans des temps réduits est un problème difficile pour deux principales raisons. Premièrement, la taille et le nombre de graphes augmentent de manière exponentielle et continue, et il est de plus en plus courant de trouver de grands graphes partout. Deuxièmement, avec l'apparition des graphes dynamiques dans plusieurs applications du monde réel, le nombre de comparaisons requises à effectuer entre les graphes a considérablement augmenté.  Dans cette thèse, nous étudions les différentes stratégies et mécanismes qui permettent d'accélérer et de simplifier la comparaison de graphes dans différents domaines d’application. L'objectif principal est de proposer de nouvelles représentations et mesures de similarité entre les graphes qui s'appliquent aux grands graphes. Les stratégies et mécanismes étudiés sont : la comparaison de graphes dans le modèle de flux de données, la décomposition de grands graphes pour pouvoir les comparer, la simplification des graphes par compression, échantillonnage ou plongement de graphes. Les fruits de cette thèse sont 3 contributions différentes, chacune utilise un mécanisme de simplification de la comparaison de graphes. La première, consiste en une nouvelle approche rapide de comparaison de graphes appliquée au problème de la détection d'anomalies dans un flux d'arêtes provenant de différents graphes. Cette approche est basée sur un algorithme de clustering de graphes qui utilise un plongement incrémental de graphes afin de les comparer dans le modèle de flux. Le plongement utilisé est basé sur la décomposition de graphes en sous-structures et sur la distance d'édition de graphes. Le principal avantage de cette approche est qu'elle est rapide et permet de mettre à jour de manière incrémentale et rapide les vecteurs de graphes dans le modèle de streaming. Dans notre deuxième contribution, nous proposons une nouvelle mesure de dissimilarité pour les graphes géométriques appliquée au problème de la reconnaissance des formes en 2D. La mesure de dissimilarité proposée est une distance qui s'appuie sur le mécanisme de sparsification de graphes et sur un nouveau plongement de nœuds qui capture le voisinage topologique. Le rôle du mécanisme de sparsification est de réduire le nombre de nœuds dans les graphes géométriques et ainsi réduire le temps de comparaison total. Notre troisième contribution est une nouvelle méthode de compression pour les grands graphes qui préserve une proportion des voisins de chaque nœud du graphe.  L'objectif principal de ce travail est de simplifier les grands graphes tout en préservant autant de propriétés de voisinage des sommets que possible afin d'accélérer le temps de comparaison des graphes.

Les différents tests et expérimentations de nos 3 approches réalisés sur différents jeux de données issus de nombreuses applications montrent l'efficacité des mécanismes employés pour accélérer et simplifier la comparaison de graphes.