Statistical inference on random graphs and networks

• Ano de defesa: 2018
• Autor(a) principal: Cerqueira, Andressa
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Algoritmo Backward and Forward; Algoritmo Coupling From the Past; Backward and Forward algorithm; Couping From the Past algorithm; Estimação; Estimation; Exponential random graph; Grafos aleatórios exponenciais; Krichevisky-Trofimov; Krichevsky-Trofimov; Modelo estocástico por blocos; Perfect simulation; Simulação perfeita; Stochastic block model
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45133/tde-04042018-094802/

In this thesis we study two probabilistic models defined on graphs: the Stochastic Block model and the Exponential Random Graph. Therefore, this thesis is divided in two parts. In the first part, we introduce the Krichevsky-Trofimov estimator for the number of communities in the Stochastic Block Model and prove its eventual almost sure convergence to the underlying number of communities, without assuming a known upper bound on that quantity. In the second part of this thesis we address the perfect simulation problem for the Exponential random graph model. We propose an algorithm based on the Coupling From The Past algorithm using a Glauber dynamics. This algorithm is efficient in the case of monotone models. We prove that this is the case for a subset of the parametric space. We also propose an algorithm based on the Backward and Forward algorithm that can be applied for monotone and non monotone models. We prove the existence of an upper bound for the expected running time of both algorithms.