An inverse problem for fractional random walks on finite graphs

1. Problemstellung

Das Paper untersucht ein geometrisches inverses Problem auf einem endlichen, zusammenhängenden Graphen $G = (X, E)$ mit einer Menge von Knoten $X$ und Kanten $E$. Auf den Knoten ist eine Leitfähigkeit $\gamma: X \to (0, \infty)$ definiert.

Das zentrale Problem besteht darin, aus partiellen Beobachtungen eines fraktionalen Random Walks (Zufallspfads) auf dem Graphen folgende Größen wiederherzustellen:

• Die Gesamtzahl der Knoten $|X|$.
• Die Kantenmenge $E$ (die Graphstruktur).
• Die Leitfähigkeit $\gamma$ (bis auf einen positiven Skalierungsfaktor).

Die Daten:
Die Beobachtungen sind auf eine feste, beobachtbare Teilmenge der Knoten $B \subseteq X$ beschränkt. Für jeden diskreten Zeitschritt $t$ weiß man entweder, dass der Zufallspfad nicht in $B$ ist, oder man kennt den exakten Knoten $x \in B$, an dem er sich befindet.

Der fraktionale Random Walk:
Im Gegensatz zu klassischen Random Walks, bei denen nur Übergänge zu benachbarten Knoten erlaubt sind, erlaubt dieser Prozess „lange Sprünge" (long jumps). Die Übergangswahrscheinlichkeit $P(x, y)$ zwischen zwei verschiedenen Knoten $x, y$ hängt von der Leitfähigkeit $\gamma$ und der graphentheoretischen Distanz $d_G(x, y)$ ab:
$$P(x, y) := \frac{1}{m(x)} \frac{\gamma^{1/2}(x)\gamma^{1/2}(y)}{d_G(x, y)^\alpha}$$
wobei $\alpha > 0$ ein fester, bekannter Exponent ist und $m(x)$ eine Normierungskonstante ist. Dies entspricht einer diskretisierten Version des fraktionalen Leitfähigkeitsoperators, der in der kontinuierlichen Theorie (Calderón-Problem) eine große Rolle spielt.

2. Methodik

Die Autoren verwenden eine Kombination aus linearer Algebra, Graphentheorie und der Analyse von Markov-Ketten, um das inverse Problem zu lösen. Der Ansatz gliedert sich in zwei Hauptphasen:

Phase 1: Charakterisierung der Übergangsmatrix aus partiellen Daten
Die Daten werden als Folge von Submatrizen der Potenzen der Übergangsmatrix $P$ dargestellt. Da nur Knoten in $B$ beobachtbar sind, betrachtet man die Blöcke $(P^k)_{11}$, die die Übergangswahrscheinlichkeiten zwischen Knoten in $B$ nach $k$ Schritten beschreiben.

• Die Autoren definieren die Datenmenge $\Lambda_K(P) = \{(P^k)_{11}\}_{k=1}^K$.
• Ein zentrales Ergebnis ist, dass die Daten für $k \ge 3$ (also $\Lambda_3(P)$) ausreichen, um die Übergangsmatrix bis auf eine bestimmte Eichklasse (Gauge Class) zu bestimmen.
• Es wird gezeigt, dass Daten für $k > 3$ redundant sind. Dies ist ein überraschendes nicht-lokales Phänomen, da bei klassischen Random Walks (nur Nachbarn) mehr Schritte nötig wären, um entfernte Knoten zu erreichen.
• Die Beziehung zwischen zwei Matrizen $P$ und $\tilde{P}$, die dieselben Daten liefern, wird durch eine Gruppenwirkung beschrieben: $P = (I_N \oplus A) \tilde{P} (I_N \oplus A^{-1})$, wobei $A$ eine invertierbare Matrix ist.

Phase 2: Rekonstruktion von Graphstruktur und Leitfähigkeit
Sobald die Übergangsmatrix $P$ (oder die zugehörige Interaktionsmatrix $C$) bis auf die Eichklasse bekannt ist, wird die eigentliche Struktur des Graphen rekonstruiert.

