Print Email Facebook Twitter Maximum modular graphs Title Maximum modular graphs Author Trajanovski, S. Wang, H. Van Mieghem, P. Faculty Electrical Engineering, Mathematics and Computer Science Department Intelligent Systems Date 2012-07-18 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. Subject statistical and nonlinear physics To reference this document use: http://resolver.tudelft.nl/uuid:0a31b891-4f8f-4f0b-932b-de1f348838e2 DOI https://doi.org/10.1140/epjb/e2012-20898-3 Publisher EDP Sciences/Springer ISSN 1434-6028 Source http://link.springer.com/article/10.1140%2Fepjb%2Fe2012-20898-3 Source European Physical Journal B, 85, 2012 Part of collection Institutional Repository Document type journal article Rights (c) 2012 EDP Sciences/Springer Files PDF Trajanovski_2012.pdf 656.32 KB Close viewer /islandora/object/uuid:0a31b891-4f8f-4f0b-932b-de1f348838e2/datastream/OBJ/view