An inverse problem for fractional random walks on finite graphs

1. Il Problema

L'articolo studia un problema inverso geometrico su un grafo finito e connesso $G = (X, E)$, dove è definita una funzione di conduttività $\gamma: X \to (0, \infty)$.
L'obiettivo è recuperare le seguenti quantità a partire da dati parziali:

• Il numero totale di vertici $|X|$.
• L'insieme degli archi $E$ (la struttura del grafo).
• La funzione di conduttività $\gamma$ (a meno di un fattore moltiplicativo positivo).

Il modello di osservazione:
Si considera un random walk frazionario (o passeggiata aleatoria frazionaria) $H^{x_0}_t$ sul grafo, che parte da un vertice iniziale $x_0$. A differenza delle passeggiate aleatorie classiche (che permettono salti solo tra vertici adiacenti), questo modello consente salti lunghi (long jumps) tra vertici non necessariamente adiacenti.
La probabilità di transizione $P(x, y)$ tra due vertici distinti $x, y$ dipende dalla conduttività $\gamma$ e dalla distanza lungo il grafo $d_G(x, y)$ secondo la formula:
$$P(x, y) := \frac{1}{m(x)} \frac{\gamma^{1/2}(x)\gamma^{1/2}(y)}{d_G(x, y)^\alpha}$$
dove $\alpha > 0$ è un parametro frazionario noto e $m(x)$ è una costante di normalizzazione.

Dati disponibili:
Le osservazioni sono parziali: si conoscono le posizioni del camminatore aleatorio solo su un sottoinsieme fisso e osservabile di vertici $B \subseteq X$. I dati consistono nella sequenza di matrici che descrivono le probabilità di transizione tra vertici in $B$ dopo $k$ passi, per $k=1, 2, \dots$.

2. Metodologia

Gli autori adottano un approccio che combina teoria dei grafi, algebra lineare e calcolo vettoriale non locale.

• Rappresentazione algebrica dei dati:
  La matrice di transizione $P$ viene partizionata in blocchi rispetto all'insieme osservabile $B$ (dimensione $N$) e l'insieme non osservabile $X \setminus B$ (dimensione $M$):
  $$P = \begin{pmatrix} P_{11} & P_{12} \\ P_{21} & P_{22} \end{pmatrix}$$
  I dati osservabili corrispondono ai blocchi $(P^k)_{11}$ per $k \in \mathbb{N}$.

• Analisi della classe di gauge:
  Viene dimostrato che i dati osservabili non determinano univocamente la matrice $P$, ma piuttosto una classe di gauge di matrici. Due matrici $P$ e $\tilde{P}$ producono gli stessi dati osservabili se e solo se sono legate da un'azione di gruppo specifica (simile a una coniugazione parziale).

• Ridondanza dei dati:
  Un risultato cruciale della metodologia è la dimostrazione che i dati relativi a salti superiori a 3 passi ($k > 3$) sono ridondanti. Le informazioni contenute in $\Lambda_3(P)$ (dati fino a 3 passi) sono sufficienti per caratterizzare l'intera classe di gauge. Questo è un fenomeno non locale sorprendente, poiché nella passeggiata classica i dati a 3 passi non conterrebbero informazioni su vertici distanti più di 3 unità.

• Ricostruzione della struttura:
  Una volta identificata la classe di gauge, gli autori utilizzano le proprietà specifiche delle matrici di transizione frazionarie (in particolare la relazione tra i vertici "foglia" e i loro vicini) per recuperare la struttura del grafo e la conduttività.

3. Contributi Chiave e Risultati Principali

A. Caratterizzazione dei Dati (Teorema 1.3)

Il primo risultato fondamentale è la caratterizzazione dell'insieme di tutte le matrici di transizione compatibili con i dati osservabili.

