RNTI

MODULAD
Détection de communautés dans les graphes bipartites
In AAFD 2011, vol. RNTI-A-5, pp.65-76
Abstract
La recherche de communautés est un problème important pour de nombreux problèmes d'analyse des réseaux sociaux. Nous nous intéressons dans ce travail à la détection de communautés en utilisant uniquement le graphe des relations, dans la lignée des travaux de Newman. Le problème se formule donc comme la recherche de la partition du graphe maximisant un critère de qualité, comme la modularité. Le traitement des graphes bipartites est important pour de nombreuses applications (clients achetant des produits, objets associés à des étiquettes, etc.). La modularité proposée par Newman ne peut pas s'appliquer au cas des graphes bipartites, aussi plusieurs variantes ont été récemment proposées. Dans cet article, nous présentons deux formulations de critères et un algorithme d'optimisation heuristique similaire à celui de Louvain. Des résultats sur des graphes synthétiques et naturels sont présentés et discutés.