Übergangsgraph

Übergangsgraphen s​ind spezielle gerichtete Graphen m​it Kantengewichten, d​ie eine Verbindung zwischen Stochastik u​nd Graphentheorie schlagen. Sie eignen s​ich besonders z​ur anschaulichen Darstellung v​on zeitdiskreten homogenen Markow-Ketten.

Ein einfacher Übergangsgraph mit zwei Knoten. Die Adjazenzmatrix des Graphen ist ${\displaystyle A={\begin{bmatrix}0.3&0.7\\0.4&0.6\\\end{bmatrix}}}$. Da alle Einträge größer als 0 sind und alle Zeilensummen 1, ergeben ist sie zeilenstochastisch.

Definition

Ein gerichteter und kantengewichteter Graph ${\displaystyle G}$ heißt Übergangsgraph, wenn für jeden Knoten ${\displaystyle i}$ die Kantengewichte der von ${\displaystyle i}$ ausgehenden Kanten größer 0 sind und sich zu 1 aufsummieren:

${\displaystyle \sum _{j\in N_{G}^{+}(i)}c_{ij}=1}$.

Dabei ist ${\displaystyle N_{G}^{+}(i)}$ die Nachfolgermenge von Knoten ${\displaystyle i}$, also die Menge aller Knoten, die durch von ${\displaystyle i}$ ausgehende Kanten erreicht werden können.

Äquivalent dazu ist, dass der Graph ${\displaystyle G}$ Adjazenzgraph einer zeilenstochastischen Matrix ist.

Verwendung

Übergangsgraphen dienen zur anschaulichen Darstellung von homogenen Markow-Ketten mit endlichem Zustandsraum in diskreter Zeit. Dabei entspricht jeder Knoten einem Zustand des Systems und die Kantengewichte sind die Übergangswahrscheinlichkeiten zwischen den Zuständen. Dann ist ${\displaystyle c_{ij}}$ genau die Wahrscheinlichkeit, vom Zustand ${\displaystyle i}$ in den Zustand ${\displaystyle j}$ zu wechseln. Einige Eigenschaften der Markow-Kette finden sich direkt im Übergangsgraph wieder:

• Der Übergangsgraph ist genau dann stark zusammenhängend, wenn die Markow-Kette irreduzibel ist.
• Der Zustand ${\displaystyle j}$ ist von dem Zustand ${\displaystyle i}$ aus erreichbar, wenn es einen ${\displaystyle i-j}$-Pfad im Übergangsgraph gibt.
• Zwei Zustände i und j kommunizieren genau dann, wenn sowohl ein ${\displaystyle i-j}$-Pfad als auch ein ${\displaystyle j-i}$-Pfad im Übergangsgraph existiert.
• Ist der Übergangsgraph bipartit, so hat jeder Zustand der Markow-Kette gerade periode.
• Ist der Übergangsgraph bipartit und Zusammenhängend, so hat die Markow-Kette gerade Periode.

Anwendungsbeispiel

Mit Hilfe von Übergangsgraphen lässt sich das Wahl- und Kaufverhalten visualisieren. Dargestellt werden die prozentuale Zahl von Wieder- und Wechselwählern. Bezogen auf die obigen Abbildung würden 60 % der Partei bzw. dem Produkt A treu bleiben und 40 % zu Partei bzw. Produkt E wechseln. Die Zahl der Wiederwähler bei Partei bzw. Produkt E liegt bei 30 %, die Zahl der Wechselwähler bei 70 %. Allerdings wird der Übergangsgraph schon ab vier Parteien bzw. Produkten recht unübersichtlich.

Literatur

• Hans-Otto Georgii: Stochastik. Einführung in die Wahrscheinlichkeitstheorie und Statistik. 4. Auflage. Walter de Gruyter, Berlin 2009, ISBN 978-3-11-021526-7, doi:10.1515/9783110215274.
• Marion Patyna, Klaus Schilling: Lineare Algebra: Mehrstufige Prozesse – Matrizenrechnung, Eins Verlag Köln, 1. Auflage 2011, S. 104–118, ISBN 978-3-427-04440-6.