Estimação do número de comunidades no modelo estocástico de blocos com correção de grau

• Ano de defesa: 2022
• Autor(a) principal: Tapia, Cristel Ecaterin Vera
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: : Poisson stochastic block model; Degree corrected stochastic block model; Estimação do número de comunidades; Estimation of the number of communities; Modelo estocástico de blocos com correção de grau; Modelo estocástico de blocos de Poisson; regime semi-esparso.; semi-sparse regime
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/104/104131/tde-05042023-103310/

O modelo estocástico de blocos (SBM, do inglês Stochastic Block Model) é um modelo de grafos aleatórios em que o conjunto de vértices é dividido em blocos, e a probabilidade de conexão entre cada par de vértices depende dos blocos aos quais os vértices pertencem. O SBM foi introduzido por Holland et al. (1983), é tipicamente aplicado em grafos simples, com cada entrada da matriz de adjacência seguindo uma distribuicao de Bernoulli. Karrer e Newman (2011) estenderam o modelo em duas direções: definiram o modelo multigrafo ou também conhecido como modelo estocástico de blocos de Poisson (Poisson SBM), em que as entradas da matriz de adjacência seguem a distribuição de Poisson, e introduziram o modelo estocástico de blocos com correção de grau (DCSBM, do inglês Degree Corrected Stochastic Block Model), que permite que a distribuição dos graus dos vértices dependa também dos vértices, e não somente dos blocos aos quais pertencem. A presente tese e dedicada ao problema de estimacao do número de comunidades no Poisson SBM e no DCSBM. Consideramos o regime denso, no qual a probabilidade de conexão entre pares de vértices não depende do tamanho do grafo e também o regime semi-esparso, no qual a probabilidade de conexão entre pares de vértices pode decair para 0 (numa certa taxa) com o tamanho do grafo. Neste contexto geral, provamos que o estimador do número de comunidades introduzido por Cerqueira e Leonardi (2020) (com as devidas alterações) é fortemente consistente.