graph_randomisierung.tex

Mit dem Havel-Hakimi-Generator können wir nun für jede graphische Sequenz einen Graphen als Zeugen für diese Sequenz erzeugen.
Die generierten Graphen sind aber zum einen deterministisch, \dh, für eine fixierte Sequenz~$\degseq$ wird immer derselbe Graph erzeugt, und zum anderen pathologisch (extrem viele Dreiecke, extrem hohe Grad-Assortativität \ldots).
Das Fixed-Degree-Sequence-Model (FDSM)\aside{ Fixed-Degree-Sequence-Model (FDSM)} schlägt daher vor, dass wir erst den Havel-Hakimi-Algorithmus ausführen und dann den Graphen durch viele zufällige kleine Änderungen lokal perturbieren.
Es besteht die begründete Hoffnung, dass wenn der hierdurch implizierte Irrweg lang genug ist, wir dann schlussendlich einen (fast) uniformen Graph aus $\Gd$ produzieren.

Formal beschreiben wir die Perturbation als einen Markov-Chain-Monte-Carlo-Prozess.
Der Zustandsraum der Markov-Kette ist $\gd$.
Für jeden Graphen $G \in \gd$ bestimmt der gewählte Prozess, welche anderen Graphen $G' \subseteq \gd$ (mit welcher Wahrscheinlichkeit) innerhalb von einem Schritt erreicht werden können.
Es entsteht also ein \aside{Übergangsgraph} Übergangsgraph (den wir auch Markov-Kette nennen), dessen gerichtete und gewichtete Kanten mögliche Schritte zusammenfassen.

\section{Edge-Switching}
Edge-Switching ist wohl der meist genutzte Prozess zum Perturbieren von Graphen.
Das ist sicherlich auch dem geschuldet, dass er sehr einfach zu implementieren ist und in der Praxis relativ gut funktioniert (mehr dazu später).

Anders als bei den meisten Modellen gibt es signifikante funktionale Unterschiede zwischen gerichteten und ungerichteten Graphen.
Edge-Switching funktioniert aber mit noch ausgefalleneren Graphklassen (siehe \zB \cite{carstens_2017}), \zB
\begin{itemize}
    \item ungerichtete, einfache Graphen mit fester Gradsequenz
    \item ungerichtete, einfache zusammenhängende Graphen  mit fester Gradsequenz \cite{DBLP:journals/compnet/VigerL16}
    \item gerichtete Graphen  mit fester Gradsequenz
    \item gerichtete, einfache Graphen (mit einfacher Modifikation)  mit fester Gradsequenz
    \item Graphen mit fester Joint-Degree-Sequence~\cite{DBLP:conf/alenex/StantonP11} (\dh, die Anzahl der Kanten zwischen Knoten mit Graden~$d_1$ bzw.~$d_2$ wird für alle Paare $(d_1, d_2)$ definiert)
    \item bipartite Graphen
    \item weitere Klassen bei Modifikation möglich
\end{itemize}

Das \aside{allgemeine Edge-Switches} allgemeine Framework führt eine fixierte Anzahl an sog. \emph{Edge-Switches} aus.
Diese unterscheiden sich vor allem darin, welche Graphen als legal betrachtet werden:
\begin{enumerate}
    \item Ziehe aus $G$ zwei Kanten $e_1 = (a,b)$ und $e_2 = (u,v)$ zufällig mit Zurücklegen.
    \item Falls $e_1 = e_2$: Verwerfe den Switch ersatzlos.

    \item Berechne zwei neue Kanten $e'_1 = (a, v)$ und $e'_2 = (u, b)$.

    \item Erzeuge Graph~$G'$ aus $G$ durch Ersetzen von $e_1$ und $e_2$ durch $e'_1$ und $e'_2$.

    \item Wenn $G'$ durch die Modifikation illegal wurde, verwerfe den Switch ersatzlos.
\end{enumerate}

In \aside{ungerichtete Switches} ungerichteten Graphen entscheiden wir durch fairen Münzwurf, ob wir $e_1 = \set{a,b}$ und $e_2 = \set{u, v}$ durch
\begin{equation}
    e'_1 = \set{a, v} \qquad e'_2 = \set{b, u},
\end{equation}
oder
\begin{equation}
    e'_1 = \set{a, u} \qquad e'_2 = \set{b, v},
\end{equation}
zu ersetzen versuchen.

