Modularité asymptotique de quelques classes de graphes

International audienceDe nombreuses disciplines scientifiques font appel au clustering pour l'analyse de leurs réseaux d'interaction. Pami les très nombreux algorithmes existants, toute une famille utilise la modularité de Newman-Girvan comme objectif à maximiser, et cette valeur est devenue un paramètre de graphe standard. Dans cette étude nous prenons à rebours l'approche empirique usuelle et nous posons la question théorique de la modularité de classes de graphes. Nous montrons que des classes très régulières et sans ''clusters'' naturels (grilles, hypercubes,...) ont une modularité asymptotiquement 1 (le maximum possible), soit bien plus que les valeurs usuelles des données ''bien clusterisées''. Nous montrons que sous réserve d'une condition sur le degré maximum, les arbres ont aussi modularité asymptotique 1. Résultat qui nous permet de fournir une borne inférieure pour la modularité des graphes connexes peu denses et de certains power-law graphs, qui ont modularité asymptotique au moins 2/degré moyen, ainsi qu'un algorithme garantissant cette performance