⚡ electrical engineering

Sample entropy for graph signals: An approach to nonlinear analysis of graph signals

Cet article présente SampEn $_{G}$ , une généralisation de l'entropie d'échantillonnage aux signaux graphiques qui quantifie leur irrégularité en remplaçant l'encodage temporel par une intégration multi-sauts basée sur les opérateurs de décalage du graphe, validée empiriquement sur divers réseaux et dynamiques non linéaires.

Auteurs originaux : Mei-San Maggie Lei, John Stewart Fabila Carrasco, Javier Escudero

Publié 2026-04-23

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Mei-San Maggie Lei, John Stewart Fabila Carrasco, Javier Escudero

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🌐 Le Concept de Base : Mesurer le "Désordre" sur une Carte

Imaginez que vous essayez de comprendre si une ville est organisée ou chaotique.

L'approche classique (SampEn) : Traditionnellement, les scientifiques analysent une seule ligne de temps, comme une file d'attente unique. Ils regardent si les gens qui arrivent maintenant ressemblent à ceux qui étaient là il y a un instant. C'est comme lire une histoire ligne par ligne.
Le problème : Aujourd'hui, beaucoup de données ne sont pas des lignes droites. Elles sont des réseaux (comme les réseaux sociaux, les neurones du cerveau, ou les routes d'une ville). Dans un réseau, l'information ne va pas seulement "d'avant en arrière", elle saute d'un point à un autre, comme une rumeur qui se propage de voisin en voisin.

Les méthodes actuelles pour analyser ces réseaux sont un peu "brutes" : elles transforment les données en symboles (comme changer des mots en lettres A, B, C), ce qui fait perdre beaucoup de détails fins.

🚀 La Solution : SampEnG (L'Enquêteur à Multiples Sauts)

Les auteurs (Maggie Lei et son équipe) ont créé une nouvelle méthode appelée SampEnG. Imaginez-la comme un détective très intelligent qui ne se contente pas de regarder le voisin immédiat, mais qui regarde tout le quartier.

Voici comment cela fonctionne avec une analogie simple :

1. Le "Saut" au lieu du "Pas"

Dans une file d'attente classique, on regarde ce qui se passe à l'instant $t$ et $t+1$ .
Dans un réseau, le détective SampEnG utilise le concept de "saut" (hop).

1er saut : Il regarde le signal direct sur un nœud (une personne, un capteur).
2ème saut : Il regarde ce qui se passe chez les amis directs de cette personne.
3ème saut : Il regarde ce qui se passe chez les amis de ses amis.

Au lieu de faire une ligne droite, il crée une "boule de neige" d'information autour de chaque point. Plus il saute loin, plus il voit le contexte global.

2. La Recette de la "Soupe de Voisins"

Pour chaque point du réseau, le détective prépare une "soupe" (une moyenne pondérée) :

Il prend la valeur du point lui-même.
Il ajoute la valeur moyenne de ses voisins directs.
Il ajoute la valeur moyenne des voisins des voisins.

Il crée ainsi un profil unique pour chaque point du réseau, basé sur son environnement immédiat et lointain.

3. Le Test de Similitude (Le Jeu des "Qui ressemble à qui ?")

Une fois qu'il a ces profils pour tout le monde, il pose la question : "Si je compare le profil d'aujourd'hui avec celui de demain (ou d'un autre point), est-ce qu'ils se ressemblent ?"

Si les profils restent très similaires quand on ajoute un peu plus de contexte (un saut de plus), c'est que le système est prévisible et ordonné (comme une ville très structurée).
Si les profils deviennent soudainement très différents et imprévisibles, c'est que le système est chaotique et complexe (comme une foule en panique).

🧪 Ce qu'ils ont découvert (Les Résultats)

Les chercheurs ont testé leur méthode avec deux expériences amusantes :

