An inverse problem for fractional random walks on finite graphs

1. Problématique et Contexte

L'article étudie un problème inverse géométrique sur un graphe fini et connexe $G = (X, E)$, où les sommets sont munis d'une fonction de conductivité $\gamma : X \to (0, \infty)$.

• Données observées : On dispose d'une séquence d'observations partielles d'une marche aléatoire fractionnaire sur le graphe. Ces observations sont limitées à un sous-ensemble fixe de sommets observables $B \subseteq X$.
• Nature de la marche : Contrairement aux marches aléatoires classiques (locaux, sauts uniquement entre voisins), cette marche est fractionnaire (non locale). Elle permet des « longs sauts » entre n'importe quels sommets $x, y$, avec une probabilité de transition $P(x, y)$ qui décroît comme une puissance fractionnaire de la distance géodésique $d_G(x, y)$ le long du graphe.
• Dépendance : La probabilité de transition dépend de la conductivité $\gamma$ selon la formule :
  $$P(x, y) := \frac{1}{m(x)} \frac{\gamma^{1/2}(x)\gamma^{1/2}(y)}{d_G(x, y)^\alpha}$$
  où $\alpha > 0$ est un paramètre fixe et connu, et $m(x)$ est une constante de normalisation.
• Objectif : Reconstruire à partir des données partielles :
  1. Le nombre total de sommets $|X|$.
  2. L'ensemble des arêtes $E$ (la structure du graphe).
  3. La conductivité $\gamma$ (à un facteur multiplicatif positif près).

Ce travail s'inscrit dans la continuité du problème de Calderón fractionnaire, visant à comprendre les opérateurs fractionnaires dans un cadre riemannien en passant par une discrétisation sur des graphes.

2. Méthodologie

La démarche de l'article repose sur une analyse algébrique rigoureuse des matrices de transition et sur des propriétés combinatoires des graphes.

A. Modélisation des données

