Classification of signals and graphs by algebraic spectral approaches

Overview & Synopsis

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.