Pattern recognition in graphs: heuristic and applications
Reconnaissance de motifs dans des graphes : heuristique et applications
Résumé
The topic of this thesis is graph comparison. In the first part of this manuscript we propose several algorithms for finding similar patterns in large graphs. The second part of this thesis deals with the study of user file systems as the underlying data on which the initial pattern recognition methods were developed. We propose a stochastic model for random generation of trees, based on observations of the statistical study of real data. In the third part, we detail two adaptations of the algorithm for recognizing similar pattern in graphs to specific applications. The first one concerns the recognition of objects extracted from low resolution video for rough indexing. The second application has been developed to visualize software evolution.
Cette thèse s'inscrit dans la problématique de la comparaison de graphes. Nous proposons dans la première partie de ce manuscrit plusieurs algorithmes de recherche de motifs similaires dans de grands graphes. La seconde partie de cette thèse traite de l'étude des arborescences de fichiers, structure de données pour laquelle la méthode initiale de reconnaissance de motifs a été développée. Nous présentons un modèle stochastique pour la génération aléatoire de structure arborescentes, basé sur les observations de l'étude statistique des données réelles. Enfin, nous détaillons deux adaptations de l'algorithme de reconnaissance de motifs similaires à des applications particulières. La première concerne la reconnaissance d'objets extraits de la video basse résolution pour l'indexation grossière. La deuxième application a été développée pour la visualisation de l'évolution de projets logiciels.