Total: 1
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.