Recherche en conception et analyse d’algorithmes, théorie des graphes et analyse de réseaux sociaux
Travail au Laboratoire d’algorithmes et de complexité
Sous la supervision du professeur Hovhannes Harutyunyan
Date : Août 2024 – Présent
Mon rôle principal consistait à :
Concevoir Spider, un algorithme de détection de communautés dans les graphes combinant une expansion géodésique, un raffinement guidé par la modularité et un appariement glouton par fusion.
Évaluer les performances de Spider sur 14 réseaux réels (jusqu’à 8 035 nœuds et 183 663 arêtes) en comparaison avec Leiden, Louvain et Infomap, obtenant des améliorations de 8 à 15 % en NMI, modularité et score F1.
Appliquer une sparsification par metric backbone, permettant une réduction moyenne de 65 % des arêtes, et proposer la modularité moyenne pondérée par distance géodésique (wGDM) afin de normaliser et d’équilibrer la GDM pour l’évaluation locale de la qualité des communautés.
Mettre en place un pipeline expérimental entièrement reproductible, incluant des graines aléatoires fixes, des implémentations de référence et des scripts d’évaluation automatisés.