Le Test de la "Machine à Chaos" (Logistic Map) :
Ils ont utilisé un modèle mathématique célèbre qui passe de l'ordre au chaos.
- Résultat : Quand ils ont appliqué leur méthode sur un réseau qui ressemble à une simple file d'attente (un chemin), leur méthode a donné exactement les mêmes résultats que les anciennes méthodes. C'est comme si leur nouvelle voiture roulait aussi bien que l'ancienne sur une route droite, mais qu'elle pouvait aussi traverser des montagnes !
Le Test des "Réseaux Aléatoires" (Graphes Erdős–Rényi) :
Ils ont créé des réseaux où les connexions entre les points étaient aléatoires, un peu comme un réseau social où les gens se suivent au hasard.
- Ce qu'ils ont vu : Plus le réseau était dense (beaucoup de connexions, beaucoup de "amis" communs), plus la méthode détectait que le système devenait prévisible (le désordre apparent diminue car tout le monde se ressemble).
- Vitesse : C'est rapide ! Ils ont pu analyser un réseau de 2 700 points en moins de 1,5 seconde sur un ordinateur portable standard.

💡 Pourquoi c'est important ?

Imaginez que vous voulez analyser :

La propagation d'une épidémie dans une ville.
L'activité électrique d'un cerveau (où les neurones sont connectés en 3D, pas en ligne).
Les fluctuations boursières interconnectées.

Avec SampEnG, vous ne regardez plus juste une ligne droite. Vous comprenez la structure du réseau lui-même. Vous pouvez dire : "Ce système est chaotique non pas parce que les données sont bruyantes, mais parce que la structure du réseau permet trop de mélanges."

En résumé : Les auteurs ont inventé une nouvelle "loupe" qui permet de mesurer le désordre non pas dans une file d'attente, mais dans un réseau complexe, en regardant comment l'information se propage de proche en proche, comme une rumeur qui traverse une ville.

1. Problématique et Contexte

Le traitement du signal sur les graphes (GSP) a vu le développement de plusieurs méthodes d'entropie basées sur la dynamique symbolique, telles que l'entropie de permutation, l'entropie de dispersion et l'entropie à bulles. Bien que efficaces, ces méthodes présentent une limitation majeure : elles nécessitent une discrétisation du signal pour calculer l'entropie de Shannon, ce qui les restreint à une analyse de dynamique symbolique et perd l'information contenue dans l'espace d'état continu.

Parallèlement, l'Entropie d'Échantillonnage (Sample Entropy ou SampEn) est une méthode éprouvée pour quantifier l'irrégularité et la complexité des séries temporelles dans un espace d'état continu. Elle estime la probabilité de récurrence conditionnelle sans nécessiter de seuil fixe arbitraire (bien qu'un seuil $\epsilon$ soit utilisé), en mesurant la similarité des motifs de longueur $m$ lorsqu'ils sont étendus à $m+1$ . Cependant, jusqu'à présent, il n'existait pas de généralisation directe de la SampEn pour les signaux définis sur des graphes, capable de préserver la nature continue du signal tout en tenant compte de la topologie du réseau.

2. Méthodologie : SampEnG

Les auteurs proposent SampEnG, une généralisation de l'entropie d'échantillonnage adaptée aux signaux de graphes. L'approche repose sur le remplacement de l'encodage temporel par un encodage basé sur les sauts de graphe (graph hops).

A. Construction des motifs (Patterns)

Pour un graphe $G = (N, E, A)$ , au lieu d'empiler des observations temporelles successives, SampEnG agrège des informations provenant des voisinages locaux pondérés par les marches aléatoires :

Définition du saut : Un "pas" temporel est remplacé par un "saut" de graphe (traverser une arête).
Opérateur de décalage : Les voisinages sont explorés via les puissances de l'opérateur de décalage du graphe (la matrice d'adjacence $A$ ). La matrice $A^L$ représente le nombre de marches de longueur $L$ entre deux nœuds.
Moyenne pondérée par la marche : Pour chaque nœud $i$ et chaque rayon de saut $L$ , une composante $x_i^L$ est calculée comme la moyenne pondérée des valeurs du signal des nœuds situés exactement à $L$ sauts de distance.
$x_i^L = \frac{1}{\text{deg}_L(i)} \sum_{j \in N_L(i)} (A^L)_{ij} x_j$
où $\text{deg}_L(i)$ est le degré de marche de longueur $L$ .
Vecteurs de motifs : Pour un nœud $i$ , on construit un vecteur de dimension $m$ (motif $x^m(i)$ ) et un vecteur de dimension $m+1$ (motif $x^{m+1}(i)$ ) en concaténant ces moyennes locales pour $L=0$ à $m-1$ (ou $m$ ).

