Abstract EN:

Un graphe étant un ensemble d'objets liés par une certaine relation typée, le problème de "modularisation" des grands graphes (qui revient à leur partitionnement en classes) peut, alors, être modélisé mathématiquement en utilisant l'Analyse Relationnelle. Cette modélisation permet de comparer sur les mêmes bases un certain nombre de critères de découpage de graphe c'est-à-dire de modularisation. Nous proposons une réécriture Relationnelle des critères de modularisation connus tels le critère de Newman-Girvan, Zahn-Condorcet, Owsinski-Zadrozny, Condorcet pondéré, Demaine-Immorlica, Wei-Cheng, la Différence de profils et Michalski-Goldberg. Nous introduisons trois critères : la Modularité équilibrée, l'écart à l'Indétermination et l'écart à l'Uniformité. Nous identifions les propriétés vérifiées par ces critères et pour certains critères, notamment les critères linéaires, nous caractérisons les partitions obtenues via leur optimisation dans le but de faciliter leur compréhension et d'interpréter plus clairement leurs finalités en y associant la preuve de leur utilité dans certains contextes pratiques. Les résultats trouvés sont testés sur des graphes réels de tailles différentes avec l'algorithme de Louvain générique.