Mathématiques et détection de communautés

Les sociologues étudient les schémas des interactions et des relations sociales au quotidien en structurant la société en réseau. De même, les biologistes utilisent les réseaux pour organiser des similarités entre espèces ou la coexpression de gènes. Dans ces réseaux, chaque élément est représenté par un point, ou «nœud», et chaque interaction par une ligne les reliant. Nous connaissons les réseaux d’éléments en interaction sous la forme de graphes.

Un des points d’intérêt principaux de tels réseaux est de déterminer quels nœuds sont «similaires»: par exemple ceux représentant les collègues ou les membres d’une famille. Lorsque des nœuds semblables se regroupent, ils commencent à former ce qu’on appelle des «communautés». Ces dernières sont toutefois difficiles à détecter. Ce problème est crucial lorsqu’il s’agit d’étudier notamment les interactions entre les protéines et l’expression génique dans les cellules ou de poser un diagnostic médical et d’établir des schémas dans le comportement social.

La tâche la plus élémentaire de la détection de communautés consiste à partitionner les nœuds d’un graphe en groupes aux liens plus denses, qui représentent par exemple les membres d’un club de sport. Fort d’une croissance énorme depuis les années 1980, le domaine de la détection de communautés utilise aujourd’hui une diversité remarquable de modèles et d’algorithmes mis au point par différentes branches scientifiques telles que l’apprentissage automatique et l’informatique.

Des questions concernant les communautés

«Malgré cette croissance, plusieurs questions fondamentales subsistent», déclare le professeur Emmanuel Abbé, de la Chaire de mathématiques de la science des données de l’EPFL (faculté des Sciences de base et faculté Informatique et Communications). Son travail se concentre sur des problèmes persistants en détection de communautés.

Le premier point concerne la validité des communautés détectées dans les graphes. «Les algorithmes peuvent détecter des communautés, mais sont-elles pertinentes ou artificielles?» demande le chercheur. Autre question, celle de la fiabilité des méthodes utilisées actuellement dans la branche: «Pouvons-nous toujours extraire les communautés qui sont présentes? L’extraction est-elle totale ou partielle?» Finalement, le contrôle qualité pose aussi problème: «Quelles sont les bonnes références pour évaluer les performances des algorithmes, et quels sont les meilleurs algorithmes?»

Ces dernières années, Emmanuel Abbé et son équipe sont parvenus à répondre à ces questions pour une catégorie de graphes aléatoires souvent utilisés en apprentissage automatique et en statistiques. Appelés «modèles à blocs stochastiques», ces derniers sont des références utiles pour les scientifiques car ils sont très révélateurs et admettent un vaste ensemble d’extensions pratiques. Les recherches d’Emmanuel Abbé sur l’analyse des modèles à blocs stochastiques proposent un axe de recherche qui rapproche la théorie de l’information et l’apprentissage automatique et est à la source de différents travaux de suivi dans les deux branches.

Le scientifique et ses coauteurs ont décrit les cas où l’extraction de communautés était possible ou non pour les modèles à blocs stochastiques généraux. Leur recherche améliore un travail qui s’étend sur des décennies en obtenant les bornes précises donnant la limite fondamentale pour différents critères de détection de communautés, et en mettant au point différents algorithmes qui atteignent ces limites.

«Les communautés sont l’une des premières caractéristiques intéressantes dans les réseaux, et les modèles à blocs sont l’un des premiers modèles de réseau, affirme Emmanuel Abbé. Il existe bien d’autres problèmes en lien avec l’extraction de schémas dans des données graphiques, pour lesquels nous espérons que les récentes avancées nous aideront aussi.»

Travaux mathématiques

Dans un article publié en 2016 [1], l’équipe d’Emmanuel Abbé a d’abord dérivé la limite fondamentale pour la reconstruction exacte dans le cas de deux communautés, obtenant une expression de forme fermée pour la limite. Elle a ensuite montré que la limite pouvait être atteinte de manière efficace, et elle a mis en lien le problème de reconstruction exacte avec la théorie des codes, apportant ainsi une nouvelle perspective pour la détection de communautés et le groupement graphique.

Ce travail s’est étendu dans un autre article [2] (publié en fait en 2015) en résolvant la reconstruction exacte dans le modèle à bloc stochastique général, avec un nombre arbitraire de groupes de tailles aléatoires et de taux de connectivité arbitraires entre les communautés. Il a notamment quantifié la limite fondamentale en matière de divergence de Chernoff-Hellinger, conférant une nouvelle signification opérationnelle à cette divergence mathématique du point de vue de la détection de communautés.

Un autre article [3], publié en 2017, s’est penché sur les critères de reconstruction plus faibles lorsque les communautés sont reconstruites seulement partiellement pour le modèle à bloc stochastique général. L’article prouve le caractère optimal d’un algorithme qui consiste en une linéarisation de l’algorithme de propagation des convictions (BP) de la physique statistique, confirmant ainsi une hypothèse avancée par les physiciens. Tandis que l’établissement de garanties rigoureuses des performances des BP pour les graphes à cycles constitue un problème ouvert, l’article a obtenu une preuve solide du caractère optimal de l’algorithme BP linéarisé en le liant à un algorithme spectral pour certains opérateurs de non-retour en arrière.

Les références 4 et 5 citées ci-dessous donnent un aperçu de ces travaux et de la littérature traitant du sujet.