title

Generalized representation matrices, spectral measures and statistical distances for graph and signal analysis and classification

keywords

Representation matrices, similarity measures, visibility graphs, entropies, networks vulnerability

abstract

Graphs are mathematical objects that are well-suited to represent complex networks (energy supply infrastructures, land, air or sea routes, network of underwater communication cables, etc.), data from multiple sensors (hydrophone networks or sensor networks for environmental monitoring) and finally time series seen as graphs using the so-called visibility algorithm. These graphs are often studied using linear algebra tools such as representation matrices and their associated spectra. Different matrices exist, each with its own advantages and disadvantages. In this thesis, we construct a generalized bi-parameter representation matrix, denoted \(\mathbf{P}_{\alpha, k}\). The introduction of \(\mathbf{P}_{\alpha, k}~\) allows us to unify the theories and properties derived from those traditionally used, such as the adjacency matrix and the Laplacian one. This matrix also enables us to evaluate the evolution of spectra between these matrices, essential for the classification of graphs and signals seen as graphs, a field of application that is extremely promising in terms of both the diversity of input sources and the tasks to be accomplished: detection of magnetic anomalies, detection of epilepsy in EEG signals, determination of whether a protein is carcinogenic or not. To ensure this classification, it is necessary to have similarity measures between graphs that compare structural and/or spectral elements. Two new similarity measures have therefore been developed: the first calculates the correlation between the spectra of the generalized representation matrix mentioned above, and the second compares, using statistical distances, the degree distributions of horizontal visibility graphs. In addition to time series classification, visibility graphs are valuable tools for the analysis of signals such as stochastic processes like fBm or fGn. We have thus introduced a method for estimating the Hurst coefficient, a parameter characterizing these processes, based on the extraction of two information-theoretic quantities from the degree distributions of visibility graphs: one global, namely Shannon entropy, and the second local, namely Fisher information measure. Classifying graphs can also mean characterizing their potential vulnerabilities. To this end, we introduce a measure of edge vulnerability based on the relative variation of the von Neumann entropy (based on the density matrix of the graph and reflecting the information content of the underlying physical system) if this edge is disturbed or even removed. We use two approximations of the von Neumann entropy in order to drastically reduce computation time while keeping a reasonable error: one based on a Taylor series at an optimal point, and the second on an approximation of the eigenvalues of the density matrix of the perturbed graph.

thesis defence

Monday 28^th Avril 2025, 1:30 p.m., French Naval Academy, Lanvéoc, France

committee members

Pierre BORGNAT	DR CNRS	ENS Lyon, Laboratoire de Physique	Rapporteur
Nicolas TREMBLAY	CR CNRS	UGA, GIPSA-LAB	Rapporteur
Sophie ACHARD	DR CNRS	UGA, Laboratoire Jean Kuntzmann	Examinatrice
Marc BARTHELEMY	DR CNRS	CEA, Université Paris-Saclay, IPhT	Examinateur
Thierry CHONAVEL	Professeur	IMT Atlantique, Lab-STICC	Examinateur
Vincent GRIPON	Professeur	IMT Atlantique, Lab-STICC	Examinateur
Nicolas KERIVEN	CR CNRS	IRISA	Examinateur
Abdel-Ouahab BOUDRAA	PU	École Navale / ENSAM, IRENav	Directeur
Delphine DARÉ-EMZIVAT	MCF	École Navale / ENSAM, IRENav	Encadrante
Michel BERTHIER	PU	La Rochelle Université, Laboratoire MIA	Invité

manuscript