Résumé technique : Optimisation heuristique et exacte de la modularité avec communautés contraintes en taille

Énoncé du problème

La détection de communautés est une tâche fondamentale en analyse de réseaux, mais les algorithmes standards échouent souvent à intégrer des connaissances a priori spécifiques au domaine concernant les tailles des communautés. Dans des applications telles que la segmentation de marché, la neuroscience (connectomes cérébraux) et la génomique (interactions chromosomiques), les experts possèdent souvent des connaissances sur des plages raisonnables de tailles de communautés. Cependant, les méthodes non contraintes existantes produisent fréquemment des partitions avec des disparités extrêmes de taille (par exemple, une communauté massive et de nombreuses communautés triviales) ou ne parviennent pas à s'aligner sur les réalités biologiques ou fonctionnelles.

Bien que les techniques multi-échelles permettent aux utilisateurs d'influencer indirectement la taille moyenne des communautés en ajustant un paramètre de résolution ($\gamma$), cette approche ne contrôle pas la taille des communautés individuelles, ni ne garantit que toutes les communautés tombent dans une plage spécifique définie par l'utilisateur. Cet article aborde le problème de la Modularité Maximale Contrainte en Taille (SMM) : trouver une partition d'un réseau qui maximise la modularité tout en s'assurant que chaque taille de communauté $n_c$ satisfait $n_{min} \le n_c \le n_{max}$.

Méthodologie

Les auteurs proposent une approche duale pour résoudre le problème SMM : une base d'optimisation exacte et une heuristique évolutive.

1. Base d'optimisation exacte (SMMk)

Pour établir une vérité terrain pour la fiabilité, les auteurs formulent le problème comme un Programme en Nombres Entiers (IP).

• Formulation : Ils étendent la formulation standard de Programmation en Nombres Entiers pour le problème de la $k$-partition à modularité maximale (MMk).
• Contraintes : Le modèle inclut des contraintes linéaires pour imposer les bornes de taille. Plus précisément, ils introduisent des contraintes garantissant que pour toute communauté non vide $c$, le nombre de nœuds $\sum x_{ic} \ge n_{min}$, et pour toutes les communautés potentielles, $\sum x_{ic} \le n_{max}$.
• Résolveur : Le modèle est résolu à l'aide de l'optimiseur Gurobi pour obtenir des partitions globalement optimales (ou quasi-optimales) pour des graphes de petite à moyenne taille. Cela sert de base de référence pour évaluer l'heuristique.

2. Optimisation heuristique (Leiden Contraint - CL)

Imposer directement des contraintes de taille dans les heuristiques de modularité standards (comme l'algorithme Leiden) pose problème car les déplacements locaux de nœuds peuvent facilement violer les bornes de taille (par exemple, déplacer un nœud vers une nouvelle communauté singleton viole $n_{min} > 1$).

• Approche par pénalité : Au lieu d'une méthode de barrière (qui restreint l'espace de recherche), les auteurs emploient une approche par pénalité. Ils transforment le problème contraint en un problème non contraint en optimisant une fonction objectif modifiée :
  $$Q'(G, P) = Q(G, P) - \phi \Theta(P)$$
  Où $\Theta(P)$ est une fonction de pénalité pour les communautés violant les contraintes de taille, et $\phi$ est un poids de pénalité.
• Fonction de pénalité : La pénalité $\theta(n_c)$ pour une communauté de taille $n_c$ est définie comme suit :
  $$\theta(n_c) = \begin{cases} \sqrt{n_{min} - n_c} & \text{si } n_c < n_{min} \\ \sqrt{n_c - n_{max}} & \text{si } n_c > n_{max} \end{cases}$$
  La fonction racine carrée est choisie car elle est sous-additive, empêchant l'algorithme de rester piégé dans des optima locaux où le fait de diviser une grande communauté violante en deux communautés plus petites mais toujours violantes donnerait une pénalité totale plus faible.