• Se $\Lambda_3(P) = \Lambda_3(\tilde{P})$, allora esiste una matrice invertibile $A$ tale che $P$ e $\tilde{P}$ sono legati da un'azione di gruppo:
  $$P = (Id_N \oplus A) \tilde{P} (Id_N \oplus A^{-1})$$
• Questo implica che i dati determinano univocamente la matrice $P$ solo a meno di questa trasformazione di gauge.
• Non località: La sufficienza di $k=3$ è dovuta alla natura non locale dell'operatore frazionario, che permette di "vedere" l'intera struttura del grafo in pochi passi, a differenza del caso locale.

B. Unicità e Ricostruzione (Teorema 1.2)

Sotto ipotesi di admissibilità del grafo (che garantiscono che la matrice $P_{12}$ abbia rango pieno e che il grafo abbia foglie sufficientemente distanti), gli autori dimostrano:

1. Ricostruzione della cardinalità: Il numero di vertici $|X|$ può essere calcolato direttamente dai dati.
2. Ricostruzione della struttura: Se la matrice di transizione $P$ è nota (o se si assume che due grafi abbiano la stessa matrice $P$), allora l'insieme degli archi $E$ e la conduttività $\gamma$ sono univocamente determinati (a meno di un fattore scalare positivo per $\gamma$).
3. Ridondanza: Non è necessario osservare passi oltre il terzo per ottenere informazioni aggiuntive utili alla ricostruzione.

C. Proprietà della Classe di Gauge (Sezione 5)

Gli autori analizzano le condizioni necessarie affinché una matrice nella classe di gauge corrisponda effettivamente a un random walk fisico (cioè derivi da una matrice di interazione simmetrica e positiva). Viene mostrato che la conduttività può essere recuperata solo a meno di un fattore moltiplicativo globale, poiché le matrici $C$ e $\lambda C$ generano la stessa matrice di probabilità $P$.

D. Algoritmo di Ricostruzione della Struttura (Teorema 6.1)

Viene presentato un metodo esplicito per recuperare l'insieme degli archi $E$ e le funzioni di conduttività partendo dalla conoscenza della matrice di interazione (a meno di fattori scalari). L'algoritmo si basa sull'analisi dei rapporti di distanze tra vertici, sfruttando in modo critico la presenza di vertici foglia (vertici con un solo vicino) e le loro proprietà di eccentricità.

4. Significato e Implicazioni

• Ponte verso il caso continuo: Questo lavoro rappresenta un primo passo fondamentale verso lo studio del problema inverso di Calderón frazionario in contesti Riemanniani. L'articolo suggerisce che gli operatori frazionari su varietà possono essere approssimati come limiti continui di random walk non locali su grafi, fornendo un approccio discretizzato per studiare problemi di conduttività frazionaria.
• Nuova proprietà non locale: La dimostrazione che i dati a 3 passi sono sufficienti per caratterizzare l'intero sistema evidenzia una proprietà di unicità di continuazione (unique continuation) intrinseca agli operatori frazionari su grafi, che non esiste nel caso delle passeggiate aleatorie classiche (dove l'informazione si propaga solo localmente).
• Applicazioni: Il lavoro ha rilevanza per campi come la tomografia ottica, le reti neurali e l'analisi di reti complesse, dove la conoscenza della topologia e dei pesi interni è cruciale ma spesso non accessibile direttamente.
• Limiti e Prospettive: Gli autori notano che le condizioni di admissibilità (A1 e A2) sono sufficienti ma non è ancora noto se siano necessarie. Il lavoro apre la strada a future ricerche sulla stabilità dei dati (come piccoli errori di misura influenzano la ricostruzione) e sull'estensione a varietà Riemanniane continue.

In sintesi, il paper risolve un problema inverso complesso su grafi discreti, dimostrando che la natura non locale dei salti frazionari permette di recuperare la topologia e i pesi del grafo con dati parziali e limitati nel tempo, offrendo nuovi strumenti teorici per l'analisi di operatori frazionari.