{'fraction_non_alphanumeric': 0.05091691956527378, 'fraction_numerical': 0.021463958706196665, 'mean_word_length': 3.7839061918352153, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Statistical inference on random graphs and networks

CERQUEIRA, A. Statistical inference on random graphs and networks. 2018. 83 f. Tese (Doutorado) Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, 2018. 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.


Chapter 1 Introduction
In recent years there has been an increasing interest in the study of probabilistic models defined on graphs. One of the main reasons for this interest is that these models are very flexible, making them suitable for the description of real datasets, for instance in social networks, computational networks, biological networks and neural networks. The interactions in a real network can be represented through a graph, where the objects of study are represented by the vertices of the graph and the interactions between these components are identified as the edges of the graph.
In order to describe the random interactions in a system many random graphs models have been vastly studied; however two among all random graphs models will be the focus of this thesis: the Stochastic Block model and the Exponential random graph model.
In some real networks one can observe the presence of communities, where the nodes of the network are split into groups with similar connection patterns. The Stochastic Block Model (SBM) was introduced by Holland et al. (1983) and it is vastly studied in the literature for community detection on random networks. In this model, each node in the network has associated a latent discrete random variable describing its community label, and given two nodes, the presence of a connection between them depends only on the values of the nodes' latent variables.
From a statistical point of view, some methods have been proposed to address the problem of parameter estimation or label recovering for the SBM. Some examples include maximum likelihood estimation (Amini et al., 2013;Bickel e Chen, 2009), variational methods (Daudin et al., 2008;Latouche et al., 2012), spectral clustering (Rohe et al., 2011) and Bayesian inference (van der Pas et al., 2017). The asymptotic properties of these estimators have also been considered in subsequent works such as Bickel et al. (2013) or Su et al. (2017).
In both problems described above the number of communities (or blocks) of the model is assumed to be known. To our knowledge, the estimation of the number of communities in the SBM was not addressed in the literature until the recent work by Wang et al. (2017). The authors propose a penalized likelihood criterion and show its weak consistency, that is INTRODUCTION 1.0 only valid when the number of communities is upper bounded by a known constant and the network average degree grows as a polylog function on the number of nodes.
The method introduced in Wang et al. (2017) has been subsequently studied in Hu et al. (2016), where the authors propose a modification of the penalty term. However, in practice, the computation of the suggested estimator still remains a demanding task since it depends on the profile maximum likelihood.
The second model studied in this work is the Exponential Random Graph (ERG). Unlike the SBM, it does not take into account the structure of communities in the network. This model is defined using the sufficient statistics of the graph, for example, the number of edges, the number of triangles, the number of stars, and so on. For this reason this model has received a lot of attention from the Social Sciences community. Social networks are used as a way to describe and analyze the interactions between a set of actors where the reciprocity property is desired. Reciprocity assures that if two actors of the model interact with a third one, then it is more likely that they interact between them as well. In this context, the ERG has been vastly explored to model social networks since the sufficient statistics may represent desired properties of the graph; for example, the number of triangles in the graph can be used to represent the reciprocity property.
In terms of parameter estimation for this model, classical inferential methods such as Monte Carlo maximum likelihood of Geyer e Thompson (1992) and the pseudolikelihood estimation introduced by Besag (1974) are widely used in practice. In both these methods, it is necessary to use samples of the ERG distribution; however sampling from this distribution is usually not a simple task due to the fact that the normalizing constant of this distribution depends on a sum over the support of the distribution, that is, the set of all graphs. For a large number of vertices of the graph the distribution's support is a huge set; for instance, to compute the normalizing constant for a graph with 20 vertices it is necessary to calculate a sum over the support set containing 2 190 graphs.
In general, the algorithms to sample from the ERG distribution are based on a well known and vastly studied method in the literature called Markov chain Monte Carlo (MCMC). The Metropolis Hastings algorithm, introduced in the works of Metropolis et al. (1953) and Hastings (1970), and the Gibbs sampling algorithm, described in the work of Geman e Geman (1984), are the most used MCMC algorithms. None of these algorithms depend on the normalizing constant of the distribution to sample approximately a graph from this model.
The main idea of MCMC algorithms is the construction of an appropriate Markov chain having as limiting distribution the desired distribution. Using this method, the value obtained by running the Markov chain, from an initial state and after a number of steps, is an approximate sample of the target distribution. Notice that after running the chain a finite number of steps the sample obtained is an approximation of the limiting distribution of the chain and, depending on the number of steps, this value may depend on the initial state. Snijders (2002) has studied and applied the MCMC algorithm for the purpose of simulating from the ERG model. However, the principal drawback of the MCMC methods is the choice of the number of steps to run the algorithm in order to obtain a representative sample of the target distribution.
Bhamidi and co-authors presented a study of the mixing time of the Markov chain constructed using the Glauber dynamics (also known as Gibbs sampling) for ERG models with positive parameters. They describe the model introducing the concept of high and low temperature regimes and they show that for models for which the parameters belong to the high temperature phase the mixing time of the chain converges quickly to the stationary distribution. Furthermore, for models under the low temperature regime, the convergence takes an exponential time. They also show that for models under the high temperature regime any finite collection of edges in the graph are asymptotically independent, that is, when the number of vertices grows to infinity.
To overcome the issue of the convergence of the MCMC methods, Butts (2015) proposed a novel algorithm called bound sampler, for which the simulation time is fixed and depends only on the number of vertices of the graph. This algorithm and MCMC samplers are approximated methods for sampling from the ERG model. However, the bound sampler is recommended instead of MCMC algorithms when the mixing time of the chain is quite long.

Objectives
In this thesis we first address the model selection problem for the number of communities in the Stochastic Block Model (SBM). Given a graph obtained from the SBM, our goal is the construction of an estimator for the number of communities of the model.
In this way, we take an information-theoretic perspective and introduce the Krichevsky-Trofimov (KT) mixture estimator (Krichevsky e Trofimov, 1981) in order to determine the number of communities of a SBM based on a finite sample of the network. We propose an estimator without assuming a known upper bound on the number of communities.
We prove the strong consistency of this estimator, in the sense that the empirical value is equal to the correct number of communities in the model with probability one, as long as the number of nodes in the network is sufficiently large. To our knowledge this is the first strong consistency result for an estimator of the number of communities, even in the bounded case.
On the other hand, with respect to the inferential problems for the ERG model we address the following question: can we construct a perfect sampling algorithm to simulate from the distribution of the ERG?
The perfect (also known as exact) simulation algorithms guarantee that after a well defined finite number of steps the value generated by the algorithm has the target distribution. Propp e Wilson (1996) were the first to introduce the perfect simulation through a Markov chain algorithm called Coupling from the past (CFTP) that generates an exact INTRODUCTION 1.3 sample from the stationary distribution of the chain and determines automatically how long it needs to run.
In our approach, we adapt a version of the CFTP algorithm, which is developed for the spin systems in Propp e Wilson (1996), to construct a perfect simulation algorithm for the ERG model using the Glauber dynamics. However, in this case, this algorithm can be implemented efficiently only for monotone models.
In order to cover all models, we propose another perfect simulation algorithm based in Galves et al. (2010), where the authors applied a perfect simulation algorithm for a Gibbs measure with infinite range interactions. In this work, the algorithm is formed by two stages: in the first stage they determined the set of sites whose spins influence each other and, in the second stage, the spins are assigned using the influence information of the first stage.
In Galves et al. (2013) the authors present a perfect simulation algorithm to simulate from the stationary process of a multicolor system on Z d with interactions of infinite range using a Kalikow-type decomposition of the infinite range rates. This decomposition is a convex combination of rates with finite range and it allows us to deal with the infinite range dependence. This decomposition is also applied in the case of processes with long memory as described in the works of Comets et al. (2002) andGarivier (2015).
In spite of the fact that the vertex set of the graph considered in this thesis is finite, we propose a decomposition of the transition probabilities of the Markov chain, constructed using the Glauber dynamics, that considers the local dependence of an edge in the graph through a subset of pair of vertices.

Contributions
The main contributions of this thesis are the following: • The construction of a penalized estimator based on the Krichevsky-Trofimov (KT) mixture distribution for the number of communities of the SBM.
-We construct an estimator without assuming a known upper bound on the number of communities; -We prove that the estimator is strongly consistent.
• The construction of alternative algorithms to the MCMC approach to be applied in the estimation methods for ERG models.
-We construct a perfect sampling algorithm based on the coupling from the past algorithm for monotone ERG models; -We construct an alternative perfect sampling algorithm that can also be applied to non-monotone models.

Organization of the work
This thesis is divided in two parts for the reader's convenience. Part I covers the model selection problem for the SBM. In Chapter 2 we present the definitions and notations of random graphs used in this thesis. This chapter also contains an overview of the inferential problems for this class of models and the definition of the KT mixture distribution. In the last chapter of this part, Chapter 3, we present the penalized estimator without assuming a known upper bound on the number of communities and we prove its strong consistency. In the second part of this thesis we discuss the perfect simulation problem for the class of ERG models. In Chapter 4 are present the definitions of the ERG models and a brief description of the main concepts used in the second part of this work. The construction of the coupling from the past algorithm is described in Chapter 5. In Chapter 6 we focus our attention on the algorithm called Backward and Forward that can be applied to non-monotone ERG models. Finally, a simulation study of both algorithms is presented in Chapter 7.
In Chapter 8 we present the final considerations about the results obtained in this thesis as well as the future potential research problems in this field.
In Appendix A the reader can find the additional results and proofs omitted in the previous chapters of this thesis.

Part I Stochastic Block Model
In this chapter we present the general definitions and notations about random graphs frequently used in this thesis. The specific definitions and notations required to the development of this thesis are given gradually in the sections. We also introduce the Stochastic Block Model and the Krichevsky -Trofimov mixture distribution.

Random Graph Definitions
A graph is a pair (V, E), where V is a finite set of vertices and E is a set of edges that connect pairs of vertices. In this work we consider undirected graphs, i.e, graphs for which the set E satisfies the following properties: Let G |V | be the collection of all undirected graphs with set of vertices V. A graph (V, E) ∈ G |V | can be identified with a symmetric binary matrix x ∈ M |V | {0, 1} such that x(i, j) = 1 if and only if (i, j) ∈ E. The matrix x is called the adjacency matrix of the graph. We will thus denote by x a graph, which is completely determined by the values x(i, j), For an undirected random graph its adjacency matrix X is symmetric, its diagonal entries are zero and its upper diagonal entries are given by a collection of random variables {X(i, j) : In the model selection problem for the SBM we are interesting in the case where the number of vertices of the graph grows to infinity. In that case, we assume that |V | = n and we denote the adjacency matrix of the graph by x n×n to emphasize that it depends on n. In the second part of the thesis we consider that the number of vertices of the graph is fixed and finite. Under this assumption, it is convenient to introduce minor notational changes, and we advise the reader to check Section 4.1.1 for further details.

2.2
A well known and studied model in the literature is the Erdős-Rényi introduced in Erdös e Rényi (1959). In this model the edges are chosen independently of the other edges of the graph and with the same probability, that means, {X(i, j) : 1 ≤ i < j ≤ |V |} is a collection of independent and identically distributed Bernoulli random variables.

Stochastic Block Model
We consider a network with n nodes with adjacency matrix X n×n = (X(i, j)) is given by a symmetric matrix with diagonal entries equal to zero. The classification of the nodes in k 0 communities are given by a latent random vector Z n = (Z 1 , Z 2 , · · · , Z n ) of independent random variables taking values in [k 0 ] := {1, · · · , k 0 } for which P(Z i = k) = π 0 k , π = (π 0 1 , · · · , π 0 k 0 ) and The event {Z i = k} means that the node i belongs to community k.
Given the nodes' labels, each entry of the adjacency matrix X n×n is conditionally independent given the labels of the vertices and it is generated according to the conditional distribution The Erdős-Rényi model is a particular case of the SBM when we have k 0 = 1. In order to guarantee that the model is identifiable, in the sense that it cannot be reduced to a smaller model (i.e., a model with a smaller number of communities), we assume that each community has positive probability to have at least one member. Furthermore, we assume that two communities cannot have the same probabilities of being connected to other communities. Thus, we assume that the following holds: Assumption 2.2.1. P does not have two identical columns and π has all positive entries.
We write the vector of model's parameters as θ = (π, P ) and the parametric space

2.2
For θ ∈ Θ k we write the joint distribution of X n×n and Z n as As it is usual in the definition of likelihood functions, by convention we define 0 0 = 1 in (2.2.1) when some of the parameters are 0.
For θ ∈ Θ k the marginal distribution of X n×n is given by The definition of identifiability for this model, as described in Assumption 2.2.1, is vastly used in the literature; however, in this thesis we use an equivalent definition. We define the order of the SBM as the smallest k for which the equality (2.2.1) holds for a pair of parameters (π 0 , P 0 ) ∈ Θ k and it is denoted by k 0 . If a SBM has order k 0 then it cannot be 2.2 reduced to a model with less communities than k 0 ; this specifically means that P 0 does not have two identical columns.
Example 2.2.2. Consider the SBM with two blocks where the block assignments and connections are represented by Figure (2.1). In this case, we have n a = 4 , n b = 2 n a,a = 12 , O a,a = 6 Using the fact that P is symmetric, the joint distribution described in (2.2.1) is expressed as The next example illustrates the fact that Assumption 2.2.1 is necessary to guarantee identifiability of the model in the sense described above. Observe that this model does not satisfy Assumption 2.2.1. In this way, it can be represented by a smaller order model with parameter θ = ( π, P ) given by P = 0.2 0.4 0.4 0.5 and π = (0.4 0.6) .
The construction of the smaller order model is detailed in Section 3.2.2 for general models. The main idea behind this construction is to replace label 3 by 2. For example, in Figure  (2.2a), consider the graph sampled from the model of order 3 with parameter θ, then we relabeled the nodes 3 by 2 to get the graph in (2.2b). In this case, for the graph x 7×7 represented in Figure (2.2a) and the labels z 7 = (1 2 1 3 3 2) we have that log P θ (x 7×7 , z 7 ) = −8.369482. For the relabeled model, Figure (2.2b), with labels z 7 = (1 2 1 2 2 2) we have that log P θ ( x 7×7 , z 7 ) = −8.369482.

Inferential Problems
Let (x n×n , z 0 n ) be a sample of the SBM of order k 0 with parameter θ 0 = (π 0 , P 0 ). We only observe the structure of the network x n×n and the nodes' labels z 0 n are hidden. From an inferential point of view we can address three problems: 2.3 1. Estimation of the parameter θ 0 = (π 0 , P 0 ); 2. Estimation of the latent nodes' labels z 0 n ; 3. Estimation of the number of communities k 0 .
There is an increasing number of works that have addressed the problem of estimating the latent block configuration and the model's parameters. However, in both problems the number of communities of the model is assumed to be known. In this scenario we can list some relevant works such as the likelihood maximization (Amini et al. (2013) and Bickel e Chen (2009)), variational methods (Daudin et al., 2008;Latouche et al., 2012), spectral clustering (Rohe et al., 2011). There are also some theoretical works about the asymptotic properties of theses methods, as Bickel e Chen (2009) Rohe et al. (2011 and Su et al. (2017).
In this part of the thesis we focus on the estimation of the number of communities of the model (order estimation). For this, we define the estimation procedure and the types of estimators.
Definition 2.3.1. An order estimation procedure is a sequence of estimators k 1 , · · · , k n , · · · that, given observed graphs with 1, · · · , n, · · · nodes, it outputs estimates k n (x n×n ) of k 0 . Definition 2.3.2 (Weak and Strong Consistency). A sequence of estimators k 1 , · · · , k n , · · · is weakly consistent if P θ ( k n = k 0 ) converges to 1 as n → ∞. A sequence of estimators k 1 , · · · , k n , · · · is strongly consistent if k n = k 0 eventually almost surely as n → ∞. Wang et al. (2017) were the first to propose a penalized likelihood criterion to choose the correct number of communities. Their estimator is given bŷ

Estimation of the number of communities
where λ is a tuning parameter. They prove the criterion is weakly consistent, that means, the estimator chooses the correct number of blocks with probability tending to 1, when n goes to infinity. However, in a practical way, the computation of the log likelihood function (2.2.3) and its supremum is usually not a simple task due to the fact that it depends on a sum over an exponential number of terms. To overcome this difficulty, Wang et al. (2017) proposed some alternative ways to approximate the likelihood function in order to preserve the asymptotic consistency of the suggested estimator. They proposed a variational method as described in Bickel et al. (2013) to obain a variational estimator for θ computed using the EM algorithm of Daudin et al. (2008). Another method that preserves the asymptotic properties of (2.3.1) is the computation of the maximum complete likelihood (2.2.1) by plugging the labels' estimates. For this purpose, to estimate the node's labels it is suggested to use the profile maximum likelihood in Bickel e Chen (2009) or the pseudo-likelihood algorithm in Amini et al. (2013) Hu et al. (2016 proposed a corrected Bayesian information criterion (CBIC) where the estimator is given bŷ (2.3. 2) The penalty function in the CBIC estimator improves that used in Wang et al. (2017); however, in practice, the computation of the suggested estimator still remains a demanding task since it depends on the profile maximum likelihood.

The KT mixture distribution
In Chapter 3 we propose an estimator based on the Krichevsky -Trofimov distribution (KT) proposed in Krichevsky e Trofimov (1981). The Krichevsky-Trofimov estimator in the context of a SBM is a regularized estimator for the random adjacency matrix X n×n .
As it is usual for the KT distributions we choose as "prior" for the pair θ = (π, P ) a product measure obtained by a Dirichlet(1/2, · · · , 1/2) distribution (the prior distribution for π) and a product of (k 2 + k)/2 Beta(1/2, 1/2) distributions (the prior for the symmetric matrix P). In other words, we define the distribution For a given sample (x n×n , z n ) of the SBM of order k the Krichevsky-Trofimov mixture distribution on G n only depends on the observed network and it is defined by It is important to emphasize that even though we use prior distributions for the parameters π and P , the KT distribution does not play the role of a posterior distribution.
We start with a result that have an important role in the proof of the consistency of the estimator proposed in Chapter 3. This result gives an upper bound for the maximum log ratio between the maximum likelihood and the Krichevsky-Trofimov mixture distribution.

2.3
Proposition 2.3.3. For all k and all n ≥ max(4, k) we have and Proof. We start by proving the first inequality in (2.3.4). The proof is based on Csiszár et al. (2004, Theorem 6.2). Thus, Now we prove the second inequality in (2.3.4). The proof is based on Liu e Narayan (1994, Lemma 3.4). For θ ∈ Θ k we have that Using that the maximum likelihood estimators of π a and P a,b are given by n a n andÕ a,b n a,b (respectively) we can bound above (2.3.6) and (2.3.7) by n a n na . (2.3.8) Using the fact that the maximum likelihood estimator of P l,r is given byÕ l,r n l,r we write (2.3.7) as (2.3.9) Observe that the Krichevsky-Trofimov mixture distribution defined in (2.3.3) can be written as (2.3.10) Then substituting (2.3.6) and (2.3.7) in (2.3.10) We can write and Thus, we rewrite (2.3.10) as We start with the evaluation of KT k (z n ).
In the same way, for where the last inequality follows from the fact thatñ a,b ≥ 1.

Computation of KT
As discussed before, in practice the computation of the estimator of the number of blocks proposed in the literature can be a challenging task because of the form of the likelihood function. The proof of Proposition 2.3.3 gives us the tools to compute the KT distribution. For notational convenience we rewrite the counters defined in (2.2.2) as By equations (2.3.11) and (2.3.14), we write the KT distribution as Observe that KT k (z n ) gives a marginal distribution for the labels and it is a conjugate distribution between the multinomial and Dirichlet distribution. In the same way, KT k (x n×n |z n ) is the marginal conditional density of x n×n given z n and it is the conjugate distribution of the Bernoulli and Beta distributions.
Using the fact that KT k (z n ) is a distribution we can compute an approximation KT k (x n×n ) of KT k (x n×n ) in the following way: This computation avoid the maximization over Θ k in (2.3.1) and (2.3.2).

Chapter 3
The KT order estimator In this chapter we present the estimator for the number of communities of the SBM based on the Krichevsky -Trofimov mixture distribution without assuming a known upper bound on the number of communities of the model. We also present the proof of strong consistency of the proposed estimator.

Order estimator
The KT order estimator in the context of a SBM is a regularized estimator of a mixture distribution for the random adjacency matrix X n×n . Given a sample (x n×n , z n ) of the SBM the estimator only depends on the observed network x n×n . Thus, the KT order estimator is given byk where KT k (x n×n ) is the mixture distribution for a SBM of order k and pen(k, n) is a penalizing function.
In order to derive the strong consistency result for the KT order estimator, we need a penalty function in (3.1.1) with a given rate of convergence when n grows to infinity. Although there are a range of possibilities for this penalty function, the specific form we use in this thesis is for some > 0. The convenience of the expression above will become clear in the proof of the consistency result. Now we can state the consistency result.

3.2
Theorem 3.1.1 (Consistency Theorem). Suppose the SBM has order k 0 , with parameters (π 0 , P 0 ). Then, for a penalty function of the form (3.1.2) we have that eventually almost surely as n → ∞.
The proof of Theorem 3.1.1 is given in the next section.

Proof of the consistency theorem
The proof of Theorem 3.1.1 is divided in two main parts. The first one, presented in Subsection 3.2.1, proves thatk KT does not overestimate the true order k 0 , eventually almost surely when n → ∞, even without assuming a known upper bound on k 0 . The second part of the proof, presented in Subsection 3.2.2, shows thatk KT does not underestimate k 0 , eventually almost surely when n → ∞. By combining these two results we prove that k KT = k 0 eventually almost surely as n → ∞.

Non-overestimation
The main result in this subsection is given by the following proposition.
Proposition 3.2.1. Let (x n×n , z 0 n ) be a sample of size n from a SBM of order k 0 , with parameters π 0 and P 0 . Then, thek KT order estimator defined in (3.1.1) with penalty function given by (3.1.2) does not overestimate k 0 , eventually almost surely when n → ∞.
The proof of Proposition 3.2.1 follows straightforward from Lemmas 3.2.3, 3.2.4 and 3.2.5 presented below. The proofs of these Lemmas are inspired in the arguments used in the proof of the consistency of the BIC Markov order estimator in Csiszár et al. (2000) that are also applied to prove the consistency of the code-based estimators of the number of hidden states of a Hidden Markov Model in Gassiat e Boucheron (2003). However, first we state and prove a lemma that is useful to bound the probability of overestimation.
where c k 0 ,n is given in (2.3.5).
Proof. Observe that for k > k 0 we have (3.2.1) where the last equality follows from the fact that KT k (·) is a distribution.
Lemma 3.2.3. Under the hypotheses of Proposition 3.2.1 we have that eventually almost surely when n → ∞.

3.2
Proof. Using Lemma 3.2.2 we can write where the last inequality follows from the fact that pen(k, n) is increasing in k. Using the penalty given by (3.1.2) we obtain Let C k 0 be an upper-bound on exp(c k 0 ,n ). Thus, Since pen(k, n)/ log(n) only depends cubically in k we have that Using the fact that exp(c k 0 ,n ) is decreasing on n, the result follows from the first Borel Cantelli lemma.
Lemma 3.2.5. Under the hypotheses of Proposition 3.2.1 we have that eventually almost surely when n → ∞.
Proof. In order to prove the lemma, it is enough to prove that By definition of KT we have where the last inequality holds for n big enough.

Non-underestimation
In this subsection we deal with the proof of the non-underestimation of the proposed estimator.
Proposition 3.2.6. Let (x n×n , z 0 n ) be a sample of size n from a SBM of order k 0 , with parameters (π 0 , P 0 ). Then, thek KT order estimator defined in (3.1.1) with penalty function given by (3.1.2) does not underestimate k 0 , eventually almost surely when n → ∞.
In order to prove this result we need Lemma 3.2.7 below, that explore limiting properties of the under-fitted model. That is we handle with the problem of fitting, under Θ k 0 −1 , a SBM with order k 0 .
We start by constructing a (k 0 − 1)-order SBM ( Z n , X n×n ) with parameters (π,P ) from (π 0 , P 0 ), by a merging procedure that is defined below. Let Q( Z n , Z n ) be the (k 0 − 1) × k 0 joint matrix of Z n and Z n whose the (ã, a)-th entry is given by The matrix Q( Z n , Z n ) can be seen as a coupling between the random labels Z n of the model of order k 0 and the random labels Z n of the model with k 0 − 1 blocks.
An intuitive construction of a (k 0 − 1)-block model is obtained by merging blocks of a model of order k 0 . This merging can be constructed in several ways, but we consider the construction given in Wang et al. (2017); however, instead of using the block proportions as considered in their work, we use the true probabilities (π 0 , P 0 ).
Given the probabilities π 0 = (π 0 1 , π 0 2 , · · · , π 0 k 0 ) we define a merging operation M a,b (P 0 , π 0 ) which combines blocks a and b in P 0 by taking weighted averages with probabilities given by π 0 . For example, for P = M k 0 ,k 0 −1 (π 0 , P 0 ) In the same way, we consider the merged probabilities π = M k 0 ,k 0 −1 (π 0 ) as In the general merging (π, P ) = (M a,b (π 0 ), M a,b (P 0 , π 0 )), b > a, the nodes are relabeled using Given (x n×n , z n 0) originated from the SBM of order k 0 and parameters (π 0 , P 0 ), we define the profile likelihood estimator of the label assignment under the (k 0 − 1)-block model as The next lemma gives an upper bound for the limit of logarithm of the ratio between the true likelihood under the corrected model and the maximum profile likelihood function under the underfitting model that depends on the merging operation described above.
Lemma 3.2.7. Let (x n×n , z 0 n ) be a sample of size n from a SBM of order k 0 , with parameters (π 0 , P 0 ). We have that there exist r, s ∈ [k 0 ] such that eventually almost surely when n → ∞. In the formula above γ(x) = x log x+(1−x) log(1−x).

3.2
Proof of Lemma 3.2.7. Definê Using the fact that x n×n given z 0 n has distribution P 0 and z 0 n is originated from π 0 we have that (3.2.5) and, eventually almost surely when n → ∞, The first two terms on the right hand side of (3.2.5) is of smaller order compared to n 2 , so eventually almost surely when n → ∞ (3.2.7) First, observe that each term in the first sum of the right hand side of (3.2.7) is limited and it is of order smaller than n 2 .
Using the fact that each term of the second sum of the right hand side of (3.2.7) is limited we have that lim sup n→∞ 1 n 2 log sup Hence, there exists a subsequence (z n j ) j≥1 of (z n ) n≥1 such that lim j→∞ 1 n 2 log sup Given any string z n ∈ [k 0 − 1] n , each of the termsπ a (z n ) andP a,b (z n ) are bounded in absolute value by 1. In particular, this holds true for z n = z n j being any element in the subsequence (z n j ) constructed above. This implies that we can extract a subsequence (z m k ) of (z n j ) for which for some numbers π a , P a,b , and any a, b ∈ {1, . . . , k 0 − 1}. Combined with (3.2.8), we thus get that lim sup n→∞ 1 n 2 log sup Combining (3.2.6) and (3.2.9) we have that eventually almost surely when n → ∞. To obtain a lower bound of (3.2.10), we need to obtain ( π, P ) that minimizes This is equivalent to obtain ( π, P ) that maximizes The numerator equals and the denominator equals Then rewrite (3.2.11) as . (3.2.12) Observe that the conditional probabilities P a, b are completely determined by the coupling Q a, a (Z n , Z n ) and the parameters P 0 a,b . Therefore, to find a pair ( π, P ) maximizing (3.2.11) is equivalent to find an optimal coupling maximizing (3.2.12).
In Wang et al. (2017) it has been shown that there exists r and s, r, s ∈ [k 0 ], such that (3.2.12) achieves its maximum for π = M r,s (π 0 ) and P = M r,s (π 0 , P 0 ). This concludes the proof of the first inequality in (3.2.4).
In order to prove the second inequality in (3.2.4), we consider, for convenience and without loss of generality, r = k 0 and s = k 0 − 1. Define the function ϕ(x, y) = x log x y We rewrite and, by definition of the merging M k 0 −1,k 0 (π 0 , P 0 ), Using the log-sum inequality we have that The equality in (3.2.13) and (3.2.14) hold if and only if for 1 ≤ a ≤ b ≤ k 0 P a,k 0 = P a,k 0 −1 .
Then we conclude that the matrix P 0 has the last two columns equal. However, by assumption, k 0 is the order of the SBM that originated the graph x n×n , that means, P 0 does not have identical columns. So, there exists a 1 ∈ [k 0 ], such that P a 1 ,k 0 = P a 1 ,k 0 −1 . Hence the result follows.
Proof of Prosposition 3.2.6. Let (x n×n , z 0 n ) be a sample of size n from a SBM of order k 0 . To prove Proposition 3.2.6 it is enough to show that for all k < k 0 log KT k 0 (x n×n ) − pen(k 0 , n) ≥ log KT k (x n×n ) − pen(k , n) eventually almost surely when n → ∞.
Using the fact that lim n→∞ pen(k 0 , n) − pen(k , n) n 2 = 0 it suffices to show that, eventually almost surely when n → ∞, Using the fact that P θ 0 (x n×n ) ≤ sup We also have that . .
Thus, to show (3.2.15) it suffices to show, for k < k 0 , that eventually almost surely when n → ∞.

3.2
Using z n = arg max Taking the log log sup Thus, eventually almost surely when n → ∞. Using Lemma (3.2.7) the result follows.
To complete the proof, for k < k 0 − 1 we write where the first inequality follows from the fact that sup θ∈Θ k 0 −1 P θ (x n×n ) ≥ sup θ∈Θ k P θ (x n×n ).

Exponential Random Graphs
In this chapter we introduce the concept of Exponential Random Graphs (ERG) and we construct a time-reversible Markov chain for which the invariant measure is the ERG distribution using the Glauber dynamics.

Definitions and Notations
In this model, we consider that the number of vertices of the graph is fixed and finite, that is, V = {1, 2, . . . , N }.
Let G N be the collection of all undirected graphs with set of vertices V. For convenience, we omit the notation of dependence of the graph on N . So, let x be an observed graph in G N . We write x −ij to represent the set of values {x(l, k) : (i, j) = (l, k)}. For a given graph x and a set of vertices U ⊆ V , we denote by x(U ) the subgraph induced by U , that is x(U ) is a graph with set of vertices U and such that x(U )(i, j) = x(i, j) for all i, j ∈ U .
The empty graph x (0) is such that x (0) (i, j) = 0, for 1 ≤ i < j ≤ N . In the same way, the complete graph j ∈ V and i < j} be the set of possible edges in a graph with set of vertices V. For any graph x ∈ G N , a pair of vertices (i, j) ∈ E and a ∈ {0, 1}, the modified graph x a ij is given by For the ERG model the probability of selecting a graph in G N depends on its structure; for example, the number of edges, the number of triangles, the length of the longest path 4.1 and so on. The probability of observing a graph x is given by where θ is a s × 1 vector of parameters, s(x) is a s × 1 vector of graph's statistics and z N (θ) is the normalizing constant of the model given by z N (θ) = x∈G N exp(θ T s(x)).
A specific model of ERG explored in this thesis is called edges-2-stars-triangles model. In this model, the graph's statistics are given by the number of edges, 2-stars and triangles. In terms of the probability (4.1.1), we write The Erdős-Rényi model is a particular case of the ERG model when we have θ 2 = 0 and θ 3 = 0.
In different works, such as in Chatterjee et al. (2013) and Bhamidi et al. (2011), an alternative definition of the ERG distribution is used for models for which the graph's statistics of x are only represented by subgraphs of x. In this representation, the vector of statistics used in (4.1.1) can be replaced by the number of subgraphs contained in the graph x. For example, the statistic that counts the number of triangles in a graph can be computed by counting the number of completed graphs with three vertices that are contained in x.
In order to define subgraphs counts in a graph, let V m be the set of all possible permutations of m distinct elements of V . For v m ∈ V m , define x(v m ) as the subgraph of x induced by v m , that is x(v m ) is a graph with set of vertices v m such that if there exist the edge (i, j) in the graph x, for two vertices i and j in v m , then there exist the edge (i, j) in x(v m ). For a graph g with m vertices, we say x(v m ) contains g (and we write x(v m ) g) if g(i, j) = 1 implies x(v m )(i, j) = 1. Then, for x ∈ G N and g ∈ G m , m ≤ N , we define the number of subgraphs g in x by the counter (4.1.2) Let g 1 , . . . , g s be a sequence of fixed graphs, where g i has m i vertices, m i ≤ N and β ∈ R s a vector of parameters. By convention we set g 1 as the graph with only two vertices and one edge. Following Chatterjee et al. (2013) and Bhamidi et al. (2011) we define the probability of graph x by It is possible to relate the parameters θ and β of the two equivalent definitions of the probability of the ERG. For instance, consider the model that counts the number of edges and triangles of the graph. Since (4.1.2) counts twice the number of edges of the graph and six times the number of triangles, we have that θ 1 = 2β 1 and θ 2 = 6β 2 N . More generally, if g s is a fixed graph with m s vertices and A(g s ) is the number of automorphisms of g s , then θ s = A(g s )β s N ms−2 . A graph automorphism is a permutation of the vertices of the graph that preserves the edges of the graph, as shown in Figure (4.1).
The model (4.1.3) is used in some proofs of this thesis.

Glauber dynamics
In the ERG models, the computation of the normalizing constant z N (θ) = x∈G N exp(θ T s(x)) (or Z N (β)) might be extremely demanding due to the size of G N . For example, for a graph with 10 vertices, we have that |G N | = 2 45 . The algorithms used to simulate from the ERG distribution avoid the computation of this constant applying the MCMC methodology. In this work we develop techniques that consider the main idea of the MCMC algorithms: the construction of a time-reversible Markov chain for which the invariant measure is the ERG distribution.
In this section we show how to construct the time-reversible Markov chain with stationary distribution p N (· ; θ) using a local update algorithm called Glauber dynamics, also known as Gibbs sampler. This Markov chain has as states the graphs with N vertices, so the state space is the set G N .
Using the Glauber dynamics the probability of a transition from the graph x to the modified graph x a ij is .

4.2
In the case of ERG we can write .
In the same way, .
For the specific model edges-2-stars-triangles, we have that . (4.2.1) The construction of a Markov chain with invariant distribution p N (· ; θ) can be done with the help of the local update function φ : (4.

2.2)
A transition in the Markov chain from graph x to graph y is obtained by the random function y = φ(x, e, u) , with e ∼ Uniform(E), u ∼ Uniform(0, 1) .
In this way, the Markov chain with invariant distribution p N (· ; θ) is constructed in the following manner 1. Set n = 1 and x 0 as the initial state.
2. Select a pair of vertices (i, j) uniformly on the set E.
3. Generate the random number u n from the Uniform distribution on the interval [0, 1].
5. Update n to n + 1 6. Repeat 2 − 6 until n > T 7. Return x 0 , · · · , x T The time-reversible Markov chain (X n ) n≥0 with the desired invariant measure p N (· ; θ) has the transition probabilities given by otherwise. (4.2.3) For the reader's convenience we prove in Proposition 4.2.1 that the construction described above generates a Markov chain with the desired invariant measure.
Proposition 4.2.1. The Markov chain (X n ) n≥0 with transition probabilities given by (4.2.3) is reversible with respect to the ERG probability distribution p N (·|θ).
Proof. We need to verify that p N (x|θ)P (x, y) = p N (y|θ)P (y, x), for all x, y ∈ G N .
If y is such that x −ij = y −ij the equality above is verified, since P (x, y) = P (y, x) = 0. Without loss of generality, let x be a graph with x(i, j) = a, for some i, j ∈ V . Consider the case that y −ij = x −ij . If y(i, j) = a, then x = y and the equality follows. If y(i, j) = 1 − a we have Thus the result follows.
In this chapter we present the construction of the Coupling from the past (CFTP) algorithm for the ERG models.

The algorithm
In order to get a sample from the stationary distribution of a Markov chain, an alternative approach introduced by Propp e Wilson (1996) is called Coupling From The Past (CFTP). This method yields a value distributed under the exact target distribution, and is thus called perfect (also known as exact) simulation. Like MCMC, it does not require computing explicitly the normalising constant; but it does not require any burn-in phase either, nor any detection of convergence to the target distribution. In our approach, we adapt a version of the CFTP algorithm, which is developed for the spin systems in Propp e Wilson (1996), to construct a perfect simulation algorithm for the ERG model using the Glauber dynamics. The ERG model can be interpreted as a system of particles, where in this case the particles are the edges having spin 0 or 1.
For random vectors e −1 −n = (e −n , e −n+1 , . . . , e −1 ) and u −1 −n = (u −n , u −n+1 , . . . , u −1 ), with e −k ∈ E and u −k ∈ [0, 1], we define the random map F 0 −n given by the following induction: The CFTP protocol of (Propp e Wilson, 1996) relies on the following elementary observation. If, for some time −n and for some uniformly distributed e −1 −n = (e −n . . . , e −1 ) and u −1 −n = (u −n , . . . , u −1 ), the mapping F 0 −n (·, e −1 −n , u −1 −n ) is constant, that is if it takes the same value at time 0 on all possible graphs x, then this constant value is readily seen to be a sample from the invariant measure of the Markov chain. Moreover, if F −n is constant for some positive n, then it is also constant for all larger values of n. Thus, it suffices to find a value of n large enough so as to obtain a constant map, and to return the constant value of this map. For example, one may try some arbitrary value n 1 , check if the map F 0 −n 1 (·, e −1 −n 1 , u −1 −n 1 ) is constant, try n 2 = 2n 1 otherwise, and so on... Since the state space has the huge size |G N | = 2 N (N −1) 2 , it would be computationally intractable to compute the value of F 0 −n (x, e −1 −n , u −1 −n ) for all x ∈ G N in order to determine if they coincide. This is where the monotonicity property of the distribution helps: it is sufficient to inspect the maximal and minimal elements of G N . If they both yield the same value, then all other initial states will also coincide with them, and the mapping will be constant.
To apply the monotone CFTP algorithm we define an ordering on G N in the following way: two graphs satisfy x y if, and only if, x(i, j) ≤ y(i, j), for all i, j ∈ V . In other words, x y if and only if x(i, j) = 1 implies y(i, j) = 1 . (5.1.1) Notice that the ordering defined above is not a total ordering; that is, there are graphs in G N that cannot be pairwise compared. On the other hand, there exists a maximal graph x (1) (the complete graph) such that z x (1) , for all z ∈ G N and a minimal graph x (0) (the empty graph) such that x (0) z, for all z ∈ G N .
Considering this partial order, we say p N (· |β) is monotone if the conditional distribution of x(i, j) = 1 given x −ij is a monotone increasing function. That is, p N (· |β) is monotone if, and only if x y implies Then, Inequality (5.1.2) is equivalent to The main difficult to verify that the distribution of the ERG is monotone is the size of G N , since the equation (5.1.3) should hold for all graphs x, y ∈ G N that satisfy x y. In such a way, the following proposition gives a sufficient condition on the parameter vector θ under which the corresponding ERG distribution is monotone.
Proof. Let x, z ∈ G N such that x z. Without loss of generality, we consider the parametrization of the ERG given by (4.1.3).
For a pair of vertices (i, j), we define a new count that considers only the subgraphs of x that contain the vertices i and j, that is Since x z we have that N g k (x 1 ij , (i, j)) ≤ N g k (z 1 ij , (i, j)). For β k ≥ 0, k = 2, · · · , s, we have that Finally, Since θ s = A(g s )β s N ms−2 , the result follows.

5.2
To apply the monotone CFTP algorithm, we use the partial order defined by (5.1.1) and the extremal elements x (0) and x (1) . The resulting procedure, which simulates the ERGM using the CFTP protocol, is described in Algorithm 1.

11:
Simulate u −n with distribution uniform on [0, 1] 12: be the stopping time of Algorithm 1. Proposition 5.1.3 below guarantees that the law of the output of Algorithm 1 is the target distribution p N (·; θ). The proof of Proposition 5.1.3 follows directly from Theorem 2 in Propp e Wilson (1996) and is omitted here.

Convergence Speed
By the construction of the perfect simulation algorithm it is expected that the stopping time T stop N of Algorithm 1 is related with the mixing time of the chain constructed using the Glauber dynamics. The proof of this relation is based in the general proof given by Propp e Wilson (1996) and for convenience of the reader we give the complete proof here.
(5.2.1) For x ∈ G N , let the Markov chain {Y x n } n∈N be given by and denote by p x n the distribution of this Markov chain at time n. Now define where · TV stands for the total variation distance. Let T mix N be given by 2) The following theorem shows that the expected value of T stop N is upper bounded by T mix N , up to a explicit multiplicative constant that depends on the number of vertices of the graph.
Theorem 5.2.1. Let T mix N be the mixing time defined by (5.2.2) for the forward map (5.2.1). Then Proof. Define the stopping time of the forward algorithm by T stop N = min{n > 0 : F n 0 (x (0) , e n 1 , u n 1 ) = F n 0 (x (1) , e n 1 , u n 1 )} To prove the theorem claim we use the random variable T stop N , since T stop N and T stop N have the same probability distribution. In fact, Let {Y 1 n } n∈N and {Y 0 n } n∈N be the Markov chains obtained by (5.2.1) with initial states given by x (0) and x (1) , respectively. Define l(y) as the length of the longest increasing chain such that the top element is y. In the case Y 0 n we have that Y 0 n has at least one different edge of Y 1 n , since our algorithm use a local update. Then, l(Y 0 n ) + 1 ≤ l(Y 1 n ). So, we have that l(x) = l(x (1) ) and l(x (1) ) is the length of the longest increasing chain started on Since P( T stop N > n) is submultiplicative (Theorem 6 in Propp e Wilson (1996)) we have that Using the submultiplicative property of d(n) (Lemma 4.12 in Levin et al. (2009) and by (5.2.5) and (5.2.6) we conclude that Theorem 5.2.1 guarantees that the CFTP algorithm is successful when it is applied for models for which the mixing time of the chain is small, that is, when the distribution of the chain constructed using the Glauber dynamics converges quickly to the stationary distribution. For this models, the CFTP algorithm can be implemented instead of using the MCMC method to get a exact sample from the ERG models.
The upper bound in Theorem 5.2.1 could be also combined with other results on the mixing time of the chain to obtain an estimate of the expected value of T stop N , when they are available. As an example, we cite the results obtained by Bhamidi et al. (2011), where they present a study of the mixing time of the Markov chain constructed using the Glauber dynamics for ERG model under the conditions of Proposition 5.1.1 as we consider here.
They show that for models where β belongs to the high temperature regime (we will not get into details about this definition) the mixing time of the chain is Θ (N 2 log N ). On the other hand, for models under the low temperature regime, the mixing time is exponentially slow.
The mixing time of models for which the parameter vector does not satisfy the conditions of Proposition 5.1.1, that is, β i ≤ 0, for i = 2, · · · , s, not in either phase are not studied in this work. Without loss of generality, the same result follows considering the model (4.1.1) with the appropriate relation between β and θ. The mixing time of models with parameters not in either phase are not studied in this work, as well as, the models with parameters that do not satisfy the conditions of Proposition 5.1.1. Without loss of generality, the same result follows considering the model (4.1.1) with the appropriate relation between β and θ.
In order to construct an algorithm that can be applied for non monotone models a perfect simulation algorithm called Backward and Forward algorithm is described in the next chapter.
We come back to the CFTP algorithm in Chapter 7, where we present a few simulation results about both algorithms studied in this part of the thesis.
In this chapter we present an alternative algorithm to simulate a graph from the ERG model for which it is not required monotonicity properties. This algorithm is based on the Kalikow-type decomposition of the transition probabilities of the Markov chain, constructed using the Glauber dynamics, having as stationary distribution the ERG distribution.

The algorithm
In this chapter we propose another perfect simulation algorithm based in Galves et al. (2010) and Galves et al. (2013). Galves et al. (2010) applied a perfect simulation algorithm for a Gibbs measure with infinite range interactions. In Galves et al. (2013) the authors present a perfect simulation algorithm to simulate from the stationary process of a multicolor system on Z d with interactions of infinite range. In both works the approach is based on the Kalikow-type decomposition of the infinite range rates. This decomposition is a convex combination of rates with finite range and it allows us to deal with the infinite range dependence. This decomposition is also applied in the case of processes with long memory as described in the works of Comets et al. (2002) andGarivier (2015).
In spite of the fact that the vertex set of the graph considered in this thesis is finite, we propose a decomposition of the transition probabilities of the Markov chain, constructed using the Glauber dynamics, that considers the local dependence of an edge in the graph through a subset of pair of vertices.

Kalikow-type decomposition
In the model edges-2-stars-triangles the probability of the transition from a graph x to x a ij , defined in (4.2.1), depends on the possible edges of x for which the structure of triangles or 2-stars are obtained using the edge (i, j). In this way, the presence or absence of the edge (i, j) influences the number of triangles and 2-stars of the graph. The set of possible edges that can formed triangles and 2-stars using the edge

6.2
Note that the use of the word "possible" edges here is just to emphasize that we need to look to these pairs of vertices to count triangles and 2-stars that depend on the pair (i, j).
The idea is to restrict the set of edges E N −2 ij that we need to look in the graph to compute the transition probability p ij (1|θ, x −ij ). To this end, we rewrite the set of possible edges E N −2 ij , by defining the subsets E 0 ij , E 1 ij , · · · , E N −2 ij in the following way By the construction described above we have that Example 6.2.1. Suppose that we have a graph with set of vertices V = {1, 2, 3, 4, 5}. We fix the pair of vertices (1, 3) and we construct the subsets defined in (6.2.1) in the following way The sets defined above can be interpreted using the Figure (6.1). The set E 1 13 is composed by the edges for which the structures of triangles and 2-stars are obtained considering the edge (i, j) and the vertex 2. In the same way, the set E 2 13 is obtained by considering the vertices 2 and 4. The last set E 3 13 is obtained by considering all the remaining vertices V \ (i, j), that is, 2, 4 and 5.
The sets defined in (6.2.1) are interpreted in the following way: the first set E 0 ij means that we do not need to consider the other edges in the graph to add (or remove) the edge (i, j). The set E k ij represents the set of pairs of vertices that we need to look in the graph to add (or remove) the edge (i, j) whether I just want to look at 2k pairs of vertices in the graph.
At this point, we need to define the probability of adding or removing the edge (i, j) in the graph given the set E k ij .  Define, for a ∈ {0, 1}, (i, j) ∈ E and 1 ≤ k ≤ N − 2 The quantities defined by (6.2.3) and (6.2.4) are all well defined in terms of theory. However, in the practical use, they can be difficult to calculate, due to the fact that its expressions involve a minimum over the set G N . It is also computationally demanding, since 6.2 the size of G N is 2 N (N −1)/2 . Thereby, the target point before proceeding with the Kalikow-type decomposition is to show that all the quantities involved in this construction can be easily calculated for some models of ERG, even in the case of large N .
Proposition 6.2.3. Consider the ERG model edges-2-stars-triangles with θ 1 ∈ R and θ 2 , θ 3 ≤ 0. For (i, j) ∈ E we have that Proof. This proof follows the same arguments of the proof of Proposition 6.2.2 Now, we describe a recursive way to compute (6.2.3), considering the model edges-2stars-triangles, for which it is not necessary to explore the set of all graphs G N .
We start by finding the graph x that minimizes r 1 ij (0|θ, x(E 1 ij )) + r 1 ij (1|θ, x(E 1 ij )). The idea is calculate the minimum over a set of three graphs instead of 2 N (N − 1) /2 graphs. Recall that r 1 ij (0|θ, x(E 1 ij )) depends on the graph x through the edges in E 1 ij . So, it is a easy task to compute y 1 = arg min x(E 1 ij )) ) since we just need to calculate the arg min over the graphs x with the possible edges on E 1 ij described in Table 6.1.
It is important to make two remarks: 1. the remaining edges of the graph y 1 can assume any value in {0, 1}; 2. y 1 does not depends on the choice of the pair (i, j), since we only consider undirected graphs.
Proposition 6.2.4. Consider a ERG model edges-2-stars-triangles. For any (i, j) ∈ E and any graph x ∈ G N the following decomposition holds Remark 6.2.5. The probabilities q k ij (·|θ, x(E k ij )) are defined by (6.2.10) in the proof of Proposition 6.2.4.
The first component of the mixture described in (6.2.5) is the only term that does not depend on the structure of the graph and it can be interpreted as the mixture term associated with the distribution of the Erdős-Rényi model with parameter q 0 (1|θ).

