Markov Chains and Random Walks with Memory on Hypergraphs: A Tensor-Based Approach

1. Problématique

Les chaînes de Markov classiques et les marches aléatoires sur les graphes reposent sur deux hypothèses restrictives :

1. Interactions par paires : Les interactions ne se produisent qu'entre deux nœuds.
2. Absence de mémoire (Markovien) : La transition future dépend uniquement de l'état présent, ignorant l'historique.

Cependant, de nombreux systèmes complexes (réseaux sociaux, voies biochimiques, réseaux neuronaux) violent ces hypothèses. Ils présentent des structures d'ordre supérieur (interactions de groupe via des hyperarêtes) et des effets de mémoire (l'ordre des états passés influence le futur). L'absence de cadre unifié pour modéliser simultanément ces deux aspects conduit à des caractérisations erronées des processus de diffusion, de classement et de contrôle. Les approches existantes traitent soit la mémoire (avec des formulations tensorielles algébriquement lourdes), soit les hypergraphes (sans mémoire), mais ne les combinent pas.

2. Méthodologie

Les auteurs proposent un cadre unifié basé sur les tenseurs pour modéliser les chaînes de Markov à mémoire et les marches aléatoires sur les hypergraphes.

• Représentation Tensorielle :

  • Ils introduisent un tenseur apparié d'ordre pair (even-order paired tensor). Ce tenseur relie les dynamiques « repliées » (l'état mémoire) et « dépliées » (l'évolution linéaire).
  • Chaque transition guidée par la mémoire est représentée comme un mouvement à travers une hyperarête dirigée : la queue ordonnée encode la séquence des états passés, et la tête spécifie l'état suivant.
  • L'opération clé est le produit d'Einstein ($A * B$), qui généralise la multiplication matricielle aux tenseurs d'ordre supérieur.
  • Une application de dépliement (unfolding) transforme le tenseur apparié en une matrice standard, permettant d'utiliser l'algèbre linéaire classique pour l'analyse.

• Modélisation :

  • Temps discret : La dynamique est décrite par un tenseur de transition d'ordre $m$ (où $m$ est la profondeur de mémoire). Le processus est formulé comme une itération linéaire sur un tenseur de distribution conjointe via le produit d'Einstein.
  • Temps continu : Ils définissent un tenseur de flux d'entrée et un opérateur de flux de sortie diagonal. L'évolution suit une équation de Kolmogorov forward généralisée.
  • Réduction non linéaire : Pour les systèmes continus, ils appliquent une fermeture de type « champ moyen » ($\Pi \approx x^{\otimes (m-1)}$), réduisant le système linéaire de dimension $n^{m-1}$ à un système non linéaire de dimension $n$ (analogue à un Laplacien d'ordre supérieur).

3. Contributions Clés

1. Formulation Tensorielle Appariée : Proposition d'une formulation explicite pour les chaînes de Markov à mémoire arbitraire (profondeur $m$) utilisant des tenseurs appariés d'ordre pair, permettant un dépliement systématique pour tout $m \ge 2$.
2. Extension au Temps Continu et Réduction : Développement d'un modèle non linéaire de basse dimension pour les chaînes de Markov continues à mémoire, avec une analyse complète de la stabilité et du comportement asymptotique.
3. Marches Aléatoires Mémoire-Sensibles sur Hypergraphes : Définition d'une nouvelle classe de marches aléatoires où les hyperarêtes codent des transitions de mémoire ordonnées. Cela crée un modèle de diffusion qui capture naturellement à la fois la structure d'ordre supérieur et les effets temporels.

4. Résultats Principaux

• Convergence et États Stationnaires (Temps Discret) :

  • En utilisant le théorème de Perron-Frobenius pour les tenseurs, ils démontrent que si le tenseur apparié est $U$-primitif, il existe un unique tenseur propre $U$ positif associé à la valeur propre dominante $\lambda = 1$.
  • La distribution conjointe des états converge vers cet état stationnaire unique. La distribution marginale du système original est obtenue par somme des bords du tenseur stationnaire.
  • Le taux de convergence est déterminé par le module de la deuxième plus grande valeur propre $U$.

• Analyse du Temps Continu :

  • Ils établissent l'existence d'une distribution stationnaire unique sous des conditions d'irréductibilité.
  • Pour le modèle réduit non linéaire ($\dot{x} = L(x^{m-1})$), ils prouvent la positivité du système et la conservation de la masse.
  • Sous une condition de détail d'équilibre d'ordre supérieur (liée à la symétrie du tenseur de flux), ils démontrent la convergence globale vers un équilibre proportionnel à un vecteur positif $x^*$, en utilisant une fonction de Lyapunov.

• Application aux Hypergraphes :

  • L'application aux hypergraphes montre que les marches à mémoire ne peuvent pas être réduites à des marches sur un graphe projeté (pairwise).
  • Exemple illustratif : Sur un hypergraphe donné, une marche à mémoire peut se diviser en classes communicantes fermées (dépendant de l'état initial), alors qu'une marche classique sur le graphe projeté associé aurait une distribution stationnaire unique. Cela révèle des comportements de diffusion inaccessibles aux approches sans mémoire.
  • Les simulations montrent que l'approximation non linéaire (Laplacien d'ordre supérieur) correspond très étroitement à la dynamique exacte du système déplié, tant pour les transitoires que pour l'état stationnaire.

5. Signification et Impact

Ce travail fournit un outil mathématique rigoureux et général pour étudier la dynamique des réseaux complexes où l'histoire et les interactions de groupe sont cruciales.

• Théorique : Il unifie deux domaines séparés (chaînes de Markov à mémoire et marches sur hypergraphes) sous un seul formalisme tensoriel, résolvant le problème de la complexité algébrique des formulations précédentes.
• Pratique : Il offre des méthodes analytiques (valeurs propres, convergence) et des modèles réduits (systèmes non linéaires de basse dimension) pour simuler et analyser des systèmes réels comme la diffusion d'informations dans les réseaux sociaux, les réactions biochimiques multi-moléculaires ou les motifs temporels neuronaux.
• Perspectives : Cette approche ouvre la voie à l'étude de la stabilité des équilibres multiples, des mises à jour stratégiques dans des jeux multi-joueurs et de l'analyse de réseaux hypergraphiques hétérogènes.