Des graphes denses aux communautés significatives : évaluation de la qualité des communautés à l’aide de la modularité fondée sur la distance géodésique dans des réseaux sparsifiés par Metric Backbone
- Conférence : 12e Conférence internationale sur l’analyse, la gestion et la sécurité des réseaux sociaux (IEEE SNAMS 2025)
- DOI : https://doi.org/10.1109/SNAMS67467.2025.11391193
- Diapositives de présentation : Voir sur ResearchGate
Résumé :
La détection de communautés constitue un élément central de la science des réseaux, essentiel pour révéler et analyser les structures au sein des réseaux complexes. Cette étude propose une analyse approfondie combinant fondements théoriques et évaluation pratique détaillée. Notre investigation repose sur deux méthodologies complémentaires : la métrique de distance géodésique (GDM), utilisée comme outil d’évaluation sensible à la structure et indépendant des étiquettes ; et le Metric Backbone, une approche de sparsification sans paramètre qui préserve les structures communautaires essentielles. Nous présentons et évaluons un pipeline évolutif de détection de communautés reposant sur la sparsification par Metric Backbone combinée à des algorithmes de détection de communautés, les résultats étant évalués à l’aide de plusieurs métriques de qualité reconnues. Notre évaluation empirique systématique, menée sur sept jeux de données réels et variés, montre que la sparsification par Metric Backbone entraîne une réduction significative du nombre d’arêtes — allant de 14 % dans des réseaux de citation peu denses à 71 % dans des réseaux sociaux denses — tout en préservant la qualité de la détection de communautés. De manière notable, l’ensemble de données High School conserve des scores F1 et NMI de 0,970 malgré une réduction de 71 % des arêtes, tandis que le réseau de coachat Amazon maintient des performances stables avec une sparsification de 29 %. Les résultats soulignent que la sparsification par Metric Backbone améliore l’efficacité computationnelle et facilite l’utilisation de métriques fondées sur la distance géodésique, telles que la GDM, pour identifier des communautés compactes et bien séparées. Cette analyse approfondie constitue la première étude systématique de l’évaluation des communautés fondée sur la distance géodésique dans des réseaux sparsifiés préservant la structure, et fournit des éclairages précieux sur les conditions dans lesquelles une sparsification sans paramètre préserve — plutôt qu’entrave — la détection de communautés à travers différents types de réseaux.