• français
    • English
    français
  • Login
Help
View Item 
  •   Home
  • Institut de Recherche de l’École navale (IRENAV)
  • View Item
  • Home
  • Institut de Recherche de l’École navale (IRENAV)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Sur la similarité spectrale des graphes par mesure de corrélation

Communication avec acte
Author
AVERTY, Tristan
13094 Institut de Recherche de l'Ecole Navale [IRENAV]
DARE-EMZIVAT, Delphine
13094 Institut de Recherche de l'Ecole Navale [IRENAV]
ccBOUDRAA, Abdel-Ouahab
13094 Institut de Recherche de l'Ecole Navale [IRENAV]

URI
http://hdl.handle.net/10985/24102
Date
2023-09

Abstract

In this paper, we present a spectral similarity measure between two graphs based on a correlation measure between the spectra of their representation matrices Tα := αD+(1−2α)A, parametrized by 0 ≤ α ≤ 1, where A and D are respectively the adjacency matrix and the degree matrix. We also show that Tα is positive semidefinite for α ≥ 1/2. This work tends to show the relevance of this measure, which, when a SVM is implemented using a Gaussian kernel, allows a powerful classification on well known graph databases of the literature and classification of real signals transformed into a graph thanks to the so-called visibility method. The obtained results in terms of accuracy are similar or even better than those obtained with structural kernels with a much lower computation time and this, by computing only one spectrum for each graph. Moreover, we show the contribution of Tα compared to the α-adjacency matrix of Nikiforov for graph classification.
 
Dans cet article, nous présentons une mesure de similarité spectrale entre deux graphes basée sur un calcul de corrélation entre les spectres de leurs matrices de représentation Tα := αD + (1 − 2α)A, paramétrée par 0 ≤ α ≤ 1, où A et D sont respectivement la matrice d’adjacence et la matrice des degrés. Nous montrons par ailleurs que Tα est semi-définie positive pour α ≥ 1/2. Ce travail tend à montrer la pertinence de cette mesure, qui, introduit dans un noyau de type Gaussien d’un SVM permet une classification performante de bases de données de graphes connues de la littérature et de classification de signaux réels transformés en graphe grâce à la méthode dite de visibilité. Les résultats obtenus en termes de mesure d’exactitude sont similaires voire meilleurs à ceux obtenus avec des noyaux structurels pour un temps de calcul bien moindre et ce, en ne calculant qu’un seul spectre pour chaque graphe. De plus, nous montrons l’apport de Tα par rapport à la matrice d’α-adjacence de Nikiforov pour la classification de graphes.
 

Files in this item

Name:
IRENAV_Gretsi_2023_AVERTY.pdf
Size:
788.6Kb
Format:
PDF
Description:
Version finale
View/Open

Collections

  • Institut de Recherche de l’École navale (IRENAV)

Related items

Showing items related by title, author, creator and subject.

  • Détection d’épilepsie dans les signaux EEG par graphe de visibilité et un noyau de SVM adapté 
    Communication avec acte
    AVERTY, Tristan; DARE-EMZIVAT, Delphine; ccBOUDRAA, Abdel-Ouahab (GRETSI, 2022-09)
    Dans cet article, nous présentons une stratégie de détection d’épilepsie à partir de signaux EEG (issus d’un seul capteur) basée sur l’algorithme de visibilité, qui consiste à transformer une série temporelle en un graphe ...
  • Approximation de l’entropie de von Neumann de graphes pour une analyse de vulnérabilité 
    Communication avec acte
    AVERTY, Tristan; DARE-EMZIVAT, Delphine; ccBOUDRAA, Abdel-Ouahab; PREAUX, Yves (Gretsi, 2022)
    Dans ce travail, nous exploitons la variation de l’entropie de von Neumann de graphes comme mesure de vulnérabilité en proposant une nouvelle forme approchée de cette entropie basée sur des attributs structurels du graphe, ...
  • On signal denoising by EMD in the frequency domain 
    Communication avec acte
    BAY-AHMED, Hadj-Ahmed; KOMATY, Ali; DARE-EMZIVAT, Delphine; ccBOUDRAA, Abdel-Ouahab (2015)
    In this work a new denoising scheme based on the empirical mode decomposition associated with a frequency analysis is introduced. Compared to classical approaches where the extracted modes are thresholded in time domain, ...
  • Débruitage fréquentiel de signaux par EMD 
    Communication avec acte
    KOMATY, Ali; DARE-EMZIVAT, Delphine; ccBOUDRAA, Abdel-Ouahab (2013)
    Dans cet article, nous proposons un nouveau schéma de débruitage des signaux basé sur la décomposition modale empirique associée à une analyse fréquentielle. Le principe de l’approche consiste à seuiller les modes extraits ...
  • A Joint Spectral Similarity Measure for Graphs Classification 
    Article dans une revue avec comité de lecture
    BAY-AHMED, Hadj-Ahmed; ccBOUDRAA, Abdel-Ouahab; DARE-EMZIVAT, Delphine (Elsevier, 2019)
    In spite of the simple linear relationship between the adjacency A and the Laplacian L matrices, L=D-A where D is the degrees matrix, these matrices seem to reveal informations about the graph in different ways, where it ...

Browse

All SAMCommunities & CollectionsAuthorsIssue DateCenter / InstitutionThis CollectionAuthorsIssue DateCenter / Institution

Newsletter

Latest newsletterPrevious newsletters

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors

ÉCOLE NATIONALE SUPERIEURE D'ARTS ET METIERS

  • Contact
  • Mentions légales

ÉCOLE NATIONALE SUPERIEURE D'ARTS ET METIERS

  • Contact
  • Mentions légales