• Calendrier progressif : L'algorithme commence avec $\phi = 0$ (non contraint). Si la partition résultante viole les contraintes, $\phi$ est augmenté (en commençant à $10^{-4}$ et en doublant) et l'optimisation est réinitialisée à partir de la solution précédente. Cela continue jusqu'à ce qu'une partition réalisable soit trouvée.

Résultats clés

Les auteurs ont évalué la méthode Leiden Contraint (CL) proposée par rapport au Leiden Non Contraint (UL) et à la base de référence Programmation en Nombres Entiers Contrainte (CIP) sur des réseaux synthétiques et réels.

Benchmarks synthétiques

• Modèles de partitions plantées : Dans des réseaux avec des communautés de vérité terrain connues, CL et CIP ont nettement surpassé UL en taux de récupération (mesurés par l'Information Mutuelle Ajustée, AMI), en particulier lorsque le paramètre de mélange était faible à moyen. UL a souvent échoué à récupérer les communautés plantées car il produisait des partitions avec des tailles hors de la plage attendue.
• Anneau de cliques : Dans un graphe de 50 cliques (taille 5) connectées séquentiellement, UL n'a récupéré la partition correcte que si le paramètre de résolution était ajusté manuellement à une plage spécifique ($[5, 40]$). En revanche, CL a récupéré avec précision la partition plantée à la résolution par défaut ($\gamma=1$) lorsqu'on lui a fourni la plage de taille correcte $[2, 8]$.
• Fiabilité : Les taux de récupération de l'heuristique CL étaient constamment proches, et parfois égaux, de la base de référence exacte CIP, démontrant que l'heuristique ne sacrifie pas la précision pour la vitesse dans ces contextes.

Réseaux réels

• Connectome cérébral : Appliqué au réseau du connectome cérébral de Budapest, UL a produit une partition triviale de quatre communautés (correspondant aux hémisphères), ce qui manque d'utilité en neuroscience.
• Alignement avec le domaine : En appliquant CL avec une plage de taille dérivée de connaissances expertes (basée sur les atlas Brainnetome et Schaefer, $[43, 187]$ nœuds), la méthode a produit 6 communautés. Ce résultat s'aligne beaucoup mieux avec les clusters fonctionnels cérébraux connus (par exemple, les 7 clusters définis par Yeo et al.) que le résultat non contraint.
• Contrôle de la variation : Les auteurs ont démontré que changer le paramètre de résolution dans UL contrôle la taille moyenne des communautés mais échoue à contrôler la variation (variance) des tailles. CL fournit un contrôle direct à la fois sur la moyenne et la variation, garantissant que toutes les communautés tombent dans les bornes spécifiées.

Signification et revendications

L'article revendique que la méthode proposée offre une façon fondée d'intégrer l'expertise du domaine dans la détection de communautés.

• Contrôle direct : Contrairement à la pratique d'« essai-erreur » consistant à ajuster les paramètres de résolution, CL permet aux utilisateurs de définir explicitement la taille minimale et maximale des communautés, répondant directement aux besoins des experts du domaine.
• Évolutivité : Bien que la méthode IP exacte (CIP) soit limitée par la complexité computationnelle aux petits graphes, l'heuristique CL est évolutive et peut être appliquée à de grands réseaux, la rendant pratique pour des applications réelles.
• Implémentation : La méthode est implémentée au sein du package d'algorithme Leiden en Python, la rendant accessible pour une utilisation immédiate.

Les auteurs concluent que bien que la modularité ait des limites connues (telles que la limite de résolution et l'absence de fondement statistique clair), la capacité d'imposer des contraintes de taille via leur heuristique permet des partitions plus informatives et alignées sur le domaine. Ils suggèrent que des travaux futurs pourraient explorer l'intégration de contraintes de taille dans d'autres cadres, tels que les Modèles de Blocs Stochastiques (SBM), pour exploiter ces contraintes dans un contexte d'inférence statistique.