Full text
| |
| Author(s): |
Andressa Cerqueira
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | São Paulo. |
| Institution: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Defense date: | 2018-02-28 |
| Examining board members: |
Florencia Graciela Leonardi;
Miguel Natalio Abadi;
Cristian Favio Coletti;
Nancy Lopes Garcia;
Roberto Imbuzeiro Moraes Felinto de Oliveira
|
| Advisor: | Florencia Graciela Leonardi |
| Abstract | |
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. (AU) | |
| FAPESP's process: | 14/23526-0 - Perfect simulation of probabilistic networks |
| Grantee: | Andressa Cerqueira |
| Support Opportunities: | Scholarships in Brazil - Doctorate |