Skip to Main content Skip to Navigation

Classification of signals and graphs by algebraic spectral approaches

Abstract : 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.
Complete list of metadata
Contributor : ABES STAR :  Contact
Submitted on : Tuesday, May 17, 2022 - 10:20:15 AM
Last modification on : Wednesday, May 18, 2022 - 3:44:02 AM


Version validated by the jury (STAR)


  • HAL Id : tel-03669985, version 1


Hadj Ahmed Bay-Ahmed. Classification of signals and graphs by algebraic spectral approaches. Signal and Image processing. Université de Bretagne occidentale - Brest, 2018. English. ⟨NNT : 2018BRES0107⟩. ⟨tel-03669985⟩



Record views


Files downloads