6.2
By construction, So, we define the probability distribution .
Finally, we write Note that in the above decomposition the values of λ k ij (θ, x(E k ij )) still depends on the graph x through E k ij . In order to eliminate this dependence, we define the following quantities Observe that (6.2.8) By (6.2.6) (6.2.9) In this way, for every (i, j) ∈ E we construct the following partition of the interval [0, 1] that does not depend on x(B k ij ) and we construct the partition of the interval [0, 1] that depends on x(B k ij ), for every To define the probability measure q k ij (·|θ, x(E k ij )) on [α k−1 ij (θ), α k ij (θ) ) we use the probabilities q l ij (·|θ, x(E k ij )), l = 1, . . . , N − 2. Since q l ij (·|θ, x(E k ij )) is defined on the interval [β k−1 ij (θ, x(E k ij )), β k ij (θ, x(E k ij )) ), it is necessary to consider only q l ij (·|θ, x(E k ij )), for l such that α k ij (θ) ≤ β l ij (θ, x(E l ij )) ≤ α k+1 ij (θ). Fix k ≥ 0 and define l k 1 (x) = min{m : α k−1 ij (θ) ≤ β m ij (θ, x(E m ij ))} and l k 2 (x) = max{m : Thus, by (6.2.9), we represent the partition of the interval [α k−1 ij (θ), α k ij (θ) ) for the graph x as follows (for easy of notation we consider in this representation l k 1 (x) = l 1 and l k Formally, In each sub-interval, we use the corresponding probability q l ij (a|θ, x(E l ij )) to define (6.2.10) Notice that the probability defined above depends only on E k ij , since l k 2 (x) ≤ k by (6.2.8) and for l ≤ k we have that E l ij ⊆ E k ij . Since l k 1 (x) − 1 = l k−2 2 (x) and by (6.2.7), we finally get

Backward and Forward algorithms
In this section we consider the time-reversible Markov chain (X n ) n≥0 with respect to the probability distribution p N (·|θ) for which the construction is described in Section 4.2. As a consequence of Proposition 6.2.4 we can rewrite the transition probabilities (6.3.1) by 0, otherwise. (6.3.1) In a nutshell, a transition from a graph x n can be done in the following manner: 1. (Select a pair of vertices to update) Select a pair of vertices (i, j) uniformly on E; 2. (Select a mixture component) Select k ∈ {0, 1, · · · , N − 2} according to the probability distribution P (K = k) = λ k (θ); 3. (Add or remove an edge) The existence of an edge between i and j depends on the subgraph x n (E k ij ). The probability of x n+1 (i, j) = 1 given x n (E k ij ) is q k ij (1|θ, x n (E k ij )).
Step (2) gives us the information about the set of pairs of vertices of x n (a subgraph of x) for which the existence of an edge between i and j depends on. Observe that if, at the time n + 1, we chose k = 0, then the existence of an edge between i and j does not depend on the graph x n and it also does not depend on the predecessor graphs x n−1 , x n−2 , · · · . Using this dynamics based on the decomposition given in Proposition 6.2.4 we construct a perfect simulation algorithm composed by two procedures. To well explain both procedures, we suppose that we want to simulate the existence of an edge between a fixed pair of vertices i and j.
In the first procedure, we determine the set C ij of pair of vertices of the graph that influence the existence (or absence) of an edge between i and j, at time n.
In order to do this, we set C ij n = {(i, j)} and we select k according to step (2). If k = 0, we do not need to consider the structure of the graph at time n − 1, then we stop the procedure. If k = 0, the existence of the edge (i, j) depends on the pairs of vertices E k ij in the graph at time n − 1, then we need to add E k ij in the set C ij n . So, we have C ij n−1 = C ij n ∪ E k ij . Now, we choose randomly a pair (l, m) in C ij n−1 to determine the existence of an edge with the information about the structure of the graph at time n − 2. Thus, we follow the same sequence of steps as before. We select k according to step (2). If k = 0, we do not need to consider the structure of the graph at time n − 2, then we remove (l, m) from C ij n−1 . If k = 0, the existence of the edge (l, m) depends on the pairs of vertices E k lm in the graph at time n − 2 , then we need to add E k lm in the set C ij n−1 . The procedure stops when the set C ij m , m < n, is empty, that is, we do not need to use more information about the predecessor graphs.
The second procedure of the algorithm consists in adding, or removing, edges in the graph using the probabilities {q k ij : k = 1, . . . , N − 2, (i, j) ∈ E}, from the past to the future. This algorithm starts by adding, or removing edges, between the pairs of vertices that are chosen in the end of the first procedure. Without loss of generality we set n = 0. To sample the graph we use both procedures with C E 0 = E. These two procedures are formally described in Algorithms (2) and (3).

Construction of the process
In this section we describe formally the stochastic process behind the backward sketch process procedure described in Algorithm (2). Define C ij 0 = {(i, j)} and define C ij n as the set of pairs of vertices at time −n for which the structure of the graph at time 0 depends on. This process has as state space the set P(E), that is, the set of subsets of E.
The main idea of this construction is to select, at each time n, a pair of vertices (l, m) from C ij n and to change the set C ij n according to a transformation π lm,k (C ij n ). For B ∈ P(E), we define In a nutshell, this transformation change the set B in the following way: if k = 0, then the edge (l, m) is removed from B; otherwise the set of pair of vertices E k lm is added to the set B.
We construct the Markov chain, at time n, in the following manner 1. Choose (l, m) uniformly on C ij n−1 ; 2. Choose k according to the probability distribution P (K = k) = λ k (θ); 3. Let C ij n = π (lm,k) (C ij n−1 ).
By the construction above, (C ij n ) n≥0 is a Markov chain with initial state C ij 0 = {(i, j)} and transitions given by For the set E of all possible edges of the graph define the process The steps 6 − 11 of the Algorithm (2) are justified by the transition probability (6.4.1) of the chain.
Define the stopping times Notice that N stop is exactly the number of steps of Algorithm (2). In this way, the number of steps N stop must be finite for the perfect simulation algorithm to be successful. For this reason, we need to study the conditions to guarantee that N stop < ∞.
The following theorem assures that the law of output of Algorithm (3) is the invariant measure of the process (x n ) n≥0 and, as a consequence of the construction of the process, the invariant measure is the ERG distribution. This theorem is proved in Galves et al. (2010) and Galves et al. (2013) and for convenience of the reader we give the complete proof here.
Theorem 6.4.1. Assume that P (N stop < ∞) = 1. Thus, the law of the output {x(i, j) : (i, j) ∈ E} printed at the end of Algorithms (2) and (3) is the invariant measure of the process (x n ) n≥0 .
the stopping time of Algorithm 2. In this case, the output x y of the modified Algorithm 3 is equal to the output x of the unmodified Algorithm 3.
To prove that the law of x y t converges to µ, the law of the output {x(i, j) : (i, j) ∈ E}, we use the following result: we say that a sequence of random variables Z n converges in law , as n → ∞, for all continuous and bounded function f .
So, let f : G N → R be a bounded continuous function. We have that We conclude that Then, the law of the process (x y t ) t≥0 , starting at time 0 with the graph y converges to the law µ of the output x of Algorithm 3, as t → ∞. So, the invariant measure of the process is equal to the law of the output x of Algorithm 3.
The following theorem assures, under a certain condition, that the Algorithm (2) stops almost surely. The proof of this result follows the steps of the proof present in Galves et al. (2013).
We have that Algorithm (2) stops after a finite number of steps almost surely and Proof. Let L ij n = |C ij n | be the number of possible edges in the set C ij n after n steps of the algorithm, for (i, j) ∈ E.
The main idea of this proof is to construct a multi-type branching process Z ij n . To describe the offspring distribution, define ( ξ lm n ) n≥1,(l,m)∈E the sequence of independent random variables, taking values in {0, |E 1 lm | + 1, . . . , |E N −2 lm | + 1}. The individuals of the branching process are represented by the possible edges of the graph and the individual (l, m) has type (l, m). We start with one individual with type (i, j), so Z ij n = 1. We construct the offspring of (l, m) "adding" new possibles edges, that is ξ lm n ∈ {|E 1 lm | + 1, . . . , |E N −2 lm | + 1}. The children of (l, m) have type E k lm (l, m). In this way, we define the offspring distribution by Thus, we define the multi-type branching process by and, by condition (6.4.3) Define the stopping time V ij = inf{n : Z ij n = 0}. We have that P (V ij < ∞) = 1, since E[ ξ lm 1 ] < 1, for all (l, m) ∈ E. Now, we describe the multi-type branching process Z ij n through a random walk. The offspring of each individual in the generation n is obtained one by one, in such a way that if Z ij n = k it takes k steps to obtain Z ij n+1 . To define the random walk associated with Z ij n define P (ξ lm n = |E k lm |) = λ k (θ) P (ξ lm n = −1) = λ 0 (θ) For any (i, j) ∈ E, let I ij n be the edge that has been chosen at the n-th jump of the process (C ij u ) u≥1 . The random variable I ij n is conditionally independent given C ij n−1 and P (I ij n = (l, m)|C ij n−1 ) = 1 |C ij n−1 | Now, define the random walk such that S ij 0 = 0 and We have that By defining the stopping time V ij stop = min{k : S ij k = 0}, we have L ij n ≤ S ij n as long as Recall the following result of the martingale theory: if N is a stopping time and X n is a super martingale, then X N ∧n is a super martingale. Furthermore, E[X N ∧n ] ≤ E[X 0 ] (Theorem 5.2.6 in Durrett (2010)).
In this way, we have that Combining (6.4.4) and (6.4.5) we get We have that S ij Tn ≤ Z ij n , for T 0 = 0 and T n+1 = T n + S ij Tn .
By construction N ij stop ≤ V ij stop and by (6.4.2) we conclude that The study of the Backward and Forward algorithm are detailed in Chapter 7.
In this section we present the simulation results of the two algorithms described in this thesis. Both algorithms were implemented using the software R (R Core Team, 2015).

The algorithm
We start the simulations comparing the MCMC algorithm with the CFTP algorithm. As we know, the output of the MCMC method depends on both the initial graph used to start the algorithm and the number of steps used to run the chain. This can be observed in practice in Figure 7.1: the convergence time for both MCMC and CFTP are of the same order of magnitude, as suggested by Theorem 6.4.2. In this figure we compare the number of edges and 2-stars of the graphs obtained by MCMC at different sample sizes of the forward Markov chain and by CFTP at its convergence time. In this case, we consider the model edges and 2-stars with parameters (θ 1 , θ 2 ) = (−2.2, 0.03) for a graph with 80 vertices and the mean proportion of edges in the graphs is approximately p = 0.86. We observe in Figure  8.1a that MCMC remains a long time strongly dependent on the initial value of the chain when this value is chosen in a region of low probability. On the other hand, when the initial value is chosen appropriately, then MCMC and CFTP have comparable performances, as shown in Figure 8.1b. In this example, we use a sample with 500 graphs for each method.  In order to study the convergence of the Backward and Forward algorithm, the reader should observe in Figure 7.2 the relation between the size of the set C n , n = 1, · · · , N stop , with the parameter δ, defined in Theorem 6.4.2, for the model edges-2-stars-triangles with 10 vertices and different values of the parameters. In Figure 7.2a the size of set C n converges quickly to 0 for the model with parameter θ = (−1.8, 0.02, 0.03). Observe that δ = 0.86 so this example satisfies the condition (6.4.3) of Theorem 6.4.2.
In the second model with θ = (−1.8, 0.05, 0.04), Figure 7.2b, the condition (6.4.3) is not verified (δ = 2.1); however, the algorithm BF stops after 25723 steps. This example reinforces the fact that condition (6.4.3) is not a necessary condition for the algorithm stops.
Finally, the model with θ = (−1.8, 0.07, 0.05) does not satisfy the condition (6.4.3) (δ = 3.15) and, as we can observe in Figure 7.2c, the values of |C n | oscillate between 15 and 45, making the algorithm unfinished (the algorithm ran until step 1000000).

7.1
Despite the application of the Backward-Forward method for non monotone ERG models for which the sufficient statistics are edges, 2-stars and triangles, we have that the condition (6.4.3) of Theorem 6.4.2 restricts the models that can be simulated with mean number of steps of order N 2 , as N grows. The reader can observe in Figure 7.3 that the number of models that satisfies condition (6.4.3) decreases when the size of the graph grows. However, it is important to emphasize that condition (6.4.3) is a sufficient condition for the Backward-Forward algorithm to stop. In Table 7.1 only the first three models satisfy this condition and the algorithm still works for the other models. In the case the condition is satisfied the mean number of steps of the Backward-Forward algorithm is smaller than the mean number of steps of the CFTP algorithm using a sample of size 10000. Table 7.1: Comparison between the CFTP and BF algorithms for the model edges-2-stars-triangles with N = 10 and parameters (θ 1 , θ 2 , θ 3 ) = (−1.8, 0.02, θ 3 ) (BF) (CFTP) mean number of

edges 2-stars triangles
In this chapter we present the final considerations about the results obtained in this thesis as well as the future potential research problems related with the problem of estimating the number of communities in the SBM and simulating graphs from the ERG model.

Stochastic Block Model
In the first part of this thesis we introduced 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. The family of penalty functions of the form (3.1.2) improves the penalty function used in the penalized likelihood estimator (2.3.1) proposed by Wang et al. (2017) in the sense that the penalty function used in this thesis is of smaller order compared with the penalty used in the previous work.
The penalty function used in the corrected Bayesian information criterion proposed by Hu et al. (2016) also improves that used in the penalized likelihood estimator of Wang et al. (2017). In the case that k is of smaller order than log n the penalty function of the KT order estimator improves that used in the corrected Bayesian information criterion; however, in the case that k is close to n the penalty function used in the KT estimator is of order n 3 log n while the penalty used in the corrected Bayesian information estimator is of order n 2 log n. Having said that, a possible future research concerning the KT estimator might be an improvement in the penalty function (3.1.2). However, it is important to emphasize that even though the penalty function is not of smaller order compared with the corrected Bayesian information criterion, the KT estimator is the only strongly consistent estimator known at the moment.
Another future line of questioning can be the problem of constructing a strong consistent penalized estimator for the number of communities of the SBM based on the profile maximum likelihood instead of the KT estimator.

8.1
In this thesis we considered a SBM for which the matrix P does not depend on n, that is, the model has the same expected degree for all nodes in the graph. An interesting extension of the estimator proposed in this thesis is to consider that P n = ρ n P , where P is a matrix with constant non-negative entries and ρ n is the degree density. The expected degree of any node of the graph is given by nρ n k 0 a,b=1 P a,b π a π b . Wang et al. (2017) and Hu et al. (2016) also proved the weak consistency for the communities' estimator in the regime where the network average degree grows at a polylog rate, that means, ρ n goes to zero at a rate nρ n log n .
Another future direction concerning the estimation of the number of communities is to consider the degree corrected stochastic block model (DCSBM) introduced in Karrer e Newman (2011). In this model, the constraint of having the same expected degree for all nodes within a community is removed by defining P(X(i, j) = 1|Z i = 1, Z j = b) = θ i θ j P a,b .

Exponential Random Graphs
In the second part of this thesis we proposed a perfect simulation algorithm for the Exponential Random Graph Model, based on the Coupling From The Past method of Propp e Wilson (1996) and on the Backward and Forward algorithm as used in Galves et al. (2010) and Galves et al. (2013).
The justification for the use of the CFTP algorithm is generally restricted to the monotonicity property of the dynamics, given by Proposition 5.2.1, and to prove that T stop N is almost-surely finite, but with no clue about the expected time to convergence. Here, in contrast, we prove a much stronger result: not only do we upper-bound the expectation of the waiting time, but we show that CFTP compares favorably with standard MCMC forward simulation: the waiting time is (up to a logarithmic factor) not larger than the time one has to wait before a run of the chain approaches the stationary distribution. Moreover, CFTP has the advantage of providing a draw from the exact stationary distribution, in contrast to MCMC which may keep for a long time a strong dependence on the initial state of the chain, as shown in the simulation example of Figure 7.1. We thus argue that for these models the CFTP algorithm is a better tool than forward MCMC simulation in order to get a sample from the Exponential Random Graph Model.
In order to overcome the monotonicity constraint of the model one can apply the Backward and Forward algorithm; however, as the reader can observe in the simulations presented in Chapter 7, the efficiency of the algorithm seems to decay when the number of vertices of the graph grows. This relation can be explained by the structure of the model: when one vertice is added in the graph, all the other vertices can be linked with it. This happens because the model takes into account the triangles and stars structures of the graph.
For the efficiency of the algorithm it is necessary to have high mixture probability λ k (θ) in the Kalikow-type decomposition (6.2.5) for small values of k. However, because of the dependence between the edges described above, the mixture probabilities λ k (θ) do not decrease when the size of the set of possible edges E k ij increases, that means, when k increases. In this way, when N grows to infinity, the algorithm works only for models with λ 0 (θ) tending to 1, that means, only for the Erdős-Rényi model (recall that the mixture component related with the mixture distribution λ 0 (θ) does not take into account the other edges of the graph to decide if an edge is added in the graph). Having said that, one possible way to construct a Kalikow-type decomposition in such a way that the mixture probabilities decrease when the size of the set of possible edges grows is to consider a model for which the vertices are located in a metric space and the existence of an edge between a pair of vertices depends on the geometric distance between these vertices.
The graph for which the vertices are located in a space equipped with a metric is called spatial network. A simplest example of spatial network is the geometric graph where the vertices are randomly located in the plane and there exists an edge between a pair of vertices if the distance between the vertices is smaller than r. So an interesting extension of the simulation algorithm proposed for the ERG models is to consider a spatial network model where the probability of observing a graph is based on the graph's statistics as considered in the ERG model; however, in this case, we want to penalize connections between nodes that are very distant.
From the theoretical point of view, the study of such a model seems promising since Bhamidi et al. (2011) have proved that for ERG models under the high temperature regime any finite collection of edges in the graph is asymptotically independent when the number of vertices grows to infinity. As a complement of this work, Chatterjee et al. (2013) shows that for n large the ERG model is essentially the same as the Erdős-Rényi model. In a nutshell, this result shows that the ERG model may not be a good choice to model real networks with large number of vertices when we expect to have strong dependencies in the network.