<  Retour au portail Polytechnique Montréal

Community detection in the stochastic block model by mixed integer programming

Breno Serrano et Thibaut Vidal

Article de revue (2024)

Document en libre accès dans PolyPublie et chez l'éditeur officiel
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Version officielle de l'éditeur
Conditions d'utilisation: Creative Commons: Attribution-Pas d'utilisation commerciale-Pas de modification (CC BY-NC-ND)
Télécharger (2MB)
Afficher le résumé
Cacher le résumé

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.

Mots clés

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

Sujet(s): 2950 Mathématiques appliquées > 2950 Mathématiques appliquées
Département: Département de mathématiques et de génie industriel
Organismes subventionnaires: 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
Numéro de subvention: 308528/2018-2, E-26/202.790/ 2019, 277991500/GRK2201
URL de PolyPublie: https://publications.polymtl.ca/58199/
Titre de la revue: Pattern Recognition (vol. 152)
Maison d'édition: Elsevier sci ltd
DOI: 10.1016/j.patcog.2024.110487
URL officielle: https://doi.org/10.1016/j.patcog.2024.110487
Date du dépôt: 28 mai 2024 10:50
Dernière modification: 30 sept. 2024 04:27
Citer en 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

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Dimensions

Actions réservées au personnel

Afficher document Afficher document