• Blattknoten-Erkennung: Die Autoren nutzen die Eigenschaften der Distanzfunktion und der Übergangswahrscheinlichkeiten, um „Blattknoten" (Knoten mit genau einem Nachbarn) und deren Nachbarn zu identifizieren.
• Abstandsrekonstruktion: Durch die Analyse von Verhältnissen der Übergangswahrscheinlichkeiten können die Distanzen zwischen allen Knotenpaaren rekonstruiert werden.
• Leitfähigkeit: Aus der rekonstruierten Distanzmatrix und der Interaktionsmatrix lässt sich die Leitfähigkeit $\gamma$ bis auf einen konstanten Faktor bestimmen.

3. Schlüsselbeiträge und Ergebnisse

Haupttheorem (Theorem 1.2):
Unter bestimmten Admissibilitätsbedingungen (A1 und A2) an den Graphen (z.B. Existenz von mindestens zwei Blattknoten mit einer gewissen Exzentrizität) gilt:

1. Eindeutigkeit der Knotenanzahl: Aus den Daten $\Lambda_3(P)$ kann die Anzahl der Knoten $|X|$ eindeutig bestimmt werden.
2. Eichklasse: Die Daten bestimmen die Übergangsmatrix $P$ eindeutig bis auf die oben genannte Eichtransformation.
3. Rekonstruktion: Wenn die Übergangsmatrix $P$ selbst bekannt ist (d.h. wenn die Eichung fixiert ist, z.B. durch $P = \tilde{P}$), dann können die Kantenmenge $E$ und die Leitfähigkeit $\gamma$ (bis auf einen positiven Faktor) eindeutig rekonstruiert werden.

Charakterisierung der Daten (Theorem 1.3):

• Die Daten $\Lambda_3(P)$ sind notwendig und hinreichend, um die Eichklasse der Matrix $P$ zu bestimmen.
• Daten für $k > 3$ fügen keine neuen Informationen hinzu. Dies steht im Kontrast zu lokalen Random Walks, wo mehr Schritte nötig wären, um den gesamten Graphen zu „sehen".
• Dies offenbart eine neue nicht-lokale Eigenschaft: Durch die Möglichkeit langer Sprünge im fraktionalen Modell sind Informationen über den gesamten Graphen bereits in den ersten drei Schritten enthalten.

Gauge-Klasse Analyse (Abschnitt 5):
Die Autoren charakterisieren die Menge aller Matrizen, die die gleichen Daten liefern. Sie zeigen, dass diese Matrizen durch eine Transformation mit einer invertierbaren Matrix $A$ verbunden sind, die bestimmte stochastische Eigenschaften bewahren muss.

4. Bedeutung und Einordnung

• Diskretisierung des Calderón-Problems: Das Paper stellt einen wichtigen Schritt dar, um das fraktionale Calderón-Problem (ein inverses Problem für partielle Differentialgleichungen mit nicht-lokalen Operatoren) im Riemannschen Kontext zu verstehen. Der Graph dient als diskrete Approximation einer Mannigfaltigkeit.
• Nicht-Lokalität: Die Arbeit hebt hervor, wie sich nicht-lokale Operatoren (fraktionale Ableitungen) von lokalen Operatoren unterscheiden. Während bei lokalen Problemen die Beobachtbarkeit von entfernten Knoten von der Anzahl der Schritte abhängt, ist dies bei fraktionalen Walks durch die „Sprungwahrscheinlichkeiten" anders gelagert.
• Anwendungsbezug: Die Ergebnisse haben Implikationen für Anwendungen in der optischen Tomographie, Netzwerktopologie und der Modellierung anomaler Diffusion, wo oft nur partielle Messungen an der Oberfläche eines Systems möglich sind.
• Offene Fragen: Das Paper diskutiert die Stabilität der Rekonstruktion bei Messfehlern und die Übertragung der Ergebnisse auf kontinuierliche Riemannsche Mannigfaltigkeiten als zukünftige Forschungsziele.

Zusammenfassend beweist das Paper, dass die Kombination aus fraktionaler Dynamik und partiellen Beobachtungen auf Graphen ausreicht, um die zugrundeliegende Topologie und physikalischen Eigenschaften (Leitfähigkeit) des Systems vollständig zu rekonstruieren, wobei überraschenderweise nur sehr wenige Zeitschritte ($k=3$) für die vollständige Information benötigt werden.