\section{Edge-Switching auf unbeschränkten Matrizen}\label{sec:edge_switching_irreduzibel}
Bevor wir analysieren, ob Edge-Switching eine uniforme Verteilung erzeugt, sollten wir uns eine viel grundlegendere Frage stellen:
Können wir von einem beliebigen Startpunkt aus überhaupt jeden anderen Graphen erzeugen?
Formal fragen wir also, ob der Übergangsgraph stark zusammenhängend ist (analog: Ist die Markov-Kette irreduzibel?).
Die Antwort wird ein klares und unmissverständliches \qq{It depends \dots} sein.

\bigskip

Es ist hilfreich, über die Adjazenzmatrizen zu argumentieren.
Beobachte, dass die Sequenzen der Zeilen- und Spaltensummen der Adjazenzmatrizen von allen Graphen in $\gd$ identisch sind.
Dies motiviert folgende Abstraktion:

\def\msz{\ensuremath{\mathbb M(Z,S)}\xspace}

Seien $Z=(z_1, \ldots, z_n)$ und $S=(s_1, \ldots, s_m)$ Zeilen- und Spaltensummen.
Dann \aside{\msz: Binärmatrizen mit fixierten Zeilen- und Spaltensummen} sei \msz die Menge aller $\set{0, 1}^{n \times m}$ Matrizen, die diese Beschränkungen erfüllen.
Konkrete Graphklassen stellen \idR weitere Anforderungen; so müssen ungerichtete einfache Graphen noch erfüllen:
\begin{itemize}
    \item symmetrische Matrizen und damit $Z = S$
    \item nur $0$-Einträge auf der Hauptdiagonalen (wir sprechen von \emph{strukturellen Nullen}\aside{strukturelle Nullen: verbotene Kanten})
\end{itemize}
Für den Moment betrachten wir aber solche Einschränkungen nicht.

\begin{exercise}
    Welche Graphklasse entspricht \msz am ehesten?
\end{exercise}

Einen gerichteten Edge-Switch können wir als sog. \emph{alternierendes Rechteck} modellieren.
Für eine Matrix $(m_{ij})_{ij} = M \in \msz$ nennen wir $((i_1, j_1),\ (i_2, j_2))$ alternierendes Rechteck, wenn $m_{i_1j_1} = m_{i_2j_2} = 1$  und $m_{i_1j_2} = m_{i_2j_1} =0$;
jeweils gegenüberliegende Ecken haben also die gleichen Werte in $M$ und deren \qq{Flip} entspricht dem Effekt eines akzeptierten Edge-Switches.

\begin{theorem}[nach \cite{rao96}]
    Seien $A$ und $B$ zwei Matrizen in $\msz$.
    Sei $t$ das Minimum der Anzahl von Nullen in $A$ und der Anzahl von Einsen in $A$.
    Dann können wir $A$ in $B$ mittels einer Folge von höchstens $t$ alternierenden Rechteck-Switches überführen.
\end{theorem}

