⚡ electrical engineering

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

Diese Arbeit stellt SampEn $_{G}$ vor, eine Verallgemeinerung der Sample-Entropie für Graphensignale, die durch den Ersatz der zeitlichen Verzögerungseinbettung durch eine multihop-basierte Graph-Einbettung die Irregularität von Signalen auf Graphen quantifiziert und damit nichtlineare Analysen auf Netzwerkdaten erweitert.

Ursprüngliche Autoren: Mei-San Maggie Lei, John Stewart Fabila Carrasco, Javier Escudero

Veröffentlicht 2026-04-23

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Mei-San Maggie Lei, John Stewart Fabila Carrasco, Javier Escudero

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Ein neuer Kompass für Netzwerke

Stellen Sie sich vor, Sie haben ein riesiges Netzwerk aus Menschen, Sensoren oder Computern, die alle miteinander verbunden sind (wie ein soziales Netzwerk oder ein Stromnetz). Jeder Knoten in diesem Netz hat eine Information (z. B. eine Temperatur, eine Meinung oder ein Aktienkurs).

Bisher gab es Methoden, um zu messen, wie chaotisch oder unvorhersehbar diese Informationen sind. Aber die meisten dieser Methoden funktionierten nur, wenn die Daten wie eine einfache Liste von Zahlen kamen (eine Zeitleiste). Was aber, wenn die Daten in einem komplexen Netz mit vielen Verbindungen stecken?

Die Autoren dieses Papers haben eine neue Methode erfunden, die sie SampEnG nennen. Man kann sich das wie einen „Unordnungsmesser für Netzwerke" vorstellen.

Wie funktioniert das? (Die Analogie der Wanderer)

Um zu verstehen, wie SampEnG funktioniert, stellen wir uns das Netzwerk als eine Stadt mit vielen Straßen vor.

1. Der alte Weg (Zeit):
Bei normalen Daten (wie einer Uhrzeit) schauen wir uns an: „Was ist passiert, und was passiert eine Sekunde später?" Wir vergleichen Muster, die nacheinander kommen.

2. Der neue Weg (Das Netz):
Bei SampEnG schauen wir nicht auf die Zeit, sondern auf die Nachbarschaft.
Stellen Sie sich vor, Sie stehen an einem Kreuzungspunkt (einem Knoten).

Schritt 1: Sie schauen sich an, was direkt an Ihrer Kreuzung passiert (Ihr eigener Wert).
Schritt 2: Sie schauen sich an, was bei Ihren direkten Nachbarn passiert (1 Schritt entfernt).
Schritt 3: Sie schauen sich an, was bei den Nachbarn Ihrer Nachbarn passiert (2 Schritte entfernt).

Das ist wie ein Wanderer, der sich immer weiter von seinem Startpunkt entfernt. SampEnG sammelt diese Informationen aus immer weiter entfernten Nachbarschaften ein, um ein „Profil" oder ein „Muster" für jeden Punkt im Netz zu erstellen.

3. Der Vergleich:
Jetzt nimmt das Programm diese Muster und vergleicht sie.

Frage: „Wenn ich mir das Muster von Punkt A ansehe, sieht das Muster von Punkt B ähnlich aus?"
Das Ziel: Wenn das Netz sehr regelmäßig ist (wie ein gut geölter Uhrwerk), sehen sich alle Muster sehr ähnlich. Das bedeutet: Wenig Unordnung (niedriger Wert).
Wenn das Netz chaotisch ist (wie ein wilder Markt), sind die Muster alle unterschiedlich. Das bedeutet: Hohe Unordnung (hoher Wert).

Was haben die Forscher herausgefunden?

Sie haben ihre neue Methode an zwei verschiedenen „Testfeldern" ausprobiert:

1. Der Test mit dem „Logistischen Map" (Ein chaotischer Tanz)
Stellen Sie sich einen Tänzer vor, der zwischen einem geordneten Walzer und einem wilden, chaotischen Tanzwechseln kann.

Die Forscher haben gezeigt, dass ihr neuer Kompass (SampEnG) genau dasselbe misst wie die alten Kompass-Modelle, wenn das Netz nur eine einfache gerade Linie ist (wie eine Kette von Menschen).
Aber: Es funktioniert auch, wenn die Tänzer in einem Kreis stehen oder in einem komplexen Netz verbunden sind. Es erkennt genau, wann der Tanz vom geordneten Walzer in den chaotischen Tanz übergeht.

