Asymptotic Modularity of some Graph Classes

Abstract : Modularity has been introduced as a quality measure for graph partitioning. It has received considerable attention in several disciplines, especially complex systems. In order to better understand this measure from a graph theoretical point of view, we study the modularity of a variety of graph classes. We first consider simple graph classes such as tori and hypercubes. We show that these regular graph families have asymptotic modularity 1 (that is the maximum possible). We extend this result to the general class of unit ball graphs of bounded growth metrics. Our most striking result concerns trees with bounded degree which also appear to have asymptotic modularity 1. This last result can be extended to graphs with constant average degree and to some power-law graphs.
Type de document :
Communication dans un congrès
22nd International Symposium on Algorithms and Computation (ISAAC), Dec 2011, Yokohama, Japan. pp.435-444, 2011
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00909733
Contributeur : Laurent Viennot <>
Soumis le : mardi 26 novembre 2013 - 17:23:23
Dernière modification le : vendredi 31 août 2018 - 09:12:06
Document(s) archivé(s) le : jeudi 27 février 2014 - 10:56:05

Fichier

isaac2011AsymptoticModularity....
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00909733, version 1

Collections

Citation

Fabien De Montgolfier, Mauricio Soto, Laurent Viennot. Asymptotic Modularity of some Graph Classes. 22nd International Symposium on Algorithms and Computation (ISAAC), Dec 2011, Yokohama, Japan. pp.435-444, 2011. 〈hal-00909733〉

Partager

Métriques

Consultations de la notice

212

Téléchargements de fichiers

113