[en] A MIP APPROACH FOR COMMUNITY DETECTION IN THE STOCHASTIC BLOCK MODEL

• Ano de defesa: 2020
• Autor(a) principal: BRENO SERRANO DE ARAUJO
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] PROGRAMACAO INTEIRA MISTA; [pt] APRENDIZADO NAO SUPERVISIONADO; [pt] STOCHASTIC BLOCK MODEL; [pt] DETECCAO DE COMUNIDADES; [pt] BUSCA LOCAL; [pt] MACHINE LEARNING; [en] MIXED INTEGER PROGRAMMING; [en] UNSUPERVISED LEARNING; [en] STOCHASTIC BLOCK MODEL; [en] COMMUNITY DETECTION; [en] LOCAL SEARCH; [en] MACHINE LEARNING
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=50168&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=50168&idi=2; http://doi.org/10.17771/PUCRio.acad.50168

[pt] O Degree-Corrected Stochastic Block Model (DCSBM) é um modelo popular para geração de grafos aleatórios com estrutura de comunidade, dada uma sequência de graus esperados. O princípio básico de algoritmos que utilizam o DCSBM para detecção de comunidades é ajustar os parâmetros do modelo a dados observados, de forma a encontrar a estimativa de máxima verossimilhança, ou maximum likelihood estimate (MLE), dos parâmetros do modelo. O problema de otimização para o MLE é comumente resolvido por meio de heurísticas. Neste trabalho, propomos métodos de programação matemática, para resolver de forma exata o problema de otimização descrito, e comparamos os métodos propostos com heurísticas baseadas no algoritmo de expectation-maximization (EM). Métodos exatos são uma ferramenta fundamental para a avaliação de heurísticas, já que nos permitem identificar se uma solução heurística é sub-ótima e medir seu gap de otimalidade.