Eur. Phys. J. B (2012) 85: 244
https://doi.org/10.1140/epjb/e2012-20898-3

Regular Article

Maximum modular graphs

Delft University of Technology, Faculty of EEMCS, P.O. Box 5031, 2600 GA Delft, The Netherlands

^a e-mail: S.Trajanovski@tudelft.nl

Received: 3 November 2011
Received in final form: 7 May 2012
Published online: 18 July 2012

Abstract

Modularity has been explored as an important quantitative metric for community and cluster detection in networks. Finding the maximum modularity of a given graph has been proven to be NP-complete and therefore, several heuristic algorithms have been proposed. We investigate the problem of finding the maximum modularity of classes of graphs that have the same number of links and/or nodes and determine analytical upper bounds. Moreover, from the set of all connected graphs with a fixed number of links and/or number of nodes, we construct graphs that can attain maximum modularity, named maximum modular graphs. The maximum modularity is shown to depend on the residue obtained when the number of links is divided by the number of communities. Two applications in transportation networks and data-centers design that can benefit of maximum modular partitioning are proposed.