2. Der Test mit dem „Erdős-Rényi-Netz" (Ein zufälliges Straßennetz)
Hier haben sie ein Netz mit 2.700 Punkten gebaut, bei dem die Verbindungen zufällig waren.

Wenige Verbindungen: Wenn die Punkte nur wenige Nachbarn haben, ist das Muster sehr unterschiedlich. Der „Unordnungsmesser" zeigt einen hohen Wert.
Viele Verbindungen: Wenn man immer mehr Straßen baut, bis jeder mit jedem verbunden ist, gleichen sich alle Muster an. Alles wird gleichförmig. Der Messwert sinkt fast auf Null.
Die Geschwindigkeit: Das Tolle ist: Das geht schnell! Selbst bei 2.700 Punkten braucht der Computer nur etwa 1,4 Sekunden pro Messung. Das ist schnell genug für echte Anwendungen.

Warum ist das wichtig? (Das Fazit)

Stellen Sie sich vor, Sie wollen die Gesundheit eines riesigen Stromnetzes überwachen.

Früher mussten Sie die Daten in eine lange Liste umwandeln und dabei wichtige Informationen über die Verbindungen verlieren.
Mit SampEnG können Sie direkt ins Netz schauen. Sie können sagen: „Aha, hier wird es plötzlich zu vorhersehbar (zu ruhig) oder zu chaotisch (zu unruhig)."

Zusammengefasst:
Die Autoren haben einen neuen „Unordnungsmesser" gebaut, der nicht nur auf Zeitreihen funktioniert, sondern direkt auf Netzwerke angewendet werden kann. Er nutzt die Struktur des Netzes (wer ist mit wem verbunden?), um zu messen, wie komplex oder vorhersehbar die Daten in diesem Netz sind. Das öffnet die Tür, um alles von sozialen Netzwerken bis hin zu biologischen Zellsystemen besser zu verstehen.

Technische Zusammenfassung: Sample Entropy für Graph-Signale (SampEnG)

Titel: Sample entropy for graph signals: An approach to nonlinear analysis of graph signals
Autoren: Mei-San Maggie Lei, John Stewart Fabila Carrasco, Javier Escudero

1. Problemstellung und Motivation

Herkömmliche Methoden zur Analyse von Graph-Signalen (Graph Signal Processing, GSP), wie die graphbasierte Permutationsentropie oder Dispersion-Entropie, basieren häufig auf symbolischer Dynamik. Dies erfordert eine Diskretisierung der Signale, um die Shannon-Entropie zu berechnen. Ein wesentlicher Nachteil dieser Ansätze ist der Verlust von Informationen, die im kontinuierlichen Zustandsraum enthalten sind.

Die klassische Sample Entropy (SampEn) ist ein etabliertes Maß für die Irregularität und Komplexität von Zeitreihen im kontinuierlichen Zustandsraum. Sie schätzt die bedingte Wahrscheinlichkeit, dass Muster einer Länge $m$ auch bei einer Länge von $m+1$ ähnlich bleiben. Bisher fehlte jedoch eine direkte Verallgemeinerung dieser Methode auf Graph-Signale, die die topologische Struktur des Graphen berücksichtigt, ohne auf eine Diskretisierung angewiesen zu sein.

2. Methodik: SampEnG

Die Autoren stellen SampEnG (Sample Entropy for Graph Signals) vor, eine Verallgemeinerung der SampEn für Signale auf Graphen. Der Kern der Methode liegt im Ersatz des zeitlichen Verzögerungs-Embeddings durch ein Multi-Hop-Graph-Embedding.

Konzept des Graph-Hops: Anstelle von zeitlichen Schritten wird der "Graph-Hop" verwendet. Ein Hop entspricht einer einzigen Kantenüberquerung von einem Knoten zu einem benachbarten Knoten.
Lokale Aggregation: Für jeden Knoten $i$ wird ein Vektor (Muster) konstruiert, dessen Komponenten lokale Graph-Signal-Aggregate darstellen. Diese charakterisieren die radialen Profile um den Knoten herum in Vielfachen von $L$ Hops ( $L = 0, 1, 2, \dots$ ).
Graph-Shift-Operator: Die Aggregation erfolgt über Potenzen der Graph-Verschiebe-Operator-Matrix (Adjazenzmatrix $A$ $A$ oder gewichtete Adjazenz $W$ $W$ ).
- $x^0_i$ ist der Signalwert am Knoten $i$ .
- $x^L_i$ ist ein walk-gewichteter Mittelwert der $L$ -Nachbarschaft von Knoten $i$ , berechnet als:
  $x^L_i = \frac{1}{\text{deg}_L(i)} \sum_{j \in N_L(i)} (A^L)_{ij} x_j$
  wobei $\text{deg}_L(i)$ die Summe der $L$ -Schritte von $i$ ist und $N_L(i)$ die Menge der erreichbaren Knoten nach genau $L$ Schritten darstellt.
