Dynamic sparse graphs with overlapping communities

1. Problématique et Contexte

La détection de communautés dans les réseaux est une tâche centrale en modélisation statistique, visant à identifier des groupes de nœuds partageant des comportements similaires ou des motifs de connectivité. Cependant, la plupart des modèles existants souffrent de limitations majeures lorsqu'ils sont appliqués aux réseaux réels :

• Dynamique temporelle : Les réseaux réels (sociaux, biologiques, économiques) évoluent dans le temps (apparition/disparition de liens, fusion/split de communautés), ce que les modèles statiques ne capturent pas.
• Clairsemé et Lois de puissance : De nombreux réseaux réels sont clairsemés (le nombre d'arêtes croît de manière sous-quadratique par rapport au nombre de nœuds) et présentent des distributions de degrés à queue lourde (loi de puissance), caractérisés par quelques nœuds très connectés et beaucoup de nœuds peu connectés.
• Chevauchement des communautés : Les entités appartiennent souvent à plusieurs communautés simultanément (membres mixtes).
• Limitation des modèles existants : Les modèles de blocs stochastiques (SBM) dynamiques classiques et les modèles de membres mixtes (MMSB) supposent souvent une densité constante ou échouent à capturer simultanément la clairsemé, la loi de puissance et l'évolution temporelle des affiliations. De plus, l'hypothèse d'échangeabilité classique conduit inévitablement à des graphes denses ou vides.

L'objectif de cet article est de proposer un modèle capable de gérer simultanément ces quatre caractéristiques : dynamique temporelle, clairsemé, distribution de degrés en loi de puissance, et communautés chevauchantes.

2. Méthodologie : Le modèle dynSNetOC

Les auteurs proposent un modèle bayésien non-paramétrique nommé dynSNetOC (Dynamic Sparse Network with Overlapping Communities).

A. Représentation par Processus Ponctuel

Le modèle s'appuie sur le cadre de Caron & Fox (2017) où le graphe est représenté comme un processus ponctuel sur un plan, plutôt que par une matrice d'adjacence fixe. Cela permet de modéliser des graphes infinis et de gérer la clairsemé via des mesures aléatoires complètement aléatoires (CRM - Completely Random Measures).

B. Construction du Modèle

Le modèle repose sur des vecteurs de CRM couplés par un processus de Markov latent :

1. Mesures de base : Pour chaque communauté $k \in \{1, \dots, p\}$, on définit une mesure aléatoire $W^{(t)}_k$ à l'instant $t$. Ces mesures sont construites à partir d'une mesure de base $W_0$ (tirée d'un processus de Gamma généralisé, GGP) et de scores d'affiliation dynamiques $\beta^{(t)}_{ki}$.
2. Affiliations dynamiques : Les scores d'affiliation $\beta^{(t)}_{ki}$ (représentant la proportion d'appartenance du nœud $i$ à la communauté $k$) évoluent dans le temps selon un processus de Markov. Cette évolution est pilotée par des variables d'augmentation $\gamma^{(t)}_{ki}$, assurant que la distribution marginale des scores reste inchangée (stationnaire) tout en introduisant une dépendance temporelle contrôlée par le paramètre $\psi$.
3. Génération des liens : Le nombre d'arêtes entre deux nœuds $i$ et $j$ à l'instant $t$ suit une distribution de Poisson dont l'intensité dépend du produit des poids latents des nœuds, eux-mêmes fonction des scores de communautés. Cela permet une factorisation de Poisson non-négative.
4. Gestion de la clairsemé : L'utilisation d'un processus de Gamma généralisé (GGP) avec un paramètre $\sigma \in (0, 1)$ garantit que le graphe généré est clairsemé et suit une loi de puissance pour la distribution des degrés.

C. Inférence Approximative

L'inférence exacte sous un GGP à activité infinie est computationnellement coûteuse. Les auteurs utilisent une approximation par la distribution etBFRY (exponentially tilted BFRY), proposée par Lee et al. (2023), qui converge vers le GGP lorsque le niveau de troncature augmente.

• L'inférence est réalisée via un algorithme Hamiltonian Monte Carlo (HMC) avec l'algorithme NUTS (No-U-Turn Sampler), implémenté dans le langage probabiliste NumPyro.
• Cela permet d'explorer efficacement l'espace des paramètres de haute dimension et d'obtenir des intervalles de crédibilité pour les affiliations temporelles.

3. Contributions Clés

1. Modélisation Unifiée : C'est le premier modèle capable de capturer simultanément la dynamique temporelle, la clairsemé, les lois de puissance et les communautés chevauchantes.
2. Généralisation Théorique : Le modèle généralise les modèles de blocs stochastiques à membres mixtes (MMSB) existants vers le régime clairsemé et à loi de puissance, en s'appuyant sur la théorie des CRM.
3. Résultats Asymptotiques : Les auteurs établissent des résultats théoriques prouvant que le modèle génère des graphes clairsemés ($E \sim N^{2/(1+\sigma)}$) avec une distribution de degrés en loi de puissance (exposant $1+\sigma$) pour $\sigma \in (0,1)$.
4. Interprétabilité Temporelle : Le modèle permet de suivre l'évolution des affiliations des nœuds (entrées, sorties, changements de communauté) et la fusion/split des communautés au fil du temps.

4. Résultats Expérimentaux

Les auteurs valident le modèle sur des données synthétiques et réelles.

A. Données Synthétiques

• Le modèle récupère avec précision les paramètres de vraisemblance (poids de sociabilité et scores d'affiliation).
• Les intervalles de crédibilité postérieurs (95%) couvrent correctement les valeurs réelles.
• La distribution des degrés prédite correspond parfaitement à la distribution empirique (loi de puissance), confirmant la capacité du modèle à reproduire la structure clairesemée.

B. Données Réelles : Reuters Terrorist Dataset

Le modèle est appliqué à un réseau de co-occurrence de mots tiré des articles de Reuters concernant les attentats du 11 septembre 2001 et les semaines suivantes (6 semaines).

• Dynamique des thèmes : Le modèle identifie l'évolution sémantique des communautés. Par exemple :
  • La communauté « Attaque » commence par se concentrer sur le 11/09 (WTC, avion) puis intègre progressivement les thèmes de la guerre en Afghanistan.
  • La communauté « Sécurité » évolue de la sécurité aérienne vers la sécurité sanitaire (anthrax) et nationale.
  • L'émergence de la communauté « Anthrax » au milieu de la période est correctement détectée.
• Comparaison avec les concurrents :
  • SNetOC (Statique) : En agrégeant les données, il perd toute information temporelle et ne peut pas suivre l'évolution des thèmes.
  • SNetOC (Hebdomadaire) : En ajustant un modèle statique par semaine, il ne capture pas la persistance des communautés ni les transitions fluides.
  • dynSBM (Bloc dynamique simple) : Échoue à capturer la distribution de degrés (mauvaise adéquation) et ne détecte pas de structure thématique cohérente.
  • dMMSB (Membres mixtes dynamique) : Bien que meilleur que le dynSBM, il échoue à modéliser correctement la structure des communautés sur ce jeu de données clairsemé, tendant à regrouper tous les nœuds dans une seule communauté basée uniquement sur le degré.

5. Signification et Conclusion

Ce travail représente une avancée significative dans la modélisation des réseaux temporels. En combinant la théorie des processus ponctuels pour la clairsemé et les processus de Markov pour la dynamique, dynSNetOC offre un cadre flexible et interprétable pour analyser l'évolution des structures complexes.

L'application aux données de presse montre que le modèle peut révéler des nuances temporelles (comme le glissement sémantique des mots-clés) que les approches statiques ou les modèles dynamiques classiques (basés sur des matrices d'adjacence denses) ne peuvent pas détecter. Cela ouvre la voie à une meilleure compréhension de la diffusion de l'information, de l'évolution des épidémies ou des changements dans les réseaux sociaux, en particulier dans des contextes où la rareté des liens et l'hétérogénéité des degrés sont prédominantes.

Les auteurs suggèrent comme travail futur l'intégration de covariables et l'estimation automatique du nombre de communautés.