RNTI

MODULAD
Comparison of linear modularization criteria using the relational formalism, an approach to easily identify resolution limit
In EGC 2015, vol. RNTI-E-28, pp.203-214
Résumé
La modularisation de grands graphes ou recherche de communautés est abordée comme l'optimisation d'un critère de qualité, l'un des plus utilisés étant la modularité de Newman-Girvan. D'autres critères, ayant d'autres propriétés, aboutissent à des solutions différentes. Dans cet article, nous présentons une réécriture relationnelle de six critères linéaires: Zahn-Condorcet, Owsi´nski- Zadro˙zny, l'Ecart à l'Uniformité, l'Ecart à l'Indétermination et la Modularité Equilibrée. Nous utilisons une version générique de l'algorithme d'optimisation de Louvain pour approcher la partition optimale pour chaque critère sur des réseaux réels de différentes tailles. Les partitions obtenues présentent des caractéristiques différentes, concernant notamment le nombre de classes. Le formalisme relationnel nous permet de justifier ces différences d'un point de vue théorique. En outre, cette notation permet d'identifier facilement les critères ayant une limite de résolution (phénomène qui empêche en pratique la détection de petites communautés sur de grands graphes). Une étude de la qualité des partitions trouvées dans les graphes synthétiques LFR permet de confirmer ces résultats.