Übergangsgraph

Übergangsgraphen sind spezielle gerichtete Graphen mit Kantengewichten, die eine Verbindung zwischen Stochastik und Graphentheorie schlagen. Sie eignen sich besonders zur anschaulichen Darstellung von zeitdiskreten homogenen Markow-Ketten.

Ein einfacher Übergangsgraph mit zwei Knoten. Die Adjazenzmatrix des Graphen ist $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 $G$ heißt Übergangsgraph, wenn für jeden Knoten $i$ die Kantengewichte der von $i$ ausgehenden Kanten größer 0 sind und sich zu 1 aufsummieren:

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

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

Äquivalent dazu ist, dass der Graph $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 $c_{ij}$ genau die Wahrscheinlichkeit, vom Zustand $i$ in den Zustand $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 $j$ ist von dem Zustand $i$ aus erreichbar, wenn es einen $i-j$-Pfad im Übergangsgraph gibt.
• Zwei Zustände i und j kommunizieren genau dann, wenn sowohl ein $i-j$-Pfad als auch ein $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.