\begin{proof}
    OBdA sei $(a_{ij})_{ij} = A \ne B = (b_{ij})_{ij}$ (da wir sonst fertig sind).
    Dann sei $d$ die Hamming-Distanz zwischen $A$ und $B$, \dh die Anzahl der Einträge, in denen sich beide unterscheiden.
    Beobachte, dass $d$ eine gerade positive Zahl sein muss (weshalb?).

    Dann existiert ein Index $(i_1, j_1)$ mit $a_{i_1j_1} \ne b_{i_1j_1}$ und sei oBdA $a_{i_1j_1} = 1$.
    Da die Summe der $j_1$-ten Spalte fixiert ist, muss es in dieser eine Zeile $i_2$ geben, \sd $a_{i_2j_1} = 0$ und $b_{i_2j_1} = 1$.
    Da wiederum die Summe der $i_2$-ten Zeile fixiert ist, muss es ein $j_2$ geben, \sd $a_{i_2j_2} = 1$ und $b_{i_2j_2} = 0$.
    Wir haben also drei Ecken gefunden.

    Könnten wir $a_{i_1j_2} = 0$ garantieren, hätten wir ein alternierendes Rechteck und wären fertig;
    im Allgemeinen gilt das aber nicht.
    Daher setzen wir diesen Prozess so lange fort, bis wir einen sog. alternierenden Kreis schließen.
    Das muss irgendwann passieren, da wir nur $d < \infty$ passende Einträge haben.
    Sei $i_1j_1, i_2j_1, i_2j_2, i_3j_2, \ldots, i_kj_k, i_1j_k$ ein \emph{kürzester} alternierender Pfad.
    Wir zeigen, dass die ersten vier Einträge sich immer für einen Switch eignen:
    \begin{itemize}
        \item Wenn $a_{i_1j_2} = 0$, bilden $i_1j_1$, $i_2j_1$, $i_2j_2$ und $i_1j_2$ ein alternierendes Rechteck.
        \item Wenn $b_{i_1j_2} = 1$, können wir denselben Switch in $B$ ausführen.
        \item Der Fall $a_{i_1j_2} = 1$ und $b_{i_1j_2} = 0$ ist ein Widerspruch dazu, dass der betrachtete Kreis minimale Länge hat, da wir die ersten drei Einträge entfernen können.
    \end{itemize}

    In jedem Fall können wir also in $A$ oder $B$ einen Switch ausführen, der die Hamming-Distanz zwischen den beiden Matrizen um mindestens zwei reduziert.
    Da jeder Switch reversibel ist, folgt der starke Zusammenhang der Übergangsmatrix direkt.

    Weiter wissen sogar, dass $A$ und $B$ mittels höchstens $d/2$ Switches ineinander überführt werden können.
    Aufgrund der Symmetrie,
    \begin{align}
        d/2 & = \card{\set{ (i, j) \mid i, j \text{, \sd\ } a_{ij} = 1 \land b_{ij} = 0}}  \\
            & = \card{\set{ (i, j) \mid i, j \text{, \sd\ } a_{ij} = 0 \land b_{ij} = 1}},
    \end{align}
    folgt direkt
    \begin{align}
        d/2 \le t =  \min\Big(
         & \card{\set{ (i, j) \mid i, j \text{, \sd\ } a_{ij} = 1}},       \\
         & \card{\set{ (i, j) \mid i, j \text{, \sd\ } a_{ij} = 0}}  \Big).
    \end{align}
\end{proof}

Wir können also Matrizen in \msz ineinander überführen.
Das impliziert auch, dass der Übergangsgraph von gerichteten Graphen ohne Mehrfachkanten (aber ggf. mit Eigenschleifen) stark zusammenhängend ist.

Leider gilt das nicht für gerichtete \emph{einfache} Graphen.
Als Gegenbeispiel dient ein Graph mit Knoten $V = \set{a,b,c}$ und Kreis $a \to b \to c \to a$.
Es ist nicht möglich, die Orientierung dieses Dreiecks auf $a \leftarrow b \leftarrow c \leftarrow a$ umzukehren, obwohl beide Graphen eine identische Gradsequenz aufweisen.

\begin{exercise}
    Konstruiere eine Sequenz von Edge-Switches, die das Dreieck umkehren kann, und Eigenschleifen verwendet.
\end{exercise}

Glücklicherweise sind Dreiecke das einzige Problem von Edge-Switching auf einfachen gerichteten Graphen.
Es gibt zwei einfache Lösungsansätze:
\begin{itemize}
    \item Führe neue Switchings, die die Orientierung eines gerichteten 3-Kreises ändern, ein.
    \item Bevor der MCMC-Prozess startet, führen wir einen Vorverarbeitungsschritt aus, der alle gerichteten 3-Kreise sucht und zufällig orientiert.
\end{itemize}

Für einfache \emph{un}gerichtete Graphen ist dies alles nicht notwendig -- die entsprechende Markov-Kette ist stark zusammenhängend.

\section{Grenzverteilung von Edge-Switching}
Wir wissen nun, dass Edge-Switching auf wichtigen Graphklassen potentiell alle Graphen erzeugen kann.
In diesem Kapitel werden wir zeigen, dass für sehr lange Irrwege die Wahrscheinlichkeitsverteilung der Ausgabe zu einer Gleichverteilung über alle möglichen Graphen konvergiert;
der Prozess hat also eine uniforme Grenzverteilung.
Da wir in der Praxis jedoch immer nur endlich lange Irrwege ausführen können, wird der Edge-Switching-MCMC-Algorithmus oft als \emph{approximativ uniform} bezeichnet.

