Maximum modular graphs

Journal article (2012)
Department
Intelligent Systems (EEMCS) (TU Delft)
Copyright: © 2012 EDP Sciences/Springer
DOI: https://doi.org/doi:10.1140/epjb/e2012-20898-3
Statistical and nonlinear physics
More Info
expand_more

Published Date

18-07-2012

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Source:

European Physical Journal B, 85, 2012

ISSN:

1434-6028

Source:

http://link.springer.com/article/10.1140%2Fepjb%2Fe2012-20898-3

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Intelligent Systems

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 NPcomplete 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 datacenters design that can benefit of maximum modular partitioning are proposed.