B. Calcul de l'Entropie

Le calcul suit la logique classique de la SampEn :

Comptage des similarités : On compte le nombre de paires de motifs $(i, j)$ dont la distance de Chebyshev est inférieure à un seuil $\epsilon = r \times \sigma$ (où $\sigma$ est l'écart-type du signal).
Probabilités conditionnelles : On calcule le rapport entre le nombre de paires similaires pour les motifs de longueur $m+1$ ( $A_m$ ) et ceux de longueur $m$ ( $B_m$ ).
Formule finale :
$\text{SampEnG}(m, r, N) = -\ln \left( \frac{A_m(r)}{B_m(r)} \right)$
Une valeur élevée indique une forte irrégularité (complexité), tandis qu'une valeur faible indique une régularité ou une prévisibilité.

3. Contributions Clés

Généralisation continue : SampEnG permet d'analyser l'irrégularité des signaux de graphes dans un espace d'état continu, évitant ainsi les pertes d'information liées à la discrétisation requise par les méthodes symboliques existantes.
Encodage topologique : L'introduction d'une embedding multi-sauts basée sur les puissances de la matrice d'adjacence permet de capturer la structure radiale du signal autour de chaque nœud, adaptée à la connectivité du graphe.
Réduction à la 1D : La méthode est conçue pour se réduire mathématiquement et empiriquement à la SampEn classique lorsque le graphe est un chemin dirigé (série temporelle).

4. Résultats Expérimentaux

A. Validation sur la Carte Logistique

Les auteurs ont testé SampEnG sur la carte logistique ( $x_{t+1} = \rho x_t(1-x_t)$ ), un modèle dynamique non linéaire connu pour ses transitions ordre-chaos.

Graphes dirigés (chemins) : SampEnG reproduit fidèlement la courbe de la SampEn 1D classique en fonction du paramètre de bifurcation $\rho$ , confirmant la validité de la généralisation.
Graphes non dirigés : La méthode suit la tendance globale et identifie correctement les points de bifurcation et les îlots de périodicité, bien que des différences quantitatives mineures apparaissent dues à la structure de voisinage symétrique et non causale.

B. Analyse sur des Graphes d'Erdős–Rényi (ER)

Des expériences ont été menées sur des graphes aléatoires dirigés ( $N=2700$ ) avec des valeurs de nœuds aléatoires.

Impact de la connectivité : Pour des réseaux clairsemés (faible degré moyen $K$ ), SampEnG diminue à mesure que la connectivité augmente, reflétant une régularité accrue de la topologie.
Effet de la densité et de la longueur du motif ( $m$ ) : À mesure que les graphes deviennent plus denses et que la longueur du motif $m$ augmente, les voisinages locaux se chevauchent davantage, homogénéisant les motifs. Cela entraîne une chute de SampEnG vers zéro, indiquant une perte de variabilité exploitable.
Performance computationnelle : La méthode est praticable pour des graphes de taille moyenne. Sur un processeur Apple M3, le traitement d'un graphe de 2700 nœuds prend environ 295 ms pour $m=1$ et 1400 ms pour $m=3$ .

5. Signification et Perspectives

SampEnG représente une avancée significative pour l'analyse non linéaire des données de réseaux.

Nouveaux horizons : Elle ouvre la voie à l'application de l'entropie conditionnelle et de l'analyse de complexité à une vaste gamme de données de réseaux (capteurs, biologie, réseaux sociaux) sans imposer de discrétisation brutale.
Robustesse : La capacité à gérer des signaux continus sur des topologies complexes permet une meilleure caractérisation des dynamiques non linéaires dans les systèmes interconnectés.
Travaux futurs : Les auteurs envisagent d'explorer d'autres embeddings de graphes, d'améliorer la robustesse au bruit et d'appliquer cette méthode à des domaines de détection en réseau réels.

En résumé, ce travail comble un vide théorique en étendant un outil puissant d'analyse de séries temporelles (SampEn) au domaine des graphes, tout en maintenant une efficacité computationnelle acceptable pour des applications pratiques.