Zunächst wiederholen wir ein paar Definitionen aus den Anfangstagen des Informatikstudiums.
Hierfür stellen wir eine Markov-Kette~$\mathcal M$ i.d.R. als Tupel $(G, P)$ mit gerichteten Graph $G = (V, E)$ dar, wobei $P$ eine stochastische $|V| \times |V|$-Matrix ist (\dh, jede Zeilensumme ist $1$) und die Existenz einer Kante in~$E$ einem positiven Eintrag in $P$ entspricht, genauer $(i, j) \in E \Leftrightarrow P_{ij} > 0$.
Gegeben einer Startverteilung $\pi \in [0, 1]^n$ (Zeilenvektor) entspricht das Vektormatrixprodukt $\pi P$ der Verteilung nach einem Schritt und $\pi P^k$ der Verteilung nach $k$ Schritten.

\begin{definition}\label{def:stationaere-verteilung}
    Sei \aside{stationäre Verteilung}$\mathcal M = (G, P)$ eine Markov-Kette und $\pi \in [0, 1]^n$ eine Wahrscheinlichkeitsverteilung über den Zuständen.
    Wir nennen $\pi$ genau dann eine \emph{stationäre Verteilung}, wenn gilt
    \begin{equation}
        \pi P = \pi. \qedhere
    \end{equation}
\end{definition}

Wie der Name bereits suggeriert, handelt es sich bei einer stationären Verteilung um einen Fixpunkt\footnote{Wir können eine stationäre Verteilung als Eigenvektor mit Eigenwert~$1$ auffassen.};
wir können beliebig viele Schritte der Markov-Kette ausführen ohne die Verteilung zu verändern.

\begin{example}
    Betrachten wir z.B. eine Kette, die aus drei Zuständen und folgende Übergangswahrscheinlichkeiten hat:

    \begin{equation}
        \begin{pmatrix}
            0 & 1/2 & 1/2 \\
            0 & 1   & 0   \\
            0 & 0   & 1
        \end{pmatrix}
    \end{equation}

    Aus Zustand $1$ gelangen mittels fairem Münzwurf entweder in Zustand 2 oder 3.
    Diese beiden Zustände sind dann absorbierend (haben nur eine Eigenschleife).
    Dann sind z.B. $(0, 1, 0)$ und $(0, 0, 1)$ stationäre Verteilungen (gibt es weitere?).
    Die Verteilung $(1, 0, 0)$ ist nicht stationär, da wir im nächsten Schritt auf $(0, 1/2, 1/2)$ übergehen.
\end{example}

Das Beispiel hat also mehrere stationäre Verteilungen.
Es \aside{Grenzverteilung}gibt jedoch Markov-Ketten mit einem besonderen Verhalten:
unabhängig vom Startpunkt, konvergiert der Prozess nach ausreichend langer Ausführung gegen eine eindeutige stationäre Verteilung.
\emph{Wenn} eine solche Verteilung existiert nennen wir diese \emph{Grenzverteilung}:

\def\grenz{\ensuremath{\mathcal G(\mathcal M)}\xspace}

\begin{definition}\label{def:grenzverteilung}
    Sei $\mathcal M = (G, P)$ eine Markov-Kette.
Dann heißt die Verteilung \grenz{} Grenzverteilung der Kette~$\mathcal M$, wenn für alle Startverteilungen~$\pi$ gilt:
\begin{equation}\label{eq:grenzverteilung}
        \smashoperator{\lim_{k \to \infty}} \pi P^k = \mathcal G(\mathcal M)
    \end{equation}
\end{definition}

\noindent
Beobachte, dass wir den Startzustand~$\pi$ in \cref{eq:grenzverteilung} auch nach vorn ziehen können
\begin{equation}
    \smashoperator{\lim_{k \to \infty}} \pi P^k = \pi \underbrace{\lim_{k \to \infty} P^k}_{:= P^{(\infty)}}
\end{equation}

Da eine etwaige Grenzverteilung unabhängig von der Startverteilung ist und vollständig durch $P^{(\infty)}$ beschrieben wird, ist die Grenzverteilung eindeutig.
Wir können sogar noch einen Schritt weitergehen:

\begin{lemma}\label{lem:grenzverteilung_ist_eindeutige_stationaere_verteilung}
    Sei $\mathcal M = (G, P)$ eine Markov-Kette, so dass die Grenzverteilung~\grenz existiert.
    Dann ist \grenz die einzige stationäre Verteilung.
\end{lemma}

