Constrained modularity maximization in complex networks via branch-and-price
Abstract
Modularity maximization is widely used to identify community structure in complex networks. In many applications, however, community detection must also incorporate prior knowledge and domain-specific requirements beyond network topology. We study constrained modularity maximization with restrictions on the number of communities, must-link and cannot-link relations, and general resource constraints. While fast heuristics can provide high-quality solutions, they generally lack optimality guarantees, whereas exact mathematical-programming approaches can become computationally demanding as the network size and constraint complexity increase. We develop a unified optimization framework offering complementary heuristic and exact solution methods. These include a constrained Louvain heuristic for feasible solution generation, a column-generation heuristic with graph-partitioning-based pricing, and exact branch-and-price algorithms using mixed-integer linear programming and sparse mixed-integer quadratic programming formulations for the pricing subproblem. We develop a cutting-plane procedure providing independent upper bounds to assess solution quality when exact optimization cannot be completed. Experiments on 11 unconstrained networks with up to 1,005 nodes and 30 constrained instances with up to 379 nodes demonstrate the complementary roles of these methods. The column-generation heuristic rapidly improves the constrained Louvain solutions across the tested constraint classes, while branch-and-price using the sparse quadratic formulation solves 29 of the 30 constrained instances to optimality within a one-hour time limit. This formulation becomes particularly effective on larger, sparse, undirected networks by substantially reducing the size of the exact pricing model. Overall, the framework guides method selection to balance computational time, solution quality, and optimality guarantees.
Related
- Shortcomings and capacities of real-constrained neural networks in complex spaces
- Exact computation of the network modularity with branch-and-bound
- Geometry-Constrained Kolmogorov-Arnold Networks: Learning Edge Geometry via Banach Duality
- Error bounds in Sobolev norms for approximations with norm constrained ReLU neural networks
- Monotone Physics-Constrained Graph Neural Networks for Image-Based Structural Damage Assessment: Theory and Leakage-Free Evaluation
BibTeX
@misc{kim2026constrained,
title = {{Constrained modularity maximization in complex networks via branch-and-price}},
author = {Jaewoo Kim and Seungyeop Lee and Jaemyung Ahn and Euihyeon Choi and Jeong-Hoon Kim},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26562},
eprint = {2610.26562},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26562},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Constrained modularity maximization in complex networks via branch-and-price
AU - Jaewoo Kim
AU - Seungyeop Lee
AU - Jaemyung Ahn
AU - Euihyeon Choi
AU - Jeong-Hoon Kim
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.26562
UR - https://arxiv.org/abs/2610.26562
AB - Modularity maximization is widely used to identify community structure in complex networks. In many applications, however, community detection must also incorporate prior knowledge and domain-specific requirements beyond network topology. We study constrained modularity maximization with restrictions on the number of communities, must-link and cannot-link relations, and general resource constraints. While fast heuristics can provide high-quality solutions, they generally lack optimality guarantees, whereas exact mathematical-programming approaches can become computationally demanding as the network size and constraint complexity increase. We develop a unified optimization framework offering complementary heuristic and exact solution methods. These include a constrained Louvain heuristic for feasible solution generation, a column-generation heuristic with graph-partitioning-based pricing, and exact branch-and-price algorithms using mixed-integer linear programming and sparse mixed-integer quadratic programming formulations for the pricing subproblem. We develop a cutting-plane procedure providing independent upper bounds to assess solution quality when exact optimization cannot be completed. Experiments on 11 unconstrained networks with up to 1,005 nodes and 30 constrained instances with up to 379 nodes demonstrate the complementary roles of these methods. The column-generation heuristic rapidly improves the constrained Louvain solutions across the tested constraint classes, while branch-and-price using the sparse quadratic formulation solves 29 of the 30 constrained instances to optimality within a one-hour time limit. This formulation becomes particularly effective on larger, sparse, undirected networks by substantially reducing the size of the exact pricing model. Overall, the framework guides method selection to balance computational time, solution quality, and optimality guarantees.
ER -