Community-Size Biases in Statistical Inference of Communities in Temporal Networks

Résumé Technique : Biais de Taille de Communauté dans l'Inférence Statistique des Communautés dans les Réseaux Temporels

Énoncé du Problème
Dans l'analyse des réseaux temporels, les chercheurs emploient fréquemment l'inférence statistique pour détecter l'évolution des communautés — des ensembles de nœuds densément connectés. Un problème critique, bien que souvent négligé, dans ce domaine est le biais inhérent aux modèles génératifs utilisés pour assigner les appartenances aux communautés au fil du temps. Les auteurs identifient que les approches standards, qui reposent soit sur une distribution uniforme sur les assignations de communauté, soit sur des processus de Markov en temps discret, biaisent systématiquement l'inférence contre les communautés ayant un nombre de nœuds très grand ou très petit. Plus précisément, ces modèles ont tendance à produire des distributions de taille de communauté qui deviennent de plus en plus « localisées » (concentrées autour de tailles modérées) à mesure que le réseau temporel évolue. Par conséquent, les méthodes d'inférence statistique utilisant ces modèles génératifs sont peu performantes lorsqu'elles tentent d'identifier des communautés qui s'écartent significativement de la taille moyenne, une caractéristique commune des réseaux réels.

Méthodologie
L'article étudie ce phénomène en représentant les réseaux temporels comme des réseaux multicouches, où chaque couche correspond à un pas de temps discret. Les auteurs analysent la performance de trois classes distinctes de modèles génératifs pour les assignations de communautés ($P(g)$) :

1. Distribution Uniforme : Assigne les étiquettes de communauté de manière indépendante et uniforme de façon aléatoire pour chaque nœud-couche.
2. Processus de Markov en Temps Discret : Modélise l'évolution des assignations de communauté où l'étiquette d'un nœud à l'instant $\ell$ dépend de manière probabiliste de son étiquette à l'instant $\ell-1$. Les auteurs examinent et implémentent spécifiquement les priors de Yang et al. [65] et de Bazzi et al. [4], qui utilisent des noyaux de transition et des paramètres de paresse (laziness parameters).
3. Prior de Division de Comptes Échangeable par Couche (LECS - Layerwise-Exchangeable Count-Splitting) : Une nouvelle approche proposée par les auteurs. Au lieu de mettre à jour chaque nœud individuellement en fonction de son état précédent, le prior LECS met à jour les comptes des nœuds au sein des communautés. Il traite les nœuds au sein d'une communauté comme interchangeables (échangeables) et emploie un processus en deux étapes :
   • Rétention Géométrique : Le nombre de nœuds restant dans une communauté est tiré d'une distribution géométrique tronquée.
   • Étiquetage Microcanonique : Les nœuds « mobiles » restants sont réassignés à d'autres communautés en échantillonnant uniformément une composition faible des nœuds restants, suivi d'une assignation uniforme des étiquettes.

Pour évaluer ces modèles, les auteurs utilisent un cadre bayésien pour échantillonner de la distribution a posteriori $P(g|A)$ en utilisant l'échantillonnage de Gibbs augmenté par des permutations d'étiquettes multicouches (multilayer label swaps) pour échapper aux extrema locaux. Ils quantifient la « localisation » des distributions de taille de communauté à l'aide du Rapport de Participation Inverse (IPR), où un IPR plus élevé indique une distribution plus localisée (biaisée).

Principales Contributions

• Identification du Biais : Les auteurs démontrent que les distributions uniformes et les processus de Markov standards en temps discret conduisent à des distributions de taille de communauté qui deviennent de plus en plus localisées au fil du temps. Cette localisation implique une faible probabilité de générer ou d'inférer correctement des communautés de tailles très petites ou très grandes lors des étapes temporelles ultérieures.
• Nouveau Modèle Génératif (LECS) : Ils introduisent le prior de Division de Comptes Échangeable par Couche (LECS). En mettant à jour les assignations de communauté sur la base des comptes agrégés de la couche précédente plutôt que sur les transitions individuelles des nœuds, ce modèle atténue l'accumulation du biais de localisation.
• Garanties Théoriques : L'article fournit des résultats théoriques (Théorème 4.1 et Corollaire 4.2) prouvant que, dans la limite de couches infinies, le prior LECS avec une probabilité de rétention fixe produit une distribution stationnaire nettement moins localisée que les modèles de processus de Markov, particulièrement pour les tailles de communauté qui ne sont pas extrêmes.
• Implémentation Algorithmique : Les auteurs détaillent les algorithmes d'échantillonnage de la distribution a posteriori requis pour ces modèles, y compris la dérivation des expressions en forme close pour les probabilités de transition du prior LECS et l'implémentation des permutations d'étiquettes multicouches pour gérer les problèmes d'équivariance d'étiquettes dans les SBM (Modèles de Blocs Stochastiques) temporels.

Résultats
À travers des expériences empiriques sur des réseaux synthétiques avec $N=50$ nœuds et $L=5$ couches, les auteurs rapportent :

• Métriques de Localisation : Les valeurs d'IPR du prior LECS restent significativement plus basses et plus stables à travers les couches par rapport aux modèles de processus de Markov de Yang et al. et de Bazzi et al., dont les valeurs d'IPR augmentent au fil du temps. La distribution uniforme présente la localisation la plus élevée.
• Performance de Détection : Dans des réseaux possédant des structures de communauté connues de tailles variables ($q \in \{50, 60, 70, 80, 90\}$ sur 100 nœuds), l'approche basée sur le prior LECS surpasse les approches de processus de Markov (Yang et al. et Bazzi et al.) pour la détection de grandes communautés (ex: $q=70, 80, 90$). Bien que l'approche de Bazzi et al. soit légèrement meilleure pour les tailles modérées ($q=50, 60$), l'approche LECS démontre une robustesse supérieure pour les grandes communautés.
• Permutations Multicouches : L'inclusion de permutations d'étiquettes multicouches dans l'algorithme d'échantillonnage améliore significativement la performance des approches LECS et Bazzi et al., empêchant l'échantillonneur de rester bloqué dans des extrema locaux causés par un désalignement des étiquettes à travers les couches.

Signification et Revendications
L'article affirme que le choix du modèle génératif pour les assignations de communautés est un déterminant primaire de la précision de l'inférence statistique dans les réseaux temporels, particulièrement concernant la taille des communautés. Les auteurs soutiennent que les méthodes existantes reposant sur des processus de Markov ou des priors uniformes sont fondamentalement biaisées contre la détection de communautés de tailles disparates. En introduisant le prior LECS, ils fournissent un modèle génératif qui « atténue considérablement le biais contre les grandes et petites communautés », ce qui en fait un outil plus adapté pour l'étude des réseaux temporels où les tailles de communauté varient considérablement. Les auteurs concluent que leur approche est bénéfique pour l'étude de la structure communautaire dans des réseaux présentant de grandes ou de petites communautés et suggèrent que des biais de taille de groupe similaires peuvent affecter la détection d'autres structures mésoscopiques, telles que les motifs cœur-périphérie (core-periphery).