\begin{proof}
    Die Aussage, dass \grenz eine stationäre Verteilung ist, überlassen wir für \cref{ex:grenzverteilung_ist_stationaer}.
    Wir zeigen daher nur, dass es keine andere stationäre Verteilung gibt.

    Sei $\sigma$ eine beliebige stationäre Verteilung von $M$.
    Dann gilt $\sigma P = \sigma$ gemäß \cref{def:stationaere-verteilung}.
    Dies können wir offensichtlich iterieren:
    \begin{equation}
        \sigma P^k = \underbrace{(\sigma P)}_{=\sigma} P^{k-1} = \sigma P^{k-1} = \ldots = \sigma
    \end{equation}

    \noindent
    Per \cref{def:grenzverteilung} muss, haben wir auch $\smashoperator{\lim_{k \to \infty}} \sigma P^k = \grenz$.
    Daraus folgt $\sigma = \grenz$.
\end{proof}

\begin{exercise}\label{ex:jede_zeile_grenzverteilung}
    Sei $\mathcal M = (G, P)$ eine Markov-Kette, für die der Grenzwert~$\mathcal G(\mathcal M)$ existiert.
    Zeige, dass jede Zeile von $P^{(\infty)}$ genau $\mathcal G(\mathcal M)$ entspricht.
\end{exercise}

\begin{exercise}\label{ex:grenzverteilung_ist_stationaer}
    Sei $\mathcal M = (G, P)$ eine Markov-Kette, für die der Grenzwert~$\mathcal G(\mathcal M)$ existiert.
    Zeige, dass $\mathcal G(\mathcal M)$ eine stationäre Verteilung ist.
\end{exercise}

Wenn eine Markov-Kette eine Grenzverteilung besitzt, ist es also egal, wo wir starten:
Irgendwann \qq{vergessen} wir die Startverteilung\dots{}
Jetzt wäre noch wichtig, dass wir überall \qq{raus} kommen können.
Solche \aside{ergodisch}Markov-Ketten nennen wir \emph{ergodisch}:

\begin{definition}
Sei $\mathcal M = (G, P)$.
Die Markov-Kette $\mathcal M$ heißt \emph{ergodisch}, wenn $\mathcal G(\mathcal M)$ existiert und für eine beliebige Verteilung~$\pi$ die Grenzwahrscheinlichkeit jedes Zustands~$j$:
\begin{equation*}
    \forall j\colon \qquad (\pi \lim_{k \to \infty} P^k)_{j} > 0 \hfill \qedhere
\end{equation*}
\end{definition}

Beachte, dass wir aus \cref{ex:jede_zeile_grenzverteilung}, wissen, dass jede Zeile in $P^{(\infty)} = (\lim_{k \to \infty} P^k)$ identisch ist; somit können wir die Definition sogar ohne~$\pi$ schreiben:
\begin{equation}
    \forall j, \text{Verteilung}~\pi\colon\qquad (\pi \lim_{k \to \infty} P^k)_{j} = (\lim_{k \to \infty} P^k)_{1,j}
\end{equation}

\bigskip

Es kann nun gezeigt werden, dass eine Markov-Kette genau dann ergodisch ist, wenn sie (i) irreduzibel und (ii) aperiodisch ist.
Ein \aside{aperiodisch}Kette heißt \emph{aperiodisch}, wenn für jeden Knoten $v$ der größte gemeinsame Teiler der Längen aller Pfade von $v$ nach $v$ den Wert~$1$ hat.

\begin{theorem}
    Edge-Switching impliziert für u.\,a. (i) einfache, ungerichtete und (ii) gerichtete Graphen mit möglichen Eigenschleifen eine ergodische Markov-Kette.
\end{theorem}

\begin{proof}
    Wir zeigen den Beweis für gerichtete Graphen; er folgt analog für ungerichtete Graphen.
Aus \cref{sec:edge_switching_irreduzibel} wissen wir bereits, dass der Übergangsgraph von Edge-Switching stark zusammenhängend ist.
    Die Markov-Kette ist also irreduzibel.

    Wir müssen also nur noch zeigen, dass sie auch aperiodisch ist.
    Hier wird ein vermeintlicher Bug zum Feature:
    Im Edge-Switching-Framework nutzen wir Rejection-Sampling und verwerfen illegale Switches ersatzlos.
    Die Behauptung ist nun, dass für jeden Zustand der Kette mindestens ein illegaler Switch existiert (es würde sogar reichen, wenn es eine einzige Eigenschleife gibt!):

