Classification of signals and graphs by algebraic spectral approaches

De nos jours, le développement de l’instrumentation électronique, de l’informatique et des systèmes de communications conduit à une collecte de données réalisée à partir de réseaux de capteurs (réseau de bouées acoustiques en mer, capteurs de température des stations météorologiques, capteurs de surveillance des niveaux de pollution et de bruit ...). La complexité de ces réseaux de capteurs et leur interaction font que ces données sont portées par des structures complexes et irrégulières qui ne peuvent être traitées efficacement par les outils standards. Les graphes constituent un modèle mathématique pour la représentation de telles données en tenant compte de leur complexité. L’objectif principal de ce travail de thèse est d’étudier la question de la pertinence de cette représentation en se focalisant sur l’interaction données-structure d’une part, et d'autre part sur la modélisation matricielle de la structure du graphe portant ces données. Ces questions sont traitées dans le cadre de la classification des signaux et des graphes en utilisant des outils de la théorie spectrale des graphes. De nouvelles mesures de similarités spectrales entre graphes ont été proposées et testées sur des données synthétiques et réelles donnant de bons résultats en termes de temps de calculs et de taux de bonne classification par rapport à l’état de l’art. Malgré la simple relation linéaire associant les matrices Laplacienne et d’adjacence, les résultats obtenus mettent en évidence le fait que ces matrices expriment différemment l’information structurelle du graphe. Cette différence de représentation a été analysée et illustrée via des mesures de complexité et de connectivité à partir du graphe associé, ainsi qu’en mesurant la déviation de l’entropie de Von Neumann du graphe, considéré alors comme un système quantique. Dans le cadre de la représentation et de l’analyse spectrale des graphes, nous nous sommes intéressés au cas particulier des graphes co-spectraux, graphes partageant le même spectre. De plus, en considérant la théorie de la décomposition en matrices de rang faible, l’analyse en graphe propre dominant, appelé DGA (pour Dominant eigenGraph Analysis), a été introduite et illustrée par la décomposition multi-échelle de la structure du graphe. En utilisant une reconstruction partielle de la matrice d’adjacence par ses graphes propres, une stratégie facilitant la détection de communautés au sein d’un graphe a été proposée. Concernant la représentation quantique du graphe, nous avons exploité l’entropie de Von Neumann pour mesurer la vulnérabilité du graphe aux perturbations structurelles. Un nouvel algorithme de pondération des connections a été ainsi proposé.Nowadays, the development of electronic instrumentation, data Processing and communications Systems leads to a collection of data carried out from networks of sensors (network of acoustic buoys at sea, température sensors of meteorological stations, sensors monitoring pollution and noise levels, etc.). The complexity of these sensor networks and their interaction mean that these data are carried by complex and irregular structures which cannot be processed efficiently by standard tools. The graphs constitute a mathematical model for the représentation of such data taking into account their complexity. The main objective of this thesis is to study the question of the relevance of this représentation by focusing on the data-structure interaction on the one hand, and on the other hand on the matrix modeling of the structure of the graph. carrying this data. These questions are addressed within the framework of the classification of signais and graphs using tools of spectral graph theory. New measurements of spectral similarities between graphs hâve been proposed and tested on synthetic and real data giving good results in terms of calculation time and good classification rate compared to the State of the art. Despite the simple linear relationship between the Laplacian and adjacency matrices, the results obtained highlight the fact that these matrices express the structural information of the graph differently. This différence in représentation was analysed and illustrated by measuring the complexity and connectivity of the associated graph, as well as by measuring the déviation of the Von Neumann entropy of the graph, which was then considered as a quantum System. In the context of the représentation and spectral analysis of graphs, we are interested in the particular case of co-spectral graphs, graphs sharing the same spectrum. Moreover, considering the theory of low rank matrix décomposition, the dominant eigengraph analysis, called DGA (for Dominant eigenGraph Analysis), has been introduced and illustrated by the multi-scale décomposition of the graph structure. Using a partial reconstruction of the adjacency matrix by its eigengraphs, a strategy facilitating the détection of communities within a graph was proposed. Concerning the quantum représentation of the graph, we exploited the Von Neumann entropy to measure the vulnerability of the graph to structural perturbations. A new algorithm of connection weighting has been proposed