Exact computation of the network modularity with branch-and-bound
Abstract
We consider the computation of the network modularity, a common measure of the structure of networks or graphs that quantifies the division of a network into modules or clusters. The computation of the network modularity is an NP-hard problem, thus making its exact computation often infeasible in practice. This has resulted in the development of several heuristics in the literature. In this work, we consider the exact computation of the network modularity with the help of a branch-and-bound algorithm. Our algorithm is guaranteed to find the optimal clustering that maximizes the network modularity, however it achieves this without a full exploration of the search space. This is accomplished by bounding partial solutions and discarding them if it can be foreseen that a partial solution will not yield an improvement over an existing solution. We assess our algorithm with respect to accuracy and runtime and compare it to a brute-force approach as well as two benchmark algorithms, simulated annealing and the Louvain method.
Related
- An Exact Combinatorial Branch-and-Bound Algorithm for the Job Sequencing and Tool Switching Problem
- Constrained modularity maximization in complex networks via branch-and-price
- First-Order Primal-Dual Repairs for Scalable Branch and Bound
- Bipolar Fuzzy Minimum-Weight Satisfiability under Continuous t-Norms: A Clause-Witness Branch-and-Bound Framework
- Perturbative Schauder Estimates for Q-Valued Quasilinear Elliptic Systems and a Sharp Dimension Bound for Branch Sets of Stationary Graphs
BibTeX
@misc{weng2026exact,
title = {{Exact computation of the network modularity with branch-and-bound}},
author = {Emily Weng and Georg Hahn},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04668},
eprint = {2610.04668},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04668},
}
RIS
TY - UNPB
TI - Exact computation of the network modularity with branch-and-bound
AU - Emily Weng
AU - Georg Hahn
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.04668
UR - https://arxiv.org/abs/2610.04668
AB - We consider the computation of the network modularity, a common measure of the structure of networks or graphs that quantifies the division of a network into modules or clusters. The computation of the network modularity is an NP-hard problem, thus making its exact computation often infeasible in practice. This has resulted in the development of several heuristics in the literature. In this work, we consider the exact computation of the network modularity with the help of a branch-and-bound algorithm. Our algorithm is guaranteed to find the optimal clustering that maximizes the network modularity, however it achieves this without a full exploration of the search space. This is accomplished by bounding partial solutions and discarding them if it can be foreseen that a partial solution will not yield an improvement over an existing solution. We assess our algorithm with respect to accuracy and runtime and compare it to a brute-force approach as well as two benchmark algorithms, simulated annealing and the Louvain method.
ER -