Musterbildung: Für jeden Knoten werden $m$ -dimensionale Muster $x^m(i)$ und $(m+1)$ -dimensionale Muster $x^{m+1}(i)$ erstellt.
Berechnung der Entropie:
1. Es wird die Anzahl der Paare $(i, j)$ gezählt, deren Muster innerhalb einer Toleranz $\epsilon$ (basierend auf der Chebyshev-Distanz) übereinstimmen.
2. Die Häufigkeiten für Muster der Länge $m$ ( $B_m$ ) und $m+1$ ( $A_m$ ) werden berechnet.
3. Die SampEnG wird als negativer Logarithmus des Verhältnisses definiert:
  $\text{SampEnG} = -\ln\left(\frac{A_m(r)}{B_m(r)}\right)$

3. Wichtige Beiträge

Verallgemeinerung: Einführung einer kontinuierlichen, bedingten Entropie für Graph-Signale, die die Einschränkungen symbolischer Dynamik umgeht.
Topologie-Bewusstsein: Die Methode nutzt die Multi-Hop-Struktur des Graphen, um lokale Nachbarschaften zu erfassen, anstatt nur direkte Nachbarn.
Reduktionsbeweis: Empirischer Nachweis, dass SampEnG auf gerichteten Pfad-Graphen exakt in die klassische 1D-SampEn übergeht.
Skalierbarkeit: Demonstration der Rechenpraktikabilität auf Graphen mit tausenden Knoten.

4. Ergebnisse und Experimente

Logistische Abbildung (Logistic Map):
- Das Modell wurde auf gerichteten und ungerichteten Pfad-Graphen getestet.
- Ergebnis: Auf gerichteten Pfad-Graphen reduziert sich SampEnG exakt auf die klassische 1D-SampEn. Auf ungerichteten Pfaden folgt der Trend der klassischen Methode, zeigt jedoch leichte quantitative Unterschiede aufgrund der nicht-kausalen, symmetrischen Nachbarschaftsstruktur.
- Die Methode erfasst erfolgreich die Bifurkationspunkte und Periodizitätsinseln des Übergangs von Ordnung zu Chaos.
Erdős-Rényi (ER) Graphen:
- Experimente wurden auf gerichteten ER-Graphen mit $N=2700$ Knoten durchgeführt.
- Einfluss der Konnektivität: Bei dünn besetzten Netzwerken (kleine durchschnittliche Ausgrad $K$ , niedrige Verbindungswahrscheinlichkeit $p$ ) nimmt die SampEnG mit steigender Konnektivität ab. Dies spiegelt eine erhöhte Regularität in der Topologie wider.
- Dichte Netzwerke: Bei sehr dichten Graphen nähert sich die SampEnG Null an. Dies liegt an der Homogenisierung der lokalen Nachbarschaften durch große Überlappungen, was die effektive Variabilität der Muster reduziert.
- Einfluss von $m$ : Eine Erhöhung der Musterlänge $m$ verstärkt diesen Effekt, da der "Reichweite"-Radius der Nachbarschaften wächst und die Muster homogener werden.
- Laufzeit: Die Methode ist effizient; für $N=2700$ wurden Laufzeiten von ca. 295 ms ( $m=1$ ) bis 1400 ms ( $m=3$ ) pro Realisierung auf einem Apple M3 CPU gemessen.

5. Bedeutung und Ausblick

SampEnG eröffnet neue Wege zur Analyse von Graph-Signalen, indem es das Konzept der bedingten Entropie auf eine breite Palette von Netzwerkdaten erweitert. Es ermöglicht die nichtlineare Analyse von Signalen in kontinuierlichen Räumen unter Berücksichtigung der komplexen Topologie von Netzwerken.

Zukünftige Arbeiten könnten alternative Graph-Embeddings untersuchen, die Robustheit gegenüber Rauschen in Graph-Signalen evaluieren und Anwendungen in realen vernetzten Sensordomänen (z. B. Sensor-Netzwerke, soziale Netzwerke, neuronale Netze) erforschen.