Les données sont formalisées par une séquence de matrices $\Lambda_\omega(P) = \{ (P^k)_{11} \}_{k \in \mathbb{N}}$, où $P$ est la matrice de transition globale et $(P^k)_{11}$ représente les probabilités de transition en $k$ étapes entre les sommets observables $B$. Une version réduite $\Lambda_K(P)$ (jusqu'à $K$ étapes) est également considérée.

La matrice $P$ est partitionnée selon les ensembles observables ($B$, taille $N$) et non observables ($X \setminus B$, taille $M$) :
$$P = \begin{pmatrix} P_{11} & P_{12} \\ P_{21} & P_{22} \end{pmatrix}$$

B. Caractérisation de l'ensemble des solutions (Gauge Class)

Les auteurs démontrent que les données $\Lambda_3(P)$ (probabilités jusqu'à 3 sauts) suffisent à caractériser l'ensemble des matrices de transition compatibles.

• Ils établissent que si deux matrices $P$ et $\tilde{P}$ produisent les mêmes données $\Lambda_3(P) = \Lambda_3(\tilde{P})$, alors elles appartiennent à la même classe de jauge.
• Il existe une matrice inversible $A \in GL_M$ telle que :
  $$P = (I_N \oplus A) \tilde{P} (I_N \oplus A^{-1})$$
• Surprise non locale : Les données pour $k > 3$ sont redondantes. Contrairement aux marches classiques où l'information se propage lentement, la nature non locale de la marche fractionnaire permet de récupérer toute l'information structurelle en seulement 3 étapes.

C. Reconstruction de la structure et de la conductivité

Une fois la classe de jauge identifiée, le problème se réduit à extraire la structure du graphe et la conductivité à partir d'une matrice de transition $P$ (ou de son équivalent $C$ avant normalisation).

• Hypothèses d'admissibilité : Le graphe doit satisfaire deux conditions (A1 et A2) garantissant que certaines sous-matrices sont de rang plein et que le graphe possède suffisamment de « feuilles » (sommets de degré 1) éloignées.
• Identification des feuilles : En analysant les rapports de distances déduits des probabilités de transition, les auteurs montrent comment identifier les feuilles du graphe et leurs voisins uniques.
• Récupération de $E$ et $\gamma$ : Une fois les feuilles identifiées, la structure complète des arêtes $E$ peut être reconstruite. La conductivité $\gamma$ est ensuite récupérée à partir des poids des arêtes, mais uniquement à un facteur scalaire global près (car la normalisation de la marche aléatoire masque l'échelle absolue de $\gamma$).

3. Résultats Principaux

Théorème 1.2 (Unicité et Reconstruction)

Pour un graphe admissible $G$ et une conductivité inconnue $\gamma$ :

1. Cardinalité : Le nombre de sommets $|X|$ est déterminé de manière unique par les données $\Lambda_3(P)$.
2. Classe de jauge : Les données déterminent la matrice de transition $P$ à une action de groupe près (la classe de jauge décrite ci-dessus).
3. Reconstruction : Si la matrice de transition $P$ est connue (ou si les deux graphes ont la même matrice de transition), alors :
   • L'ensemble des arêtes $E$ est unique.
   • La conductivité $\gamma$ est unique à un facteur multiplicatif positif près.

Théorème 1.3 (Caractérisation des données)

Ce théorème prouve que l'égalité des données sur 3 étapes ($\Lambda_3(P) = \Lambda_3(\tilde{P})$) est équivalente à l'égalité des données complètes ($\Lambda_\omega(P) = \Lambda_\omega(\tilde{P})$) et implique l'existence de la transformation de jauge. Cela établit que 3 étapes sont nécessaires et suffisantes pour la reconstruction, un résultat contre-intuitif pour les marches aléatoires.

4. Contributions Clés

1. Première étude inverse sur les marches fractionnaires : C'est l'un des premiers travaux traitant d'un problème inverse complet (structure + paramètre) pour des opérateurs fractionnaires sur des graphes finis.
2. Phénomène de redondance des données (Non-localité) : La découverte que les données de marche aléatoire au-delà de 3 sauts n'apportent aucune information nouvelle pour la reconstruction est une propriété surprenante liée à la nature non locale de l'opérateur fractionnaire. Dans le cas classique (local), il faudrait observer des temps infinis pour atteindre tous les sommets.
3. Méthode de reconstruction combinatoire : Développement d'un algorithme basé sur l'analyse des rapports de distances et de la géométrie des feuilles pour reconstruire la topologie du graphe sans connaissance a priori des arêtes.
4. Lien vers le problème de Calderón : L'article fournit une étape préliminaire cruciale pour l'étude du problème de Calderón fractionnaire sur des variétés riemanniennes, en utilisant des graphes comme approximations discrètes.

5. Signification et Perspectives

• Signification théorique : Ce travail démontre la puissance des opérateurs fractionnaires pour la résolution de problèmes inverses, même dans des cadres discrets. Il met en lumière la différence fondamentale entre les processus locaux et non locaux en termes de propagation de l'information.
• Applications potentielles : Bien que formulé sur des graphes, ce modèle a des résonances avec la tomographie optique, les réseaux de neurones, et les réseaux électriques, où des mesures partielles doivent permettre de déduire la structure interne et les propriétés de conduction.
• Questions ouvertes :
  • La stabilité de la reconstruction face au bruit dans les données (problème de régularité).
  • L'extension de ces résultats au cas continu sur des variétés riemanniennes (le but ultime des auteurs).
  • La relation précise entre cette propriété de reconstruction en 3 étapes et la propriété d'extension unique (Unique Continuation Property) des opérateurs fractionnaires continus.

En résumé, cet article établit un cadre rigoureux pour la reconstruction de graphes et de conductivités via des marches aléatoires non locales, prouvant que des observations limitées dans le temps suffisent à révéler la structure globale grâce à la nature « sautante » de la dynamique fractionnaire.