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.

Asymptotic modularity of some graph classes / F. De Montgolfier, M. Soto Gomez, L. Viennot (LECTURE NOTES IN COMPUTER SCIENCE). - In: Algorithms and Computation / [a cura di] T. Asano, S.-i. Nakano, Y. Okamoto, O. Watanabe. - [s.l] : Springer, 2011. - ISBN 978-3-642-25591-5. - pp. 435-444 (( Intervento presentato al 22. convegno International Symposium on Algorithms and Computation tenutosi a Yokohama nel 2011 [10.1007/978-3-642-25591-5_45].

Asymptotic modularity of some graph classes

M. Soto Gomez;
2011

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.
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
2011
IBM Japan, Ltd.
Nippon Telegraph and Telephone Corporation (NTT)
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
13_2011_AsymptoticModularity.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 217.92 kB
Formato Adobe PDF
217.92 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/961409
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 19
social impact