Heuristic and exact modularity optimization with size-constrained communities
Filipi N. Silva, Samin Aref, Vincent Traag, Santo Fortunato · 2026
Read Heuristic and exact modularity optimization with size-constrained communities by Filipi N. Silva, Samin Aref, Vincent Traag, Santo Fortunato (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25248.txt.
Introduction
Filipi Silva and colleagues tackle network grouping when every group must fall inside a size range set by the user. Standard tools only steer average group size through a tuning knob, leaving single groups free to balloon or shrink. Their new heuristic optimizes a standard quality score, called modularity, while respecting those size limits directly. An exact integer model serves as a check on synthetic and real networks, and the method ships inside the Python Leiden package.
Catalog record
| CREATOR | Filipi N. Silva, Samin Aref, Vincent Traag, Santo Fortunato |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36614 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25248
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Heuristic and exact modularity optimization with size-constrained communities Filipi N. Silva, Samin Aref, Vincent Traag, Santo Fortunato Abstract When searching for communities in networks, domain experts may have some prior expectations about the size of communities. Yet, community detection methods normally do not optimize communities under cluster size constraints. Multi-resolution techniques allow users to indirectly control the average community size through changing a resolution parameter, but this practice does not control the size of individual communities. We here study the problem of size-constrained community detection, where the size of all communities is limited to a user-specified range of values, in the context of modularity optimization. We propose a heuristic for modularity optimization under community size constraints. To demonstrate the reliability of our proposed heuristic, we also formulate an exact integer optimization model and use its results as a baseline. Our analysis based on synthetic benchmarks and real networks demonstrate the issues with the currently common practice of changing resolution parameters and reveal the advantages of the proposed methods as a principled way of obtaining size-constrained communities. The proposed method is publicly available in the Python Leiden algorithm package. I Introduction Understanding the underlying organizational principles of networks is a fundamental endeavor, and community detection has emerged as a pivotal concept in this field. Communities within networks represent subsets of nodes that are relatively well-connected internally Fortunato 2010 . Community Detection is a fundamental network problem which, in its simplest definition, involves partitioning nodes of an input network into communities according to the network structure. The identification of these communities is a crucial stepping stone toward comprehending the intricate structure, information flow, and emergent behavior within complex systems. Community detection is applied in various settings, spanning disciplines such as sociology, biology, and computer science. Practitioners in these fields apply community detection algorithms to analyze network models which often represent field-specific interconnected systems as the subject of a study. Despite the variety of field-specific contexts and applications, researchers in different fields may have a common computational challenge that is yet to be addressed: The subject matter expert may have prior information or requirements on community sizes. However, most existing community detection algorithms do not offer the user the flexibility to specify and directly control minimum and maximum community sizes. One example that shows the relevance of community size constraints appears in a common business application of community detection: market segmentation. This application involves clustering nodes that represent customers into communities using their networked data or other data purchasing history Korczak et al. 2019 ; Zhang et al. 2021 . A common issue with this usage is that communities will rarely become practical market segments because existing unconstrained community detection methods often lead to one extremely large community of many customers and numerous small communities of very few customers Korczak et al. 2019 ; Zhang et al. 2021 . Most small communities are often discarded without further analysis Zhang et al. 2021 because they contain too few customers to represent meaningful segment needs or be worthwhile for targeted offerings Korczak et al. 2019 . However, the range of acceptable sizes for market segments (community sizes) may be available based on marketing subject matter expertise. Therefore, a community detection algorithm that incorporates such community size range will be particularly useful in this context. The same challenge appears in many contexts across different fields including neuroscience applications where community detection algorithms are applied on brain connectome networks Szalkai et al. 2015 . The spatial and wiring patterns of neural links in brain connectome networks lead to existing algorithms typically producing either two or four trivial communities corresponding to two brain hemispheres or the front and back split of the two hemispheres, which are not particularly informative from a neuroscience perspective. Yet another example showing the same common challenge is chromosomal interaction networks. Unconstrained modularity-based community detection for the chromosomal interaction network in Mokhtaridoost et al. 2024 leads to a 3-community partition, whose communities are so large that they contradict exogenous information from biology including chromosomal territories Quinodoz et al. 2018 and topologically associating domain boundaries Dekker et al. 2023 . Therefore, size-constrained community detection will be particularly useful in genome topology research, where field-specific knowledge of reasonable ranges of community sizes is often available Mokhtaridoost et al. 2024 ; Quinodoz et al. 2018 ; Dekker et al. 2023 . We here study this problem further, focusing in particular on modularity Newman and Girvan 2004 as a commonly used and well studied method for community detection. Multi-resolution modularity-based algorithms allow users to change the modularity resolution parameter in an ad-hoc way to obtain communities matching their community size requirements using trial and error. Our results show that this common approach has major disadvantages, while its common usage justifies the need for a principled method for size-constrained community detection. We propose a modularity-based heuristic that incorporates community size constraints. We also formulate an exact method and use its results as baseline to demonstrate the reliability of our proposed optimization despite its heuristic nature Aref and Mostajabdaveh 2024 . I.1 Preliminaries and Notation We represent the undirected and unweighted graph G as the pair of sets V and E , V being the set of nodes ( |V|=n ), and E the set of edges ( |E|=m ). The symmetric adjacency matrix of graph G is represented by \textbf{A}=[a_{ij}] . The degree of node i is represented by d_{i}=\sum_{j}a_{ij} . Given a partition P=\{V_{1},V_{2},\dots,V_{q}\} of the node set V into q non-overlapping communities, the modularity function Q(G,P) is computed as Newman 2006 ; Fortunato and Hric 2016 Q(G,P)=\frac{1}{2m}\sum\limits_{(i,j)\in V^{2}}\left(a_{ij}-\gamma\frac{d_{i}d_{j}}{2m}\right)\delta(i,j)\,. (1) In Eq. ( 1 ), \gamma is the resolution parameter. The Kronecker delta, \delta(i,j) , equals 1 if nodes i and j are in the same community, otherwise it equals 0. The symmetric modularity matrix of graph G for a given resolution value \gamma , is represented by \textbf{B}=[b_{ij}] , whose entries are b_{ij}=a_{ij}-\gamma d_{i}d_{j}/{2m} . Some ordered pairs of nodes (i,j) correspond to non-negative modularity entries b_{ij}\geq 0 ; the set B^{+}=\{(i,j)\in V^{2},i<j\mid b_{ij}\geq 0\} represents all such ordered pairs. Conversely, the set B^{-}=\{(i,j)\in V^{2},i<j\mid b_{ij}<0\} contains all the ordered pairs of nodes that correspond to negative modularity entries b_{ij}<0 . II Problem statements In this section, we provide four problem statements to better define the optimization tasks involved in this study. • The unconstrained maximum modularity partition (MM) problem for the input graph G=(V,E) involves finding a partition P^{*}(G) whose modularity is maximal over all possible partitions: P^{*}(G)=\argmaxB_{P}Q(G,P) . • The size-constrained maximum modularity partition (SMM) is the same as the MM problem, but it is subject to the community size constraints: n_{\text{min}}\leq n_{c}\leq n_{\text{max}} , \forall c , where n_{c} is the size of community c . The set of partitions P that satisfy the above constraints is denoted by \mathcal{A} . • The maximum modularity k -partition (MMk) problem for the input graph G=(V,E) involves optimizing the modularity function Q(G,P) over all possible partitions of nodes to k communities at most. • The size-constrained maximum modularity k -partition (SMMk) problem is the same as the MMk problem, but it is subject to the community size constraints: n_{\text{min}}\leq n_{c}\leq n_{\text{max}} , \forall c . III