Da wir mit Zurücklegen ziehen, kann es passieren, dass $e_1 = e_2$; wir verwerfen also mindestens mit Wahrscheinlichkeit $1 / m$.
    Dies entspricht einer Eigenschleife im Übergangsgraph.
    Angenommen, es existiert ein Pfad $v$ nach $v$ der Länge~$k$ (muss existieren, da die Kette irreduzible ist).
    Dann können wir durch Umwege über Eigenschleifen einen Pfad beliebiger Länge $k' > k$ erzeugen.
    Der ggT aller Pfade ist $1$.

    Die Markov-Kette ist also irreduzibel und aperiodisch und somit ergodisch.
\end{proof}

Das ist aufgrund des folgenden Lemmas hilfreich:
\begin{lemma}
    Sei $\mathcal M = (G, P)$ eine Markov-Kette mit symmetrischer Übergangsmatrix $P_{ij} = P_{ji}$ für alle $i, j$.
Falls die Grenzverteilung~\grenz existiert, ist \grenz die Gleichverteilung.
\end{lemma}

\begin{proof}
Wir zeigen zunächst, dass die Gleichverteilung $\sigma = \bigl(\frac{1}{n}, \ldots, \allowbreak \frac{1}{n}\bigr)$ eine stationäre Verteilung ist.
Für einen beliebigen Zustand~$j$ gilt:
    \begin{align}
        (\sigma P) _ j & \stackrel{\text{Vek.-Mat.-Mul.}}{=} \sum_{i=1}^n \sigma_i P_{ij}
        = \frac 1 n \sum_{i=1}^n P_{ij}                                                   \\
                       & \stackrel{P\text{ symmetrisch}}{=} \frac 1 n \sum_{i=1}^n P_{ji} \\
                       & \stackrel{P\text{ stochastisch}}{=} 1 / n = \sigma_j
    \end{align}

Nach \cref{lem:grenzverteilung_ist_eindeutige_stationaere_verteilung}, impliziert die Existenz der Grenzverteilung~\grenz, dass $\grenz = \sigma$ die einzige stationäre Verteilung ist.
\end{proof}

Auch hier wird wieder der Bug des Rejection-Samplings zum Feature.
Jeder gerichtete Switch wird über genau die zwei betroffenen Kanten~$e_1$ und $e_2$ definiert und somit mit Wahrscheinlichkeit $1/m^2$ gewählt.
Durch wiederholte Wahl dieser beiden Kanten wird der Switch wieder rückgängig gemacht.
Die Wahrscheinlichkeiten von Vorwärts- und Rückwärtsrichtung sind also identisch und die Übergangsmatrix ist daher symmetrisch.
Analoges gilt auch für ungerichtete Switches.

\section{Implementieren von Edge-Switching}
Die sequentielle Implementierungen von Edge-Switching für gerichtete und ungerichtete Graphen ist relativ ähnlich.
Daher nehmen wir im Folgenden gerichtete Graphen an -- für einen ungerichteten Graphen müssen wir nur beachten, dass $\set{u, v} = \set{v, u}$ ist und beide Kanten\qq{richtungen} diesselbe Kante repräsentieren.
Üblicherweise repräsentieren wir beide Richtung durch eine kanonische Repräsentation $(u, v)$, wobei wir \zB durch $u \le v$ Uneindeutigkeiten verhindern.
Vor jedem Zugriff auf die im Folgenden beschriebenen Datenstrukturen würden wir also prüfen, ob die Invariante gilt, und anderenfalls die Kantenrichtung flippen.

Ein zufälliger Edge-Switch benötigt die folgenden Operationen:
\begin{itemize}
    \item zufälliges Ziehen einer Kante $(u,v) \in E$ (um die aktiven Kanten zu finden)
    \item Prüfen, ob eine Kante $(u, v)$ existiert (um Mehrfachkanten zu vermeiden)
    \item Löschen einer Kante $(u, v) \in E$ (um Updates auszuführen)
    \item Hinzufügen einer Kante $(u, v)$ (um Updates auszuführen)
\end{itemize}

Die beiden letzten Operationen können auch in einer zusammengefasst werden.

