A Bayesian approach to out-of-sample network reconstruction

Cet article présente une approche bayésienne qui exploite les snapshots passés de réseaux pour prédire leurs configurations futures et quantifier l'incertitude, surpassant ainsi les méthodes de prédiction de liens existantes lors de la reconstruction du marché interbancaire de 1999 à 2012.

L'essentiel

🕵️‍♂️ Le Détective des Réseaux : Comment prédire l'avenir d'un système complexe

Imaginez que vous êtes un détective privé. Votre mission ? Reconstruire la carte complète des relations entre des banques qui prêtent et empruntent de l'argent. Le problème ? Vous n'avez qu'une partie du puzzle. Vous voyez les gros mouvements d'argent, mais vous ne savez pas exactement qui parle à qui, ni qui est connecté à qui. C'est ce qu'on appelle la reconstruction de réseau.

Jusqu'à présent, les détectives (les scientifiques) regardaient une photo du réseau à un instant T, tentaient de deviner les liens manquants, puis jetaient cette photo pour en prendre une nouvelle le lendemain, recommençant tout à zéro. C'était inefficace : ils n'apprenaient rien de leur passé pour prédire le futur.

C'est là que les auteurs de cet article, Mattia Marzi et Tiziano Squartini, proposent une nouvelle méthode : une approche bayésienne.

1. L'Analogie du Météorologue vs. Le Météo du Jour J

Pour comprendre la différence, comparons deux façons de prédire la météo :

• L'ancienne méthode (Frequentiste) : Le météorologue regarde le ciel aujourd'hui à 8h00. Il dit : "Il y a 30% de chance de pluie." À 9h00, il regarde à nouveau le ciel et dit : "Il y a 40% de chance." Il ne se souvient pas de ce qu'il a vu à 8h00. Chaque prédiction est isolée.
• La nouvelle méthode (Bayésienne) : Le météorologue regarde le ciel à 8h00, mais il dit : "D'après mon expérience des jours précédents, il y a une forte probabilité qu'il pleuve. Donc, même si le ciel est un peu gris maintenant, je vais ajuster ma prédiction pour demain en me basant sur ce que je sais déjà."

En termes scientifiques, la méthode bayésienne utilise les données passées pour créer une "intuition" (appelée a priori) qui guide la prédiction du futur. Plus on a d'informations, plus l'intuition devient précise.

2. Le Problème du "Jeu de l'Oie" Financier

Les auteurs ont testé leur méthode sur le marché interbancaire italien (eMID), où les banques se prêtent de l'argent la nuit.

• Le défi : Les données sont partielles. On ne voit pas toutes les transactions.
• L'objectif : Prédire qui sera connecté à qui la semaine prochaine, en utilisant seulement les données de la semaine passée.

Ils ont créé deux modèles pour jouer à ce jeu :

1. Le Modèle "Tous Égaux" (BERM) : Imaginez une foule où tout le monde a la même chance de se parler. C'est simple, mais faux. Dans la réalité, certaines banques sont des géants (très connectées) et d'autres sont des souris (peu connectées).
2. Le Modèle "Fitness" (BFM) : C'est le modèle gagnant. Il reconnaît que chaque banque a sa propre "force" (son importance, sa taille). Il dit : "La banque A est très puissante, donc elle a plus de chances de se connecter à la banque B, même si on ne voit pas le lien directement."

3. La Magie de l'Auto-Entretien (Self-Sustained)

C'est le point le plus impressionnant de l'article.
Imaginez que vous devez prédire le temps qu'il fera pendant les 10 prochaines années, mais vous n'avez qu'un seul thermomètre pour la première semaine.

• La méthode classique : Elle échouerait. Elle a besoin de nouvelles données chaque jour.
• La méthode des auteurs : Elle fonctionne comme une boucle de rétroaction.
  1. Ils utilisent les données de 2001 pour prédire 2002.
  2. Au lieu d'attendre les vraies données de 2002 pour prédire 2003, ils utilisent leur propre prédiction de 2002 comme nouvelle base de données pour prédire 2003.
  3. Ils continuent ainsi, année après année.

