Detectability threshold in weighted modular networks

Résumé technique : Seuil de détectabilité dans les réseaux modulaires pondérés

Énoncé du problème
L'article traite des limites fondamentales de la détection de communautés dans les réseaux pondérés. Alors que le seuil de détectabilité — le niveau maximal de mélange au-delà duquel la structure de communauté devient indiscernable du bruit aléatoire — a été bien caractérisé pour les réseaux non pondérés (spécifiquement dans le modèle de partition plantée, PPM), les conditions pour les réseaux pondérés restent largement inexplorées. Une intuition prédominante suggère que l'incorporation de poids d'arêtes devrait améliorer les performances de détection en fournissant des informations plus riches. Cependant, les auteurs étudient si cela est vrai lorsque les poids sont générés indépendamment de la structure de communauté, agissant potentiellement comme du bruit plutôt que comme un signal. L'étude vise à dériver une expression analytique générale pour le seuil de détectabilité dans les réseaux pondérés, en déterminant comment les propriétés statistiques des poids d'arêtes influencent la capacité de l'optimisation de la modularité spectrale à récupérer les partitions de vérité terrain.

Méthodologie
Les auteurs analysent des réseaux générés selon un modèle de partition plantée pondéré (PPM) avec deux communautés de taille égale. La génération du réseau suit un processus en deux étapes :

1. Topologie : Les arêtes sont établies selon un processus de Bernoulli où la probabilité de connexion dépend de l'appartenance des nœuds à la même communauté ($p_{in}$) ou à des communautés différentes ($p_{out}$). Les degrés des nœuds suivent des distributions de Poisson dans la limite de la taille du réseau.
2. Poids : Les arêtes existantes se voient assigner des poids tirés de distributions de probabilité spécifiques ($W_{in}$ pour l'intra-communauté, $W_{out}$ pour l'inter-communauté).

L'algorithme de détection employé est l'optimisation de la modularité spectrale. Les auteurs utilisent la matrice de modularité $Q$, où les entrées sont définies par $q_{ij} = a_{ij}w_{ij} - \frac{s_i s_j}{2m}$ (avec $s_i$ étant la force du nœud et $2m$ la force totale). Le seuil de détectabilité est déterminé par l'analyse de la valeur propre principale $\lambda$ de cette matrice.

L'approche analytique centrale consiste à dériver les deux premiers moments de la distribution de différence de force ($\Delta s = s_{in} - s_{out}$). En utilisant des fonctions génératrices de moments (MGF), les auteurs expriment la plus grande valeur propre $\lambda$ comme le rapport du second moment au premier moment de $\Delta s$ :
$$\lambda \approx \frac{\langle \Delta s^2 \rangle}{\langle \Delta s \rangle}$$
Le seuil de détectabilité est identifié comme le point où $\lambda$ est maximisé par rapport au paramètre de mélange (la différence des degrés ou des poids moyens), marquant la transition où la méthode spectrale ne peut plus surpasser le choix aléatoire.

Contributions clés et résultats
L'article dérive un cadre unifié pour le seuil de détectabilité qui dépend des deux premiers moments de la distribution du degré des nœuds et du poids des arêtes. Les auteurs paramètrent le second moment de la distribution des poids comme une fonction quadratique de sa moyenne : $\langle w^2 \rangle = \alpha_0 + \alpha_1 \langle w \rangle + \alpha_2 \langle w \rangle^2$.

L'étude évalue cinq distributions de poids spécifiques : Dirac, Poisson, Exponentielle, Géométrique et Bernoulli signée. Les principales conclusions concernant la hiérarchie des seuils de détectabilité sont :

1. Distribution de Dirac (Poids déterministes) : Elle produit le plus petit seuil de détectabilité, correspondant à la limite classique du PPM non pondéré ($\Delta^*_k = \sqrt{K}$, où $K$ est la somme des degrés moyens). Cela sert de base optimale, représentant le cas où les poids sont parfaitement corrélés à la structure de communauté (ou constants).
2. Distribution Exponentielle : Cette distribution présente systématiquement le scénario le plus difficile, augmentant le seuil de détectabilité d'un facteur $\sqrt{2}$ par rapport au cas de Dirac. Cette pénalité est indépendante du poids moyen total $W$ et est attribuée à la variance élevée inhérente aux distributions exponentielles.
3. Distribution de Poisson : Présente un comportement intermédiaire dépendant du poids total $W$. Pour de faibles valeurs de $W$, les poids de Poisson créent un seuil plus élevé (détection plus difficile) que le cas exponentiel. Cependant, à mesure que $W$ augmente, la variance relative diminue, et le seuil approche asymptotiquement la limite optimale de Dirac.
4. Distribution Géométrique : Présente un comportement similaire à la distribution de Poisson mais avec une mise à l'échelle de la variance plus élevée. Son seuil approche la limite exponentielle à mesure que $W$ augmente.
5. Distribution de Bernoulli signée : Dans le cas d'une topologie homogène (où la structure est encodée uniquement dans les poids), le seuil est indépendant du paramètre de déséquilibre de signe $W$, dépendant plutôt du degré moyen.

Scénarios analysés
Les auteurs analysent deux scénarios distincts :

• Structure pilotée par la topologie : Les communautés sont définies par la densité de connexion, avec des poids homogènes à travers le réseau. Ici, le seuil dépend du poids total $W$ et de la variance de la distribution des poids.
• Structure pilotée par le poids : La topologie est homogène (Erdős–Rényi), et les communautés sont définies uniquement par des différences de poids d'arêtes. Ici, le seuil dépend de la différence des poids moyens ($\Delta w$) et des paramètres de variance.

Signification et affirmations
L'article affirme que l'utilité des poids d'arêtes dans la détection de communautés n'est pas intrinsèque mais dépend de manière critique de la question de savoir si les poids renforcent la structure de communauté.

• Bruit vs Signal : Si les poids d'arêtes sont générés indépendamment de la structure de communauté (agissant comme du bruit), leur incorporation dans l'algorithme de détection est préjudiciable. La variabilité accrue des poids d'arêtes peut rendre les communautés moins détectables que si les poids étaient ignorés.
• Mise à l'échelle de la variance : Le seuil de détectabilité est fondamentalement déterminé par la façon dont la variance des poids d'arêtes évolue avec leur moyenne. Les distributions ayant une variance élevée par rapport à la moyenne (comme l'Exponentielle) masquent la structure de communauté, tandis que celles dont la variance évolue de manière linéaire ou sous-linéaire (comme la Poisson à des moyennes élevées) permettent une meilleure détection.
• Généralisabilité : Bien que la dérivation théorique soit spécifique à l'optimisation de la modularité spectrale, les auteurs soutiennent que la hiérarchie de difficulté entre les distributions de poids reflète le rapport signal sur bruit inhérent au réseau. Par conséquent, ces limites sont probablement extensibles à d'autres méthodes de détection de communautés, y compris celles basées sur les réseaux de neurones ou les approches de la théorie de l'information.

Les auteurs valident leurs prédictions analytiques par des simulations numériques sur des réseaux finis et étendent leurs conclusions aux réseaux multi-communautés en utilisant l'algorithme de Leiden, confirmant que la hiérarchie des distributions de poids reste cohérente à travers différents nombres de communautés.