<  Back to the Polytechnique Montréal portal

Community detection in the stochastic block model by mixed integer programming

Breno Serrano and Thibaut Vidal

Article (2024)

Open Acess document in PolyPublie and at official publisher
Open Access to the full text of this document
Published Version
Terms of Use: Creative Commons Attribution Non-commercial No Derivatives
Download (2MB)
Show abstract
Hide abstract


The Degree-Corrected Stochastic Block Model (DCSBM) is a popular model to generate random graphs with community structure given an expected degree sequence. The standard approach of community detection based on the DCSBM is to search for the model parameters that are the most likely to have produced the observed network data through maximum likelihood estimation (MLE). Current techniques for the MLE problem are heuristics, and therefore do not guarantee convergence to the optimum. We present mathematical programming formulations and exact solution methods that can provably find the model parameters and community assignments of maximum likelihood given an observed graph. We compare these exact methods with classical heuristic algorithms based on expectation–maximization (EM). The solutions given by exact methods give us a principled way of measuring the experimental performance of classical heuristics and comparing different variations thereof.

Uncontrolled Keywords

community detection; stochastic block model; mixed integer programming; machine learning; unsupervised learning; local search

Subjects: 2950 Applied mathematics > 2950 Applied mathematics
Department: Department of Mathematics and Industrial Engineering
Funders: Deutsche Forschungsgemeinschaft, Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNq), Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ), CAPES
Grant number: 308528/2018-2, E-26/202.790/ 2019, 277991500/GRK2201
PolyPublie URL: https://publications.polymtl.ca/58199/
Journal Title: Pattern Recognition (vol. 152)
Publisher: Elsevier sci ltd
DOI: 10.1016/j.patcog.2024.110487
Official URL: https://doi.org/10.1016/j.patcog.2024.110487
Date Deposited: 28 May 2024 10:50
Last Modified: 01 Jun 2024 02:26
Cite in APA 7: Serrano, B., & Vidal, T. (2024). Community detection in the stochastic block model by mixed integer programming. Pattern Recognition, 152, 110487 (12 pages). https://doi.org/10.1016/j.patcog.2024.110487


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only

View Item View Item