C'est comme si vous appreniez à conduire en regardant un film, puis en conduisant vous-même en vous basant sur ce que vous avez "vu" dans le film, sans jamais toucher à la vraie route. Et devinez quoi ? Ça marche ! Leur modèle reste précis pendant des années, même sans nouvelles données réelles.

4. Les Résultats : Qui a gagné ?

En comparant leur méthode avec d'autres outils existants sur les données de 1999 à 2012 :

• Précision : Le modèle "Fitness" (BFM) a réussi à deviner non seulement le nombre total de liens, mais aussi qui était connecté à qui.
• Comparaison : Il a surpassé les méthodes classiques qui tentent de prédire les liens en utilisant des données complètes (ce qui est un avantage injuste, car dans la réalité, on n'a pas ces données complètes).
• Résilience : Même lors de la crise financière de 2008 (un moment chaotique où les réseaux changent radicalement), leur modèle a continué à fournir de bonnes prédictions, prouvant qu'il a bien compris la "structure" du système.

🎯 En résumé

Cet article nous dit que pour prédire l'avenir d'un réseau complexe (comme les banques, les réseaux sociaux ou la propagation d'un virus), il ne faut pas seulement regarder l'instant présent. Il faut apprendre du passé pour construire une "intuition" mathématique.

Leur méthode est comme un système immunitaire pour les données : elle utilise l'histoire pour se protéger contre l'incertitude du futur, permettant de reconstruire des cartes de relations invisibles avec une précision surprenante, même avec très peu d'informations.

C'est une victoire pour la science des réseaux : on peut désormais voir l'invisible, pas en devinant, mais en raisonnant logiquement sur ce que l'on sait déjà.

Résumé technique

1. Problématique

La reconstruction de réseaux est essentielle pour comprendre des systèmes allant de la finance à la biologie, où la structure complète du réseau est souvent partiellement observée. Les méthodes actuelles reposent généralement sur l'estimation des paramètres d'un modèle (comme les Graphes Aléatoires Exponentiels ou ERG) pour chaque instantané (snapshot) de manière indépendante.

• Limitation principale : Ces approches sont « intra-échantillon » (in-sample). Elles ajustent les paramètres aux données observées à l'instant $t$ pour décrire ce même instant $t$, mais ne fournissent aucune guidance pour prédire les configurations futures ($t+1$).
• Défi : Il manque un cadre formel pour propager l'incertitude d'une estimation de paramètre d'un instantané à l'autre et transformer les observations passées en une a priori informative pour le futur, permettant ainsi une reconstruction « hors échantillon » (out-of-sample) et auto-entretenue.

2. Méthodologie

Les auteurs proposent un cadre entièrement bayésien pour la reconstruction de réseaux, en transformant le Modèle de Configuration Binaire Non Dirigé (UBCM) et ses variantes en modèles probabilistes dynamiques.

A. Fondements Théoriques

Au lieu d'estimer un point unique pour les paramètres (via le maximum de vraisemblance), la méthode calcule la distribution prédictive postérieure :
$$P(A_{t+1}|A_t) = \int P(A_{t+1}|x) P(x|A_t) dx$$
où $x$ représente le paramètre latent du modèle, $A_t$ l'adjacence observée à l'instant $t$, et $P(x|A_t)$ la distribution postérieure du paramètre déduite des données passées.

B. Deux Modèles Implémentés

Les auteurs testent deux approches spécifiques :

1. Le Modèle Bayésien d'Erdős-Rényi (BERM) :

   • C'est un modèle homogène où tous les nœuds sont traités de manière égale.
   • La probabilité de lien $p$ est estimée.
   • Le prior est choisi comme une distribution Beta (conjuguée), ce qui permet une solution analytique. La distribution prédictive du nombre total de liens suit une loi Beta-Binomiale.

2. Le Modèle Bayésien de Fitness (BFM) :

   • C'est une version hétérogène basée sur le modèle de Gravité corrigé par la densité (dcGM).
   • Il intègre la « fitness » des nœuds (ici, la force $s_i$ dérivée des données pondérées) pour capturer l'hétérogénéité structurelle.
   • La probabilité de lien entre $i$ et $j$ est $p_{ij} = \frac{z s_i s_j}{1 + z s_i s_j}$, où $z$ est le paramètre global à estimer.
   • Estimation du Prior : Une approche de « prior empirique » est utilisée. La distribution de $z$ est estimée sur une fenêtre glissante de trois années passées (ajustée par une méthode jack-knife).
   • Intégration Numérique : Comme l'intégrale pour $P(A_{t+1}|A_t)$ n'est pas analytique, les auteurs utilisent la quadrature de Gauss-Hermite ou l'échantillonnage par tranches (slice sampling) dans l'espace logarithmique ($u = \ln z$) pour calculer les probabilités marginales des liens.

C. Procédure « Auto-entretenue » (Self-sustained)

L'innovation majeure est la capacité du modèle à fonctionner sans données topologiques supplémentaires après l'initialisation :

1. On utilise $A_0$ pour prédire $Q_1$ (la matrice de probabilités attendues).
2. On utilise $Q_1$ (et non $A_1$) pour mettre à jour le prior et prédire $Q_2$, et ainsi de suite.
3. Cela teste la capacité du modèle à retenir l'information structurelle et à propager l'incertitude dans le temps.

3. Contributions Clés

• Cadre Bayésien pour la Reconstruction Hors Échantillon : Première formulation permettant d'utiliser les observations passées comme prior pour prédire les états futurs d'un réseau, quantifiant simultanément l'incertitude.
• Auto-entretien de la Reconstruction : Démonstration qu'un modèle peut reconstruire l'évolution d'un réseau sur de longues périodes en n'utilisant que la distribution prédictive de l'étape précédente, sans accès aux données réelles intermédiaires.
• Supériorité du Modèle de Fitness (BFM) : Preuve que l'hétérogénéité des nœuds (via la fitness) est cruciale pour prédire non seulement le nombre total de liens, mais aussi la distribution des degrés (connectivité par nœud).

4. Résultats

Les méthodes ont été testées sur les données du marché électronique des dépôts interbancaires (eMID) de 1999 à 2012.

• Précision Globale :
  • Les deux modèles (BERM et BFM) prédisent avec précision le nombre total de liens ($L$).
  • Le BFM surpasse nettement le BERM pour la prédiction des degrés des nœuds ($k_i$). Le BERM, étant homogène, échoue à capturer l'hétérogénéité des connexions bancaires.
• Métriques de Performance :
  • Le BFM double les scores de précision (PPV) et de rappel (TPR) par rapport au BERM et aux benchmarks probabilistes classiques.
  • L'erreur relative moyenne (ARE) sur les degrés est significativement plus faible avec le BFM.
• Comparaison Intra vs Hors Échantillon :
  • Même comparé à une reconstruction « intra-échantillon » (dcGM) qui a l'avantage d'utiliser le nombre réel de liens de l'instant $t$ pour calibrer le modèle, le prédicteur bayésien « hors échantillon » obtient des performances quasi équivalentes (voire supérieures sur 54% des snapshots pour le TPR).
• Robustesse Temporelle :
  • Dans le régime « auto-entretenu », les erreurs s'accumulent mais restent faibles. La divergence de Kullback-Leibler entre la matrice réelle et la matrice prédite reste faible, confirmant que la structure du réseau est bien capturée par la distribution prédictive.
  • Le modèle résiste bien aux chocs (comme la crise de 2008), bien que l'erreur augmente temporairement, indiquant un changement structurel temporaire.

5. Signification et Impact

• Prédictivité des Réseaux Complexes : Cette approche démontre qu'il est possible de prédire l'évolution de la topologie d'un réseau complexe à partir de données partielles et passées, en exploitant les régularités structurelles plutôt que de simplement ajuster des paramètres à chaque instant.
• Applications Financières : Dans le contexte des réseaux bancaires, cela permet de surveiller les risques systémiques et la propagation des chocs même lorsque les données complètes ne sont pas disponibles en temps réel.
• Généralité : La méthode est applicable à tout réseau dynamique où l'on dispose de contraintes agrégées (comme les forces des nœuds) et où l'hétérogénéité structurelle est importante.
• Outils : Les auteurs ont rendu disponible le package Python OR4CLE pour faciliter l'application de ces algorithmes.

En résumé, cet article marque une avancée significative en passant d'une reconstruction statique et descriptive à une reconstruction dynamique, prédictive et probabiliste, capable de s'auto-alimenter dans le temps.