\subsection{Auf Adjazenzmatrizen}
Adjazenzmatrizen können alle Operationen außer das Ziehen einer zufälligen Kante in konstanter Zeit ausführen.
Das Ziehen von zufälligen Kanten können wir aber mit einer dedizierten Datenstruktur lösen --
\zB ein ungeordnetes Array~$A$, in dem jede Kante genau einmal gespeichert wird.
Bei der Implementierungen müssen wir uns aber bei Updates minimal geschickt anstellen.
Für ein Update der Kante $(u,v)$ benötigen wir den entsprechenden Index~$i$ in $A$ mit $A[i] = (u,v)$;
diesen müssen wir glücklicherweise nicht suchen, da wir ausnutzen können, dass wir nur Kanten ersetzen, die wir vorher gezogen haben.
Wir merken uns den Index einfach \dots{}
Mit diesen wenigen Tricks können wir jeden Edge-Switch in konstanter Zeit ausführen.
%Für große $n$ und dünne Graphen kann allerdings der Speicherverbrauch von $\Theta(n^2)$ Bits ein echtes Problem werden.

\subsection{Auf Adjazenzlisten}
Adjazenzlisten sind in vielerlei Hinsicht eine Herausforderung für Edge-Switching.
Allerdings verwalten viele existierenden Softwarebibliotheken Graphen in Adjazenzlisten; daher kann es lohnenswert sein, direkt auf der nativen Graphrepräsentation zu arbeiten.
Dies gilt vor allem dann, wenn wir während jedes Switches zusätzliche Eigenschaften prüfen wollen und \zB eine Breitensuche ausführen möchten, um den Zusammenhang des Graphs zu prüfen.

Um in einer Adjazenzliste eine Kante uniform zufällig zu ziehen, bietet sich ein zweistufiges Experiment an.
Zunächst wählen wir einen Knoten~$u$ mit Wahrscheinlichkeit $\deg(u) / (2m)$ und dann einen Nachbarn von $u$ uniform zufällig.
Da Edge-Switching den Grad von Knoten nicht verändert, ist es sinnvoll, vorab in Zeit $\Theta(n)$ eine Alias-Tabelle zu konstruieren, um das gewichtete Ziehen zu beschleunigen.

Um schnelle Updates zu unterstützen, ist es in der Regel hilfreich, eine unsortierte Adjazenzliste vorzuhalten.
Dann kosten aber Existenzanfragen für die Kante $\set{u,v}$ Laufzeit $\Oh{\min(\deg(u), \deg(v))}$.
Alternativ könnten wir die Nachbarschaften sortiert halten, dann dauern aber Updates $\Oh{\deg(u) + \deg(v)}$ Zeit.
Gerade bei verzerrten Gradverteilungen (\zB Power-Law) bietet sich daher die erste Variante an.

Es gibt aber noch einen weiteren Ansatz: So nutzt die Implementierung von~\cite{DBLP:journals/compnet/VigerL16} eine Adjazenzliste, bei denen hinreichend große Nachbarschaften als Hashsets ausgelegt sind.
In diesem Setting können wir einen Edge-Switch mit einer erwartet konstanten Laufzeit ausführen.

\subsection{Mit Hashsets}
Wie wir bereits gesehen haben, sind Adjazenzmatrizen für Edge-Switching auf dichten Graphen eine gute Wahl (in diesem Fall können wir sogar auf die Kantenliste verzichten! Warum?)
Für dünne Graphen kann aber der Speicherverbrauch von $\Theta(n^2)$ Bits problematisch werden.
Wir können daher ein Hashset nutzen, das alle Kanten abspeichert (für ungerichtete Graphen in kanonischer gerichteter Form).

Im Vergleich zu unserer Diskussion von \emph{Adjazenzmatrizen} können wir sogar gänzlich darauf verzichten, die Kantenliste zu samplen, wenn wir ein Hashset mit offener Adressierung nutzen.
Da sich die Anzahl der Kanten während Edge-Switching nicht ändert, ist es einfach, einen konstanten Load-Factor des Hashsets zu garantieren.
Dieser sollte so gewählt werden, dass nur ein konstanter Anteil der Zellen im Hashset leer ist;
dann ziehen wir so lange uniform Zellen aus dem Hashset, bis wir eine Kante gefunden haben, und geben diese dann zurück.
Durch den beschränkten Load-Factor ergibt sich eine konstante Akzeptanzwahrscheinlichkeit.

Gerade im Kontext von parallelen Algorithmen ist es hilfreich, auf dedizierte Kantenliste zu verzichten, da wir sonst sicherstellen müssen, dass die Updates in beiden Datenstrukturen von verschiedenen nebenläufigen Prozessen nicht zu Inkonsistenzen führen.