checkmark

# Consistent model selection for the Degree Corrected Stochastic Blockmodel

Andressa Cerqueira  Sandro Gallo  Florencia Leonardi and Cristel Vera

###### Abstract

The Degree Corrected Stochastic Block Model (DCSBM) was introduced by Karrer
and Newman (2011) as a generalization of the stochastic block model in which
vertices of the same community are allowed to have distinct degree
distributions. On the modelling side, this variability makes the DCSBM more
suitable for real life complex networks. On the statistical side, it is more
challenging due to the large number of parameters when dealing with community
detection. In this paper we prove that the penalized marginal likelihood
estimator is strongly consistent for the estimation of the number of
communities. We consider _dense_ or _semi-sparse_ random networks, and our
estimator is _unbounded_ , in the sense that the number of communities $k$
considered can be as big as $n$, the number of nodes in the network.

##  1 Introduction

Many real-world phenomena can be described by the interaction of objects
through a network. For example, interactions between individuals in a social
network, connections between airports in a country, connections between
regions of the brain, etc. Most of these networks have a community structure;
that is, the objects (nodes of the network) belonging to the same group tend
to behave similarly. In this way, probabilistic models that aim to describe
real networks need to incorporate these community structures.

The Stochastic Block Model (SBM) proposed by Holland et al. (1983) is a random
network model allowing community structures. Each pair of vertices is
connected, independently of everything, by a Poisson number of edges whose
rate depends solely on the communities of the involved vertices. The SBM,
therefore, models networks where nodes in the same community have the same
mean. This property can restrict applications to real-life networks that, not
rarely, display heterogeneity (_hubs_) in the degree distributions of vertices
belonging to the same community. Taking this into account, Karrer and Newman
(2011) proposed the Degree-Corrected Stochastic Block Model (DCSBM), which
considers the heterogeneity in the nodes’ degrees within communities. In the
degree-corrected model, each node has associated a non-negative real
parameter, a weight, specifying its “ability” to connect to other nodes in the
network. The sum of the weights in each community corresponds to the number of
nodes belonging to the community, generalizing the homogeneous SBM where we
can consider each node as having a weight equal to one. In both, the SBM and
the DCSBM, it is a standard approach to study two different regimes, the
_dense_ and the _semi-sparse_ regimes. In the former, the rates of the Poisson
distribution governing the number of edges between each pair of nodes are
fixed (do not depend on the number $n$ of nodes in the networks), leading to
linearly growing expected degrees for each node. In the latter, these rates
are allowed to decrease to zero in such a way that the expected degrees of the
nodes grow much slower than $n$.

Several works in the literature have addressed the community detection problem
for SBM and DCSBM, where the goal is to estimate the $k_{0}$ latent groups of
nodes in the network. For the SBM, community detection is proposed based on
spectral methods (Rohe et al., 2011; Lei and Rinaldo, 2015; Sarkar and Bickel,
2015), modularity (Newman and Girvan, 2004), likelihood methods (Bickel and
Chen, 2009; Celisse et al., 2012; Amini et al., 2013) and under a Bayesian
perspective (Decelle et al., 2011; Latouche et al., 2012; van der Pas et al.,
2017). For the DCSBM, Zhao et al. (2012) study consistency of modularity-based
and likelihood-based methods, Qin and Rohe (2013) proposed a regularized
spectral clustering algorithm and Jin (2015) proposed an approach based on the
entry-wise ratios between eigenvectors of the adjacency matrix. In order to
select the best model between the SBM and DCSBM to fit the data, Yan et al.
(2014) proposed an approach based on the likelihood ratio test computed
approximately using belief propagation. All these methods assume the number of
communities $k_{0}$ is known, something that barely occurs in practice.
Estimating the number of communities can be considered a model selection
problem.

The literature on estimating the number of $k_{0}$ communities is more recent
and not that extensive, at least from the theoretical point of view. In the
case of standard SBM, some approaches include sequential hypothesis tests (Lei
et al., 2016), cross-validation (Chen and Lei, 2018), spectral methods (Le and
Levina, 2022), penalized likelihood criteria (Wang and Bickel, 2017; Hu et
al., 2020) and penalized marginal likelihood estimators (Daudin et al., 2008;
Biernacki et al., 2010; Latouche et al., 2012; Cerqueira and Leonardi, 2020).
Specifically for the DCSBM with $n$ nodes and unknown weights and under the
semi-sparse regime with $n^{1/2}\rho_{n}/\log n\to\infty$, Wang and Bickel
(2017) proved the consistency of the penalized likelihood estimator with a
penalty function of order $k^{2}n\log n$ where $k$ is the number of
communities of the candidate model. More recently, Ma et al. (2021) proposed a
likelihood ratio test to estimate the number of communities and proved its
consistency for the semi-sparse regime where $n\rho_{n}/\log n$ is
sufficiently large. Their approach is based on spectral algorithms and so they
assume many further hypotheses to correctly detect the groups. Both approaches
assume the number of communities is bounded from above by a known constant.

The present paper considers the penalized marginal likelihood estimator for
the number of communities under a DCSBM with unknown weights, proposed by
Cerqueira and Leonardi (2020) for the standard SBM. This estimator can be seen
as a _minimum-description length_ principle, and it is also known as
_Krichevsky-Trofimov_ estimator in the information theory community. We prove
that this estimator equals the correct number of communities $k_{0}$
asymptotically almost-surely (for a sufficiently large number of vertices $n$
with probability one) under the more general degree-corrected model and
without assuming an upper bound for $k_{0}$. That is, the optimization is made
over all possible numbers of communities between 1 and $n$. As pointed out
above, the degree-corrected model has $n$ extra parameters, due to weights
associated to each node. For this reason, we need an additional term in the
penalty function of order $kn\log n$ with respect to the penalty function for
the standard SBM used in Cerqueira and Leonardi (2020). We consider the same
semi-sparse regime of Ma et al. (2021), where $n\rho_{n}/\log n$ is
sufficiently large, this rate being the phase transition for exact recovery of
the communities (see Abbe (2018)).

The paper is organized as follows. We define the DCSBM and its associated
likelihood function (for known parameters) in Section 2. In Section 3, we
introduce _a priori_ distributions for the parameters, define the penalized
marginal likelihood estimator, and state our main theorem, the consistency
results, as well as a key proposition relating the marginal likelihood and the
maximum likelihood. Finally, in Section 4 we present the proof of the main
result. Technical proofs and other auxiliary results are deferred to the
appendix.

##  2 The Degree Corrected Stochastic Block Model: definition and likelihood

For any $n\in\mathbb{N}$, let $X=(X_{ij})_{i,j\in[n]}$
($[n]:=\\{1,\ldots,n\\}$) denote the symmetric adjacency matrix of a random
network on $n$ vertices, with $X_{ij}\in\mathbb{N}$. For each pair
$i,j\in[n]$, with $i\neq j$ the variable $X_{ij}$ represents the number of
non-oriented edges (or alternatively, the strength of connection) between
vertices $i$ and $j$. For convenience, we define $X_{ii}$ as two times the
number of self-loops at vertex $i$.

The vertices are randomly divided into $k_{0}\geq 1$ communities and this
community attribution is represented by the vector $Z=(Z_{1},\ldots,Z_{n})$ of
$[k_{0}]$-valued random variables (i.i.d. with marginal distribution $\pi$).
We will often use the notation $i\in[a]$ ($i\in[n],a\in[k_{0}]$) to mean that
$Z_{i}=a$.

In the homogeneous SBM, the expected number of edges between vertices $i$ and
$j$ does not depend on the specific vertices but only on the communities.
Assuming the number of edges between communities $a,b$ has a Poisson
distribution with parameter $\lambda_{ab}$ we have that

$\mathbb{E}(X_{ij}|Z_{i}=z_{i},Z_{j}=z_{j})=\lambda_{z_{i}z_{j}}$

for any $i\neq j$.

The fact that, within each community, the vertices behave identically, is a
disadvantage of the SBM when modeling real-world complex networks. In order to
allow different vertices to behave differently inside each community, the
degree-corrected SBM (DCSBM) incorporates a weight $w_{i}$ for each vertex
$i\in[n]$ which influences the capacity of the vertex to connect to other
vertices. In this case, the expected number of edges between vertices $i\neq
j$ is given by

$\mathbb{E}(X_{ij}|Z_{i}=z_{i},Z_{j}=z_{j})=w_{i}w_{j}\lambda_{z_{i}z_{j}}$

and may be different for different nodes in the same community. For this
reason such networks are sometimes called _inhomogeneous_.

We assume the matrix $\lambda=(\lambda_{ab})_{a,b\in[k_{0}]}$ is symmetric and
has all entries greater than zero. In the _dense_ regime, the matrix $\lambda$
is fixed (does not depend on $n$) and has all its entries bounded from below
by a positive constant. In this case each node has an expected degree that
grows linearly on $n$, which makes the network over-connected. For this
reason, it is interesting to consider a _semi-sparse_ regime, where $\lambda$
is allowed to decrease to zero as a function of $n$. We take this approach
here and we assume that for each $n$, the distribution of the network on $n$
nodes has parameter $\lambda=\rho_{n}\tilde{\lambda}$, with $\rho_{n}\to 0$ as
$n\to\infty$ and $\tilde{\lambda}$ a constant symmetric matrix with entries
bounded from below by a positive constant. We will give conditions on
$\rho_{n}$ on our main results. For identifiability of the order $k_{0}$, i.e
the number of communities of the model, we assume that no column in
$\tilde{\lambda}$ is proportional to any other column. This is usually assumed
in the literature, see for example Ma et al. (2021).

Consider now the DCSBM with $k\in[n]$ communities. In order to compute the
joint distribution of $(Z,X)$ we need to define the following counters. For
any $z\in[k]^{n}$ and $a\in[k]$, let $n_{a}(z)$ be the number of vertices in
the network that belong to community $a$, that is

$n_{a}(z)=\sum_{i=1}^{n}\mathds{1}\\{z_{i}=a\\}\,.$

Following Karrer and Newman (2011) we assume that the vector of weights inside
each community satisfies

$\sum_{i\colon z_{i}=a}w_{i}\;=\;n_{a}(z)$

for all $a\in[k]$. This implies in particular that the total weight in the
network is $n$, the number of vertices, and putting $w_{i}\equiv 1$ we
retrieve the classical SBM.

For any symmetric matrix $x\in\mathbb{N}^{n\times n}$ (that is, any
realization of the network) define also the counter $o_{ab}(x,z)$ as the
number of edges between nodes of communities $a$ and $b$, that is

$o_{ab}(x,z)=\begin{cases}\sum_{1\leq i,j\leq
n}x_{ij}\mathds{1}\\{z_{i}=a,z_{j}=b\\}&\text{ for }a\neq b\,;\\\
\frac{1}{2}\sum_{1\leq i,j\leq n}x_{ij}\mathds{1}\\{z_{i}=a,z_{j}=a\\}&\text{
for }a=b\end{cases}$ (2.1)

and the degree of node $i$ by

$d_{i}(x)=\sum_{1\leq j\leq n}x_{ij}.$ (2.2)

The total degree on community $a$ is denoted by $d_{a}^{t}(x,z)$, and is given
by

$d_{a}^{t}(x,z)=\sum_{i\colon z_{i}=a}d_{i}(x)=\sum_{1\leq i\leq
n}d_{i}(x)\mathds{1}\\{z_{i}=a\\}=\sum_{1\leq i,j\leq
n}x_{ij}\mathds{1}\\{z_{i}=a\\}\,.$

Observe that we have

$d_{a}^{t}(x,z)=\sum_{b\neq a}o_{ab}(x,z)+2o_{aa}(x,z)\,$

and that the number of pairs of nodes in communities $a$ and $b$, denoted by
$n_{ab}(z)$, is given by

$n_{ab}(z)=\begin{cases}n_{a}(z)n_{b}(z)&\text{ for }a\neq b\,;\\\
\frac{1}{2}n_{a}(z)^{2}&\text{ for }a=b.\end{cases}$ (2.3)

We can now write down the joint distribution of $(Z,X)$ for the model with $k$
communities when we are given all the other parameters

$p(z,x|\pi,\lambda,w)=p(z|\pi)p(x|z,w,\lambda)$ (2.4)

where

$\displaystyle p(z|\pi)=\prod_{1\leq a\leq k}\pi_{a}^{n_{a}(z)}$ (2.5)

and

$\displaystyle p(x|z,w,\lambda)=\dfrac{1}{c(x)}\Biggl{[}\prod_{1\leq i\leq
n}{w_{i}}^{d_{i}(x)}\Biggr{]}\Biggl{[}\prod_{1\leq a\leq b\leq
k}\lambda_{ab}^{o_{ab}(x,z)}\exp\\{-n_{ab}(z)\lambda_{ab}\\}\Biggr{]}$ (2.6)

where

$c(x):=\Biggl{[}\prod_{i<j}x_{ij}!\Biggl{]}\Biggl{[}\prod_{i}2^{x_{ii}/2}(x_{ii}/2)!\Biggl{]}\,.$
(2.7)

##  3 Model selection: Main result

To define the estimator, we introduce convenient _a priori_ distributions for
the parameters $(\pi,\lambda,w)$. Then the hierarchical model distribution of
the DCSBM is given by

$\displaystyle\pi$
$\displaystyle\;\,\sim\,\;\text{Dirichlet}(\overbrace{{1}/{2},\dots,{1}/{2}}^{k})$
$\displaystyle\lambda_{ab}$
$\displaystyle\;\sim\;\text{Gamma}(1/2,1)\,,\quad\text{ for }a,b\in[k],\,a\leq
b$ $\displaystyle z_{i}\,|\,\pi$ $\displaystyle\;\sim\;\pi\,,\quad i\in[n]$
$\displaystyle(w_{i})_{i\in[a]}\,|\,z$
$\displaystyle\;\sim\;n_{a}(z)\;\text{Dirichlet}(\overbrace{1/2,\dots,1/2}^{n_{a}(z)})\,,\quad
a\in[k]$ $\displaystyle x_{ij}\,|\,z_{i},z_{j},w_{i},w_{j},\lambda$
$\displaystyle\;\sim\;(2-\mathds{1}\\{i\neq
j\\})\;\text{Poisson}(w_{i}w_{j}\lambda_{z_{i},z_{j}})\,,\quad\text{ for
}i,j\in[n],\,i\leq j\,.$

Let $(\lambda_{ab})_{a,b\in[k]}$ be the symmetric matrix constructed from
$(\lambda_{ab})_{1\leq a\leq b\leq k}$. Denote by $\Theta_{k}$ the space where
the hyperparameters $(\pi,\lambda,w)$ take values and by $\nu_{k}(\theta)$ the
a priori distribution over $\Theta_{k}$.

For any $x\in\mathbb{N}^{n\times n}$, the marginal likelihood $p_{k}(x)$ is
given by the integral

$\displaystyle p_{k}(x)$
$\displaystyle=\sum_{z\in[k]^{n}}\int_{\Theta_{k}}p(x,z|\theta)\nu_{k}(\theta)d\theta$

where $\nu_{k}$ is explicitly decomposed as in (5.7) (in the appendix). We can
now define the estimator for the number of communities as

$\widehat{k}_{n}(x):=\underset{1\leq k\leq n}{\arg\max}\left\\{\;\log
p_{k}(x)-(k^{3}+3kn)\log(n+1)\;\right\\}\,.$ (3.1)

######  Remark 3.1.

Observe that the estimator $\hat{k}_{n}$ in (3.1) has an extra penalty term of
order $n\log n$ with respect to the estimator defined in Cerqueira and
Leonardi (2020). This extra term is needed by the addition of $n$ parameters
$w_{i}$, $i=1,\dots,n$ to the model, and is unnecessary in the homogeneous
SBM.

We now state our main theorem.

######  Theorem 3.1.

For the DCSBM with $k_{0}$ communities and $\rho_{n}\geq C\frac{\log
n}{n},n\geq 1$, where $C$ is a sufficiently large constant, the estimator
defined in (3.1) satisfies

$\widehat{k}_{n}=k_{0}$ (3.2)

eventually almost surely as $n$ diverges.

The proof of Theorem 3.1 is based on a key proposition (see below) relating
the marginal likelihood $p_{k}(x)$ with the maximum likelihood
$\sup_{\theta\in\Theta_{k}}p(x|\theta)=\sup_{\pi}\;p(z|\pi)\sup_{\lambda,w}\;p(x|z,w,\lambda)$,
that we now define. For any $x\in\mathbb{N}^{n\times n},z\in[k]^{n},i\in[n]$
and $a,b\in[k]$, the maximum likelihood estimators of $\pi$, $\lambda$ and $w$
are given by

$\widehat{\pi}_{a}(z)=\frac{n_{a}(z)}{n}\,,\quad\widehat{\lambda}_{ab}(x,z)=\frac{o_{ab}(x,z)}{n_{ab}(z)}\,,\quad\widehat{w}_{i}(x,z)=\sum_{1\leq
a\leq k}\mathds{1}\\{z_{i}=a\\}\frac{n_{a}(z)d_{i}(x)}{d^{t}_{a}(x,z)}\,,$

and thus

$\begin{split}\sup_{\pi}\;p(z|\pi)&=\prod_{1\leq a\leq
k}\left(\frac{n_{a}(z)}{n}\right)^{n_{a}(z)}\end{split}$ (3.3)

and

$\begin{split}\sup_{\lambda,w}\;p(x|z,w,\lambda)&={1\over c(x)}\prod_{1\leq
a\leq b\leq
k}\left(\frac{o_{ab}(x,z)}{n_{ab}(z)}\right)^{o_{ab}(x,z)}e^{-o_{ab}(x,z)}\\\
&\qquad\times\prod_{a\in[k],i\in[n]:z_{i}=a}\left(\frac{n_{a}(z)d_{i}(x)}{d_{a}^{t}(x,z)}\right)^{d_{i}(x)}\,.\end{split}$
(3.4)

We now state the key proposition, which holds for a set of “good” networks
(which will be proved to hold with high probability) defined by

$\Omega_{n}:=\\{{x}\colon x_{ij}\leq\log n,\text{ for all }i,j\in[n]\\}\,.$
(3.5)

######  Proposition 3.1.

For all $k\geq 1$, all $n\geq\max(k,3)$ and all ${x}\in\Omega_{n}$ we have
that

$0\;\leq\;\log\left(\dfrac{\sup_{\theta\in\Theta_{k}}p(x|\theta)}{p_{k}(x)}\right)\;\leq\;k(k+2)\log(n+1)+3n\log
n\,.$

The proof of this proposition is given in the appendix.

##  4 Proof of the main result

The proof of Theorem 3.1 is split into two parts, first, we prove the non-
underestimation of the number of communities and then the non-overestimation.
Additional results and definitions are given in the appendix.

We begin by presenting the proof that the estimator $\widehat{k}_{n}$ does not
underestimate $k_{0}$, the true number of communities.

######  Proposition 4.1.

For the sparse DCSBM with $\rho_{n}\geq\frac{C\log n}{n}$, for a sufficiently
large constant $C>0$, the estimator $\widehat{k}_{n}$ defined in (3.1)
satisfies

$\widehat{k}_{n}\geq k_{0},$

eventually almost surely as $n\to\infty$.

###### Proof.

We define the profile estimator for the communities based on the observed
graph under the model with $k$ communities as

$\widehat{z}_{k}=\underset{z\in{\\{1,2,\ldots,k\\}}^{n}}{\arg\max}\sup_{\theta\in\Theta_{k}}p(x,z|\theta)\,.$
(4.1)

By Lemma 5.6 we can (and henceforth will) take $n$ sufficiently large so that
$x\in\Omega_{n}$, the set of “good” networks defined in (3.5). In order to
show that $\widehat{k}_{n}{(x)}\geq k_{0}$, almost surely when $n\to\infty$,
it is sufficient to show that for all $k<k_{0}$,

$\log p_{k_{0}}(x)-(k_{0}^{3}+3k_{0}n)\log(n+1)\;>\;\log
p_{k}(x)-(k^{3}+3kn)\log(n+1)\,,$ (4.2)

almost surely, when $n\to\infty$. But, if we show that

$\liminf_{n\to\infty}\;{1\over\rho_{n}n^{2}}\log{p_{k_{0}}(x)\over
p_{k}(x)}>0\,,$ (4.3)

and due to the fact that

${1\over\rho_{n}n^{2}}\left(k_{0}^{3}+3k_{0}n-k^{3}-3kn\right)\log(n+1)$

can be made sufficiently small by assumption on $\rho_{n}$, it follows that
(4.3) implies (4.2). Observe that for all $x\in\Omega_{n}$, by Proposition 3.1
and the fact that $p_{k}(x)\leq\sup_{\theta\in\Theta_{k}}p(x|\theta)$, we have
that

$\displaystyle{1\over\rho_{n}n^{2}}\log{p_{k_{0}}(x)\over p_{k}(x)}$
$\displaystyle={1\over\rho_{n}n^{2}}\log{p_{k_{0}}(x)\over\sup_{\theta\in\Theta_{k_{0}}}p(x|\theta)}+{1\over\rho_{n}n^{2}}\log{\sup_{\theta\in\Theta_{k_{0}}}p(x|\theta)\over\sup_{\theta\in\Theta_{k}}p(x|\theta)}+{1\over\rho_{n}n^{2}}\log{\sup_{\theta\in\Theta_{k}}p(x|\theta)\over
p_{k}(x)}$ $\displaystyle\geq-\gamma(k_{0}){\log
n\over\rho_{n}n}+{1\over\rho_{n}n^{2}}\log{\sup_{\theta\in\Theta_{k_{0}}}p(x|\theta)\over\sup_{\theta\in\Theta_{k}}p(x|\theta)}\,,$

for some constant $\gamma(k_{0})$. Then, to show (4.3) it is enough to prove
that for $k<k_{0}$

$\liminf_{n\to\infty}\;{1\over\rho_{n}n^{2}}\log{\sup_{\theta\in\Theta_{k_{0}}}p(x|\theta)\over\sup_{\theta\in\Theta_{k}}p(x|\theta)}>0$
(4.4)

as $-\gamma(k_{0}){\log n\over\rho_{n}n}$ is also sufficiently small by
hypothesis on $\rho_{n}$. First observe that for all $z\in[k_{0}]^{n}$ we have
that

$\begin{split}\log\sup_{\theta\in\Theta_{k_{0}}}p(x|\theta)\;\geq\;\log\sup_{\theta\in\Theta_{k_{0}}}p(x,z|\theta)\,.\end{split}$
(4.5)

Let

$\tilde{o}_{ab}(x,z):=\sum_{1\leq i,j\leq
n}x_{ij}\mathds{1}\\{z_{i}=a,z_{j}=b\\}$

for all pairs $a,b$ and notice is relates to $o_{ab}$ by
$\tilde{o}_{ab}(x,z)=o_{ab}(x,z)$ for all $a\neq b$ and
$\tilde{o}_{aa}(x,z)=2o_{aa}(x,z)$ for all $a$. From (2.4)-(2.7) and the
definition of the maximum likelihood estimators we have that

$\begin{split}\log\sup_{\theta\in\Theta_{k_{0}}}p(x,z|\theta)&\;=\;L(x)+n\sum_{a=1}^{k_{0}}\widehat{\pi}_{a}(z)\log\widehat{\pi}_{a}(z)+\frac{1}{2}\sum_{1\leq
a,b\leq k_{0}}\tilde{o}_{ab}(x,z)\log\widehat{\lambda}_{ab}(x,z)\\\
&\qquad+\sum_{1\leq a\leq
k_{0}}d^{t}_{a}(x,z)\log\frac{n_{a}(z)}{d^{t}_{a}(x,z)}\end{split}$ (4.6)

with

$\displaystyle L(x)$ $\displaystyle\;=\;-\log
c(x)-\sum_{i,j}x_{ij}+\sum_{i}d_{i}(x)\log d_{i}(x)\,;$
$\displaystyle\widehat{\pi}_{a}(z)$ $\displaystyle\;=\;{n_{a}(z)\over
n},\qquad\qquad 1\leq a\leq k_{0};$ $\displaystyle\widehat{\lambda}_{ab}(x,z)$
$\displaystyle\;=\;{\tilde{o}_{ab}(x,z)\over n_{a}(z)n_{b}(z)},\qquad 1\leq
a,b\leq k_{0};$ $\displaystyle d_{a}^{t}(x,z)$ $\displaystyle\;=\;\sum_{1\leq
i,j\leq n}x_{ij}\mathds{1}\\{z_{i}=a\\}\;=\;\sum_{b}\tilde{o}_{ab}(x,z),\qquad
1\leq a\leq k_{0}\,.$

For the denominator in (4.4) we use that

$\begin{split}\log\sup_{\theta\in\Theta_{k}}p(x|\theta)\;&\leq\;\log
k^{n}\sup_{\theta\in\Theta_{k}}p(x,\widehat{z}_{k}|\theta)\\\ &\leq\;n\log
k+\log\sup_{\theta\in\Theta_{k}}p(x,\widehat{z}_{k}|\theta)\,,\end{split}$
(4.7)

with $\widehat{z}_{k}$ defined by (4.1). Analogously as in (4.6) we have that

$\begin{split}\log\sup_{\theta\in\Theta_{k}}p(x,\widehat{z}_{k}|\theta)&\;=\;L(x)+n\sum_{1\leq
a\leq
k}\widehat{\pi}_{a}(\widehat{z}_{k})\log\widehat{\pi}_{a}(\widehat{z}_{k})+\frac{1}{2}\sum_{1\leq
a,b\leq
k}\tilde{o}_{ab}(\widehat{z}_{k})\log\widehat{\lambda}_{ab}(x,\widehat{z}_{k})\\\
&\qquad+\sum_{1\leq a\leq
k}d^{t}_{a}(x,\widehat{z}_{k})\log\frac{n_{a}(\widehat{z}_{k})}{d^{t}_{a}(x,\widehat{z}_{k})}\,.\end{split}$
(4.8)

Then, the logarithm in (4.4) can be lower bounded by the difference of (4.5)
and (4.7), and using the expressions in (4.6) and (4.8) we obtain that

$\begin{split}\log{\sup_{\theta\in\Theta_{k_{0}}}p(x|\theta)\over\sup_{\theta\in\Theta_{k}}p(x|\theta)}\;&\geq\;n\sum_{1\leq
a\leq
k_{0}}\widehat{\pi}_{a}(z)\log\widehat{\pi}_{a}(z)+\frac{1}{2}\sum_{1\leq
a,b\leq
k_{0}}\tilde{o}_{ab}(x,z)\log\widehat{\lambda}_{ab}(x,z)\\\\[5.69054pt]
&\qquad+\sum_{1\leq a\leq
k_{0}}d_{a}^{t}(x,z)\log\frac{n_{a}(z)}{d_{a}^{t}(x,z)}-n\log k\\\\[5.69054pt]
&\qquad-n\sum_{1\leq a\leq
k}\widehat{\pi}_{a}(\widehat{z}_{k})\log\widehat{\pi}_{a}(\widehat{z}_{k})-\frac{1}{2}\sum_{1\leq
a,b\leq
k}\tilde{o}_{ab}(x,\widehat{z}_{k})\log\widehat{\lambda}_{ab}(x,\widehat{z}_{k})\\\\[5.69054pt]
&\qquad-\sum_{1\leq a\leq
k}d^{t}_{a}(x,\widehat{z}_{k})\log\frac{n_{a}(\widehat{z}_{k})}{d^{t}_{a}(x,\widehat{z}_{k})}\,.\end{split}$
(4.9)

We will now rearrange the six terms of the right-hand side. First, let

$\mathcal{A}(n):=n\sum_{1\leq a\leq
k_{0}}\widehat{\pi}_{a}(z)\log\widehat{\pi}_{a}(z)-n\log k-n\sum_{1\leq a\leq
k}\widehat{\pi}_{a}(\widehat{z}_{k})\log\widehat{\pi}_{a}(\widehat{z}_{k}).$
(4.10)

Second, we can write

$\begin{split}\sum_{1\leq a\leq
k_{0}}d_{a}^{t}(x,z)\log\frac{n_{a}(z)}{d_{a}^{t}(x,z)}\;&=\;\frac{1}{2}\sum_{1\leq
a\leq
k_{0}}d_{a}^{t}(x,z)\log\frac{n_{a}(z)}{d_{a}^{t}(x,z)}+\frac{1}{2}\sum_{1\leq
b\leq k_{0}}d^{t}_{b}(x,z)\log\frac{n_{b}(z)}{d^{t}_{b}(x,z)}\\\
&=\;\frac{1}{2}\sum_{1\leq a,b\leq
k_{0}}\tilde{o}_{ab}(x,z)\log\frac{n_{a}(z)n_{b}(z)}{d_{a}^{t}(x,z)d^{t}_{b}(x,z)}\end{split}$
(4.11)

and therefore

$\begin{split}\frac{1}{2}\sum_{1\leq a,b\leq
k_{0}}\tilde{o}_{ab}(x,z)\log\widehat{\lambda}_{ab}(x,z)&+\sum_{1\leq a\leq
k_{0}}d_{a}^{t}(x,z)\log\frac{n_{a}(z)}{d_{a}^{t}(x,z)}=\frac{1}{2}\sum_{1\leq
a,b\leq
k_{0}}\tilde{o}_{ab}(x,z)\log\frac{\tilde{o}_{ab}(x,z)}{d_{a}^{t}(x,z)d^{t}_{b}(x,z)}.\end{split}$
(4.12)

Using (4.10), (4.12) and the counterpart of (4.12) under the $k$-th order
model with $\widehat{z}_{k}$ instead of $z$, the right-hand side of (4.9) now
reads

$\displaystyle\log{\sup_{\theta\in\Theta_{k_{0}}}p(x|\theta)\over\sup_{\theta\in\Theta_{k}}p(x|\theta)}\;\geq\;\mathcal{A}(n)+\frac{1}{2}$
$\displaystyle\sum_{1\leq a,b\leq
k_{0}}\tilde{o}_{ab}(x,z)\log\frac{\tilde{o}_{ab}(x,z)}{d_{a}^{t}(x,z)d^{t}_{b}(x,z)}$
$\displaystyle-\frac{1}{2}\sum_{1\leq a,b\leq
k}\tilde{o}_{ab}(x,\widehat{z}_{k})\log\frac{\tilde{o}_{ab}(x,\widehat{z}_{k})}{d_{a}^{t}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}\,.$

Now, dividing both sides of (4.9) by $\rho_{n}n^{2}$, and summing on the
right-hand side the following term (which equals 0)

$\frac{1}{\rho_{n}n^{2}}\left(\frac{1}{2}\sum_{1\leq a,b\leq
k_{0}}\tilde{o}_{ab}(x,z)\log\rho_{n}n^{2}-\frac{1}{2}\sum_{1\leq a,b\leq
k}\tilde{o}_{ab}(x,\widehat{z}_{k})\log\rho_{n}n^{2}\right)$

we finally obtain that

$\begin{split}\frac{1}{\rho_{n}n^{2}}\log{\sup_{\theta\in\Theta_{k_{0}}}p(x|\theta)\over\sup_{\theta\in\Theta_{k}}p(x|\theta)}\;&\geq\;\frac{1}{2}\,\Biggl{(}\sum_{1\leq
a,b\leq
k_{0}}\frac{\tilde{o}_{ab}(x,z)}{\rho_{n}n^{2}}\log\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,z)}{d_{a}^{t}(x,z)d^{t}_{b}(x,z)}\\\
&\qquad\quad-\sum_{1\leq a,b\leq
k}\frac{\tilde{o}_{ab}(x,\widehat{z}_{k})}{\rho_{n}n^{2}}\log\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,\widehat{z}_{k})}{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}\Biggr{)}+\frac{\mathcal{A}(n)}{\rho_{n}n^{2}}.\end{split}$
(4.13)

Since $\frac{\mathcal{A}(n)}{\rho_{n}n^{2}}$ converges almost surely to $0$,
proving that (4.13) is bounded from below by a positive constant, eventually
almost surely as $n\to\infty$, is equivalent to proving that

$\begin{split}\liminf_{n\to\infty}\;\sum_{1\leq a,b\leq
k_{0}}&\frac{d_{a}^{t}(x,z)d^{t}_{b}(x,z)}{\rho_{n}^{2}n^{4}}\varphi\Bigl{(}\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,z)}{d_{a}^{t}(x,z)d^{t}_{b}(x,z)}\Bigr{)}\\\
&-\sum_{1\leq a,b\leq
k}\frac{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}{\rho_{n}^{2}n^{4}}\varphi\Bigl{(}\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,\widehat{z}_{k})}{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}\Bigr{)}\;>\;0\,,\end{split}$
(4.14)

with $\varphi(u)=u\log u$. By Lemma 5.7 we have that

$\begin{split}\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,z)}{d_{a}^{t}(x,z)d^{t}_{b}(x,z)}\;=\;\frac{\tilde{o}_{ab}(x,z)/\rho_{n}n^{2}}{d_{a}^{t}(x,z)d^{t}_{b}(x,z)/\rho_{n}^{2}n^{4}}\;&\to\;\frac{[\text{diag}(\pi)\tilde{\lambda}\text{diag}(\pi)^{T}]_{ab}}{[\text{diag}(\pi)\tilde{\lambda}\text{diag}(\pi)^{T}{\bf
1}_{k}]_{a}[\text{diag}(\pi)\tilde{\lambda}\text{diag}(\pi)^{T}{\bf
1}_{k}]_{b}}\\\
&=\;\frac{\pi_{a}\pi_{b}\tilde{\lambda}_{ab}}{\pi_{a}[\tilde{\lambda}\pi]_{b}\pi_{b}[\tilde{\lambda}\pi]_{a}}\\\
&=\;\frac{\tilde{\lambda}_{ab}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{b}}\,\end{split}$
(4.15)

where we recall that $\tilde{\lambda}$ is the matrix such that
$\lambda=\rho_{n}\tilde{\lambda}$. Then we have that

$\begin{split}\lim_{n\to\infty}\;\frac{1}{2}\,\sum_{1\leq a,b\leq
k_{0}}&\frac{d_{a}^{t}(x,z)d^{t}_{b}(x,z)}{\rho_{n}^{2}n^{4}}\;\varphi\Bigl{(}\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,z)}{d_{a}^{t}(x,z)d^{t}_{b}(x,z)}\Bigr{)}\\\
&\;=\;\frac{1}{2}\sum_{1\leq a,b\leq
k_{0}}\pi_{a}\pi_{b}[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{b}\;\varphi\Bigl{(}\frac{\tilde{\lambda}_{ab}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{b}}\Bigr{)}\,.\end{split}$
(4.16)

On the other hand, by Lemma 5.8 we have that

$\begin{split}\limsup_{n\to\infty}\;\frac{1}{2}\sum_{1\leq a,b\leq
k}&\frac{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}{\rho_{n}^{2}n^{4}}\;\varphi\Bigl{(}\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,\widehat{z}_{k})}{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}\Bigr{)}\\\
&\leq\;\frac{1}{2}\sum_{1\leq a,b\leq
k}\pi^{*}_{a}\pi^{*}_{b}[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}\;\varphi\Bigl{(}\frac{\lambda^{*}_{ab}}{[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}}\Bigr{)}\end{split}$
(4.17)

for some $k\times k$ positive matrix $\lambda^{*}$ and $k$ dimensional vector
$\pi^{*}$ defined by (5.35). Finally, by Lemma 5.9 we have that the difference
of (4.16) and (4.17) is lower bounded by

$\frac{1}{2}\Biggl{(}\sum_{1\leq a,b\leq
k_{0}}\pi_{a}\pi_{b}[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{b}\;\varphi\Bigl{(}\frac{\tilde{\lambda}_{ab}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{b}}\Bigr{)}-\sum_{1\leq
a,b\leq
k}\pi^{*}_{a}\pi^{*}_{b}[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}\;\varphi\Bigl{(}\frac{\lambda^{*}_{ab}}{[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}}\Bigr{)}\Biggr{)}\;>\;0$

unless $\tilde{\lambda}$ has two proportional columns, which contradicts the
hypothesis of identifiability of $k_{0}$. This concludes the proof of
Proposition 4.1. ∎

We conclude the proof of Theorem 3.1 by proving that $\widehat{k}_{n}(x)$ does
not overestimates $k_{0}$, the true number of communities.

######  Proposition 4.2.

For the DCSBM, the estimator $\widehat{k}_{n}$ defined in (3.1) satisfies

$\widehat{k}_{n}\;\leq\;k_{0}$

eventually almost surely as $n\to\infty$.

Observe that there is no assumption on $\rho_{n}$ for this proposition.

###### Proof.

By the Borel-Cantelli Lemma, it is enough to prove that the following series
converges

$\begin{split}\sum_{n=1}^{\infty}\sum_{k=k_{0}+1}^{n}p(\widehat{k}_{n}=k)\;=&\;\sum_{n=1}^{\infty}\sum_{k=k_{0}+1}^{n}\sum_{{x}\in\Omega_{n}^{c}}p(x)\mathds{1}\\{\widehat{k}_{n}(x)=k\\}\\\
&+\;\sum_{n=1}^{\infty}\sum_{k=k_{0}+1}^{n}\sum_{x\in\Omega_{n}}p(x)\mathds{1}\\{\widehat{k}_{n}(x)=k\\}.\end{split}$
(4.18)

Let us start by the first term in the right-hand side, and observe that for
each $n$

$\sum_{k=k_{0}+1}^{n}\sum_{x\in\Omega_{n}^{c}}p(x)\mathds{1}\\{\widehat{k}_{n}(x)=k\\}\;=\;\sum_{x\in\Omega_{n}^{c}}p(x)\sum_{k=k_{0}}^{n}\mathds{1}\\{\widehat{k}_{n}(x)=k\\}\;\leq\;\sum_{x\in\Omega_{n}^{c}}p(x)\;=\;p(\Omega_{n}^{c}).$

Now using Lemma 5.6 we conclude that the first term of (4.18) is indeed
summable in $n$. So we now need to prove that the second term of (4.18) is
also summable in $n$. First observe that for some fixed $k=k_{0}+1,\dots,n$ we
have that

$\sum_{x\in\Omega_{n}}p(x)\mathds{1}\\{\widehat{k}_{n}(x)=k\\}\;=\;\sum_{x\in\Omega_{n}}p(x)\mathds{1}\\{\underset{\ell}{\arg\max}(\log
p_{\ell}(x)-(\ell^{3}+3\ell n)\log(n+1))=k\\}.$ (4.19)

By the definition of $\widehat{k}_{n}(x)$, we have, when $k>k_{0}$, that

$\begin{split}\Bigl{\\{}\underset{\ell}{\arg\max}[\log&\,\log
p_{\ell}(x)-(\ell^{3}+3\ell n)\log(n+1)]=k\Bigr{\\}}\\\
&\subset\;\Bigl{\\{}\log p_{k}(x)-(k^{3}+3kn)\log(n+1)\geq\log
p_{k_{0}}(x)-(k_{0}^{3}+3k_{0}n)\log(n+1)\Bigr{\\}}\,.\end{split}$

So

$\begin{split}\sum_{x\in\Omega_{n}}&p(x)\mathds{1}\\{\widehat{k}_{n}(x)=k\\}\\\
&\;\leq\;\sum_{x\in\Omega_{n}}p(x)\mathds{1}\bigl{\\{}\log
p_{k}(x)-(k^{3}+3kn)\log(n+1)\geq\log
p_{k_{0}}(x)-(k_{0}^{3}+3k_{0}n)\log(n+1)\bigr{\\}}\\\
&=\sum_{x\in\Omega_{n}}p(x)\mathds{1}\bigl{\\{}p_{k_{0}}(x)\leq
p_{k}(x)\exp[(-k^{3}-3kn+k_{0}^{3}+3k_{0}n)\log(n+1)]\bigr{\\}}.\end{split}$
(4.20)

Using Proposition 3.1, we have for ${x}\in\Omega_{n}$ that

$\displaystyle\log p(x)$
$\displaystyle\;\leq\;\log\sup_{\theta\in\Theta^{k_{0}}}p(x|\theta).$
$\displaystyle\;\leq\;\log p_{k_{0}}(x)+k_{0}(k_{0}+2)\log(n+1)+3n\log n,$
(4.21)

giving that

$\displaystyle p(x)$
$\displaystyle\;\leq\;p_{k_{0}}(x)e^{k_{0}(k_{0}+2)\log(n+1)+3n\log n}.$
(4.22)

Then, on the set $\bigl{\\{}p_{k_{0}}(x)\leq
p_{k}(x)\exp[(k_{0}^{3}+3k_{0}n-k^{3}-3kn)\log(n+1)]\bigr{\\}}$, we have that
each term in the sum in (4.20) can be upper bound by

$\begin{split}p(x)\mathds{1}\bigl{\\{}p_{k_{0}}(x)&\leq
p_{k}(x)e^{(k_{0}^{3}+3k_{0}n-k^{3}-3kn)\log(n+1)}\bigr{\\}}\\\\[5.69054pt]
&\leq\;p_{k}(x)e^{k_{0}(k_{0}+2)\log(n+1)+3n\log
n+(k_{0}^{3}+3k_{0}n-k^{3}-3kn)\log(n+1)}.\end{split}$ (4.23)

Observe that as $k\geq k_{0}+1$, the exponent in (4.23) can be upper bounded
by

$(-2k_{0}^{2}-k_{0}-1)\log(n+1)\;\leq\;-4\log n\,.$

Substituting now (4.23) in (4.20) and summing in $k=k_{0}+1,\dots,n$ gives
that

$\begin{split}\sum_{k=1}^{n}\sum_{x\in\Omega_{n}}p(x)\mathds{1}\bigl{\\{}\widehat{k}_{n}(x)=k\bigr{\\}}\;&\leq\;n\,n^{-4}\sum_{x\in\Omega_{n}}p_{k}(x)\\\
&\leq\;n^{-3}\end{split}$ (4.24)

that is summable in $n$. This concludes the proof of Proposition 4.2. ∎

## Acknowledgments

This work was produced as part of the activities of the _Research, Innovation
and Dissemination Center for Neuromathematics_ (grant FAPESP 2013/07699-0). It
was also supported by FAPESP project (grant 2017/10555-0) _“Stochastic
Modeling of Interacting Systems”_ and CNPq Universal project (grant
432310/2018-5) _“Statistics, stochastic processes and discrete structures”_.
FL is partially supported by a CNPq’s research fellowship, grant
311763/2020-0. During the realization of this work, CV was supported by a
CAPES Ph.D. fellowship.

## References

  * Abbe (2018) Emmanuel Abbe.  Community detection and stochastic block models: Recent developments.  _Journal of Machine Learning Research_ , 18(177):1–86, 2018.  URL http://jmlr.org/papers/v18/16-480.html.
  * Amini et al. (2013) Arash A. Amini, Aiyou Chen, Peter J. Bickel, and Elizaveta Levina.  Pseudo-likelihood methods for community detection in large sparse networks.  _The Annals of Statistics_ , 41(4):2097 – 2122, 2013.
  * Bickel and Chen (2009) Peter J Bickel and Aiyou Chen.  A nonparametric view of network models and newman–girvan and other modularities.  _Proceedings of the National Academy of Sciences_ , 106(50):21068–21073, 2009.
  * Biernacki et al. (2010) Christophe Biernacki, Gilles Celeux, and Gérard Govaert.  Exact and monte carlo calculations of integrated likelihoods for the latent class model.  _Journal of Statistical Planning and Inference_ , 140(11):2991–3002, 2010.
  * Boucheron et al. (2013) Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  _Concentration inequalities: A nonasymptotic theory of independence_.  Oxford university press, 2013.
  * Celisse et al. (2012) Alain Celisse, Jean-Jacques Daudin, and Laurent Pierre.  Consistency of maximum-likelihood and variational estimators in the stochastic block model.  _Electronic Journal of Statistics_ , 6(none):1847 – 1899, 2012.
  * Cerqueira and Leonardi (2020) Andressa Cerqueira and Florencia Leonardi.  Estimation of the number of communities in the stochastic block model.  _IEEE Transactions on Information Theory_ , 66(10):6403–6412, 2020.  doi: 10.1109/TIT.2020.3016331.
  * Chen and Lei (2018) Kehui Chen and Jing Lei.  Network cross-validation for determining the number of communities in network data.  _Journal of the American Statistical Association_ , 113(521):241–251, 2018.
  * Daudin et al. (2008) J-J Daudin, Franck Picard, and Stéphane Robin.  A mixture model for random graphs.  _Statistics and computing_ , 18(2):173–183, 2008\.
  * Davisson et al. (1981) L Davisson, R McEliece, M Pursley, and Mark Wallace.  Efficient universal noiseless source codes.  _IEEE Transactions on Information Theory_ , 27(3):269–279, 1981.
  * Decelle et al. (2011) Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová.  Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.  _Phys. Rev. E_ , 84:066106, Dec 2011.
  * Holland et al. (1983) Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  _Social networks_ , 5(2):109–137, 1983.
  * Hu et al. (2020) Jianwei Hu, Hong Qin, Ting Yan, and Yunpeng Zhao.  Corrected bayesian information criterion for stochastic block models.  _Journal of the American Statistical Association_ , 115(532):1771–1783, 2020.
  * Jin (2015) Jiashun Jin.  Fast community detection by score.  _The Annals of Statistics_ , 43(1):57–89, 2015\.
  * Karrer and Newman (2011) Brian Karrer and Mark EJ Newman.  Stochastic blockmodels and community structure in networks.  _Physical review E_ , 83(1):016107, 2011.
  * Latouche et al. (2012) Pierre Latouche, Etienne Birmele, and Christophe Ambroise.  Variational bayesian inference and complexity control for stochastic block models.  _Statistical Modelling_ , 12(1):93–115, 2012\.
  * Le and Levina (2022) Can M. Le and Elizaveta Levina.  Estimating the number of communities by spectral methods.  _Electronic Journal of Statistics_ , 16(1):3315 – 3342, 2022.
  * Lei and Rinaldo (2015) Jing Lei and Alessandro Rinaldo.  Consistency of spectral clustering in stochastic block models.  _The Annals of Statistics_ , 43(1):215–237, 2015\.
  * Lei et al. (2016) Jing Lei et al.  A goodness-of-fit test for stochastic block models.  _The Annals of Statistics_ , 44(1):401–424, 2016\.
  * Ma et al. (2021) Shujie Ma, Liangjun Su, and Yichong Zhang.  Determining the number of communities in degree-corrected stochastic block models.  _Journal of machine learning research_ , 22(69), 2021.
  * Newman and Girvan (2004) Mark E. J. Newman and Michelle Girvan.  Finding and evaluating community structure in networks.  _Physical review. E, Statistical, nonlinear, and soft matter physics_ , 69 2 Pt 2:026113, 2004.
  * Qin and Rohe (2013) Tai Qin and Karl Rohe.  Regularized spectral clustering under the degree-corrected stochastic blockmodel.  In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 26. Curran Associates, Inc., 2013.
  * Rohe et al. (2011) Karl Rohe, Sourav Chatterjee, and Bin Yu.  Spectral clustering and the high-dimensional stochastic blockmodel.  _The Annals of Statistics_ , 39(4):1878 – 1915, 2011.
  * Sarkar and Bickel (2015) Purnamrita Sarkar and Peter J. Bickel.  Role of normalization in spectral clustering for stochastic blockmodels.  _The Annals of Statistics_ , 43(3):962–990, 2015\.
  * van der Pas et al. (2017) SL van der Pas, AW van der Vaart, et al.  Bayesian community detection.  _Bayesian Analysis_ , 2017.
  * Wang and Bickel (2017) YX Rachel Wang and Peter J Bickel.  Likelihood-based model selection for stochastic block models.  _The Annals of Statistics_ , 45(2):500–528, 2017\.
  * Yan et al. (2014) Xiaoran Yan, Cosma Shalizi, Jacob E Jensen, Florent Krzakala, Cristopher Moore, Lenka Zdeborová, Pan Zhang, and Yaojia Zhu.  Model selection for degree-corrected block models.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2014(5):P05007, 2014.
  * Zhao et al. (2012) Yunpeng Zhao, Elizaveta Levina, and Ji Zhu.  Consistency of community detection in networks under degree-corrected stochastic block models.  _The Annals of Statistics_ , 40(4):2266–2292, 2012.

##  5 Appendix

###  5.1 Basic results

We state below Lemmas 5.1 and 5.2 for completeness. The proofs are included in
the Supplementary Material.

######  Lemma 5.1.

For integers $m=m_{1}+\cdots+m_{J}$ we have that

$\dfrac{\prod\limits_{j=1}^{J}\left(\frac{m_{j}}{m}\right)^{m_{j}}}{\prod\limits_{j=1}^{J}\Gamma\left(m_{j}+\frac{1}{2}\right)}\;\leq\;\dfrac{1}{\Gamma\left(m+\frac{1}{2}\right)\Gamma\left(\frac{1}{2}\right)^{J-1}}\,.$
(5.1)

###### Proof.

For an integer $m$, we have that

$\Gamma\left(m+\dfrac{1}{2}\right)=(m+1)(m+2)\dots(2m)\frac{\sqrt{\pi}}{2^{m}}\,.$

Thus, for integers $m_{j}$, $j=1,\dots,J$, such that $m=m_{1}+\cdots+m_{J}$ we
write

$\dfrac{\prod\limits_{j=1}^{J}\Gamma\left(m_{j}+\frac{1}{2}\right)}{\Gamma\left(m+\frac{1}{2}\right)\Gamma\left(\frac{1}{2}\right)^{J-1}}=\dfrac{\prod\limits_{j=1}^{J}(m_{j}+1)(m_{j}+2)\cdots(2m_{j})}{(m+1)(m+2)\cdots(2m)}\,.$
(5.2)

Define, for $y\geq 0$ and an integer $r\geq 1$

$g_{r}(y)=\prod\limits_{i=1}^{r}\left(y+\frac{i}{r}\right)\,.$

As it is shown in the Lemma included in the Appendix of Davisson et al.
(1981), for integers $m=m_{1}+\cdots+m_{J}$ and $y\geq 0$ we have that

$g_{m}(y)\;\leq\;\prod\limits_{j=1}^{J}g_{m_{j}}(y)\,.$ (5.3)

Using this result for $y=1$ and $r=m$ we have that

$\begin{split}\dfrac{\prod\limits_{i=1}^{m}\left(m+i\right)}{m^{m}}&\;\leq\;\prod\limits_{j=1}^{J}\,\prod\limits_{i=1}^{m_{j}}\dfrac{(m_{j}+i)}{m_{j}}=\;\dfrac{\prod\limits_{j=1}^{J}(m_{j}+1)(m_{j}+2)\cdots(2m_{j})}{\prod\limits_{j=1}^{J}m_{j}^{m_{j}}}\,.\end{split}$
(5.4)

Rearranging (5.4) and combining with (5.2) we conclude that

$\prod\limits_{j=1}^{J}\left(\frac{m_{j}}{m}\right)^{m_{j}}\;\leq\;\dfrac{\prod\limits_{j=1}^{J}(m_{j}+1)(m_{j}+2)\cdots(2m_{j})}{(m+1)(m+2)\cdots(2m)}=\dfrac{\prod\limits_{j=1}^{J}\Gamma\left(m_{j}+\frac{1}{2}\right)}{\Gamma\left(m+\frac{1}{2}\right)\Gamma\left(\frac{1}{2}\right)^{J-1}}\,.\qed$

######  Lemma 5.2.

For integers $m=m_{1}+\cdots+m_{J}$, with $J\geq 1$ and $m\geq\max(J,3)$, we
have that

$\frac{\Gamma\left(1\over 2\right)\Gamma\left(m+{J\over
2}\right)}{\Gamma\left(J\over 2\right)\Gamma\left(m+{1\over
2}\right)}\;\leq\;m^{J}\,.$

###### Proof.

Stirlings’ formula for the $\Gamma$ function states that for all $y\geq 0$ we
have

$y^{y-\frac{1}{2}}e^{-y}\sqrt{2\pi}\;\leq\;\Gamma(y)\;\leq\;y^{y-\frac{1}{2}}e^{-y}\sqrt{2\pi}e^{\frac{1}{12y}}\,.$

Then

$\begin{split}\log\left(\dfrac{\Gamma\left(\frac{1}{2}\right)\Gamma\left(m+\frac{J}{2}\right)}{\Gamma\left(\frac{J}{2}\right)\Gamma\left(m+\frac{1}{2}\right)}\right)&\;\leq\;\left(m+\frac{J-1}{2}\right)\log\left(m+\frac{J}{2}\right)-\left(m+\frac{J}{2}\right)+\dfrac{1}{12\left(m+\frac{J}{2}\right)}\\\
&\hskip
56.9055pt-m\log\left(m+\frac{1}{2}\right)+\left(m+\frac{1}{2}\right)+\log\dfrac{\Gamma(\frac{1}{2})}{\Gamma(\frac{J}{2})}\\\
&\;\leq\;\left(m+\frac{J-1}{2}\right)\log\left(m\left(1+\frac{J}{2m}\right)\right)+\dfrac{1}{12m}-m\log\left(m\left(1+\frac{1}{2m}\right)\right)\\\
&\hskip
56.9055pt-\dfrac{J-1}{2}+\log\dfrac{\Gamma(\frac{1}{2})}{\Gamma(\frac{J}{2})}\\\
&\;\leq\;\left(\frac{J-1}{2}\right)\log
m+\left(m+\frac{J-1}{2}\right)\log\left(1+\frac{J}{2m}\right)-m\log\left(1+\frac{1}{2m}\right)\\\
&\hskip
56.9055pt+\dfrac{1}{12m}-\dfrac{J-1}{2}+\log\dfrac{\Gamma(\frac{1}{2})}{\Gamma(\frac{J}{2})}\,.\end{split}$
(5.5)

Using that $1-\frac{1}{y}\leq\log y\leq y-1$, for $y>0$ we obtain that

$\begin{split}\log\left(\dfrac{\Gamma\left(\frac{1}{2}\right)\Gamma\left(m+\frac{J}{2}\right)}{\Gamma\left(\frac{J}{2}\right)\Gamma\left(m+\frac{1}{2}\right)}\right)&\leq\left(\frac{J-1}{2}\right)\log
m+\left(m+\frac{J-1}{2}\right)\left(\frac{J}{2m}\right)+\dfrac{1}{12m}-\dfrac{J-1}{2}+\log\dfrac{\Gamma(\frac{1}{2})}{\Gamma(\frac{J}{2})}\\\
&\leq\left(\frac{J-1}{2}\right)\log
m+\dfrac{J(J-1)}{4m}+\dfrac{1}{12m}+\log\dfrac{\Gamma(\frac{1}{2})}{\Gamma(\frac{J}{2})}\,.\end{split}$

Observe that for $J\geq 1$ and $m\geq\max(J,3)$ we have that

$\log\dfrac{\Gamma(\frac{1}{2})}{\Gamma(\frac{J}{2})}\;\leq\;\log(2)$

and

$\frac{J(J-1)}{4m}\;\leq\;\frac{J-1}{4}\;\leq\;\frac{J-1}{4}\log m\,.$

Then

$\begin{split}\log\left(\dfrac{\Gamma\left(\frac{1}{2}\right)\Gamma\left(m+\frac{J}{2}\right)}{\Gamma\left(\frac{J}{2}\right)\Gamma\left(m+\frac{1}{2}\right)}\right)&\;\leq\;\left(\frac{J-1}{2}\right)\log
m+\frac{J-1}{4}\log m+1\leq\;J\log m\,.\qed\end{split}$

###  5.2 Proof of Proposition 3.1

For each $z\in[k]^{n}$, the space of hiperparameters
$\Theta_{k}=\Theta_{k}(z)$ has the form

$\Theta_{k}=\Pi_{k}\times\Lambda_{k}\times\mathcal{W}(z)$

where

$\Pi_{k}:=\\{(\pi_{1},\ldots,\pi_{k})\in{(0,1]}^{k}\colon\sum_{i}\pi_{i}=1\\}$

is the standard $k$-dimensional simplex,

$\Lambda_{k}:=\\{\lambda\in(\mathbb{R}^{+})^{k\times
k}\colon\lambda_{ab}=\lambda_{ba}\text{ for all }a,b\in[k]\\}$

is the set of $k\times k$ symmetric matrices with positive entries and

$\mathcal{W}(z)=\mathcal{W}_{1}(z)\times\mathcal{W}_{2}(z)\times\dots\times\mathcal{W}_{k}(z)$

with

$\mathcal{W}_{a}(z):=\\{w\in\mathbb{(}\mathbb{R}^{+})^{n_{a}(z)}:\sum_{i}w_{i}=n_{a}(z)\\}$
(5.6)

which is the set of possible $w$’s on community $a$. By the definition of the
model we have that the _a priori_ distribution over $\Theta_{k}$ is given by

$\nu_{k}(\theta)=\nu_{k}^{(1)}(\pi)\nu_{k}^{(2)}(\lambda)\nu^{(3)}(w|z)$ (5.7)

where

$\nu_{k}^{(1)}(\pi)=\dfrac{\Gamma\left(k/2\right)}{{\Gamma\left(1/2\right)}^{k}}\prod_{1\leq
a\leq k}{\pi_{a}}^{-1/2}\,,$
$\nu_{k}^{(2)}(\lambda)=\dfrac{1}{\Gamma(1/2)^{\frac{k(k+1)}{2}}}\prod_{1\leq
a\leq b\leq k}\,\lambda_{ab}^{-1/2}e^{-\lambda_{ab}}$

and

$\nu^{(3)}(w|z)=\prod_{1\leq a\leq k}\,\frac{\Gamma\left({{n_{a}(z)}\over
2}\right)}{{n_{a}(z)\Gamma\left({1\over 2}\right)}^{n_{a}(z)}}\prod_{i\colon
z_{i}=a}\Bigl{(}\frac{w_{i}}{n_{a}(z)}\Bigr{)}^{-1/2}\,.$

We can now decompose the marginal likelihood as

$\displaystyle p_{k}(x)$
$\displaystyle\;=\;\sum_{z\in[k]^{n}}\int_{{\Theta}^{k}}p(x,z|\theta)\nu_{k}(\theta)d\theta$
$\displaystyle\;=\;\sum_{z\in[k]^{n}}\int_{\mathcal{W}(z)}\int_{\Lambda^{k}}p(x|w,z,\lambda)\nu^{(2)}_{k}(\lambda)\nu^{(3)}(w|z)d\lambda
dw\int_{\Delta^{k}}p(z|\pi)\nu^{(1)}_{k}(\pi)d\pi$
$\displaystyle\;=:\;\sum_{z\in[k]^{n}}p_{k}(x|z)p_{k}(z)$

in which the (conditional) likelihoods were given in (2.5) and (2.6). Then we
have that

$\begin{split}\int_{\Lambda^{k}}p(x|w,z,\lambda)&\nu^{(2)}_{k}(\lambda)d\lambda\;=\;\int_{\Lambda^{k}}\dfrac{1}{c(x)}\Biggl{[}\prod_{1\leq
i\leq n}{w_{i}}^{d_{i}(x)}\Biggr{]}\Biggl{[}\prod_{1\leq a\leq b\leq
k}\lambda_{ab}^{o_{ab}(x,z)}e^{-n_{ab}(z)\lambda_{ab}}\Biggr{]}\nu^{(2)}_{k}(\lambda)d\lambda\\\
&=\dfrac{1}{c(x)\Gamma({1\over 2})^{k(k+1)\over 2}}\Biggl{[}\prod_{1\leq i\leq
n}{w_{i}}^{d_{i}(x)}\Biggr{]}\int_{\Lambda^{k}}\prod_{1\leq a\leq b\leq
k}\lambda_{ab}^{o_{ab}{(x,z)}-\frac{1}{2}}e^{-(n_{ab}(z)+1)\lambda_{ab}}d\lambda\\\
&=\dfrac{1}{c(x)}\underbrace{\dfrac{1}{\Gamma({1\over 2})^{k(k+1)\over
2}}\Biggl{[}\prod_{1\leq a\leq b\leq k}\frac{\Gamma\left(o_{ab}(x,z)+{1\over
2}\right)}{[n_{ab}(z)+1]^{o_{ab}(x,z)+\frac{1}{2}}}\Biggr{]}}_{A(x,z)}\Biggl{[}\prod_{1\leq
i\leq n}{w_{i}}^{d_{i}(x)}\Biggr{]}.\end{split}$ (5.8)

Therefore

$\begin{split}p_{k}(x|z)&=\frac{A(x,z)}{c(x)}\int_{\mathcal{W}}\prod_{1\leq
i\leq n}{w_{i}}^{d_{i}(x)}\nu^{(3)}(w|z)dw\\\
&=\frac{A(x,z)}{c(x)}\prod_{1\leq a\leq k}\frac{\Gamma\left({{n_{a}(z)}\over
2}\right)}{{n_{a}(z)\Gamma\left({1\over
2}\right)}^{n_{a}(z)}}\int_{\mathcal{W}_{a}(z)}\prod_{i\colon
z_{i}=a}{w_{i}}^{d_{i}(x)}\Bigl{(}\frac{w_{i}}{n_{a}(z)}\Bigr{)}^{-1/2}dw_{a}\\\
&=\frac{A(x,z)}{c(x)}\prod_{1\leq a\leq k}\frac{\Gamma\left({{n_{a}(z)}\over
2}\right)n_{a}(z)^{d^{t}_{a}(x,z)-1}}{{\Gamma\left({1\over
2}\right)}^{n_{a}(z)}}\int_{\mathcal{W}_{a}(z)}\prod_{i\colon
z_{i}=a}{\Bigl{(}\frac{w_{i}}{n_{a}(z)}\Bigr{)}}^{d_{i}(x)-1/2}dw_{a}\\\
&=\frac{A(x,z)}{c(x)}\prod_{1\leq a\leq k}\frac{\Gamma\left({{n_{a}(z)}\over
2}\right)n_{a}(z)^{d^{t}_{a}(x,z)}}{{\Gamma\left({1\over
2}\right)}^{n_{a}(z)}}\int_{\mathcal{Y}_{a}(z)}\prod_{i\colon
z_{i}=a}{y_{i}}^{d_{i}(x)-1/2}dy\\\
&=\frac{A(x,z)}{c(x)}\underbrace{\prod_{1\leq a\leq
k}\frac{n_{a}(z)^{d^{t}_{a}(x,z)}\Gamma\left({{n_{a}(z)}\over
2}\right)}{{\Gamma\left({1\over 2}\right)}^{n_{a}(z)}}\frac{\prod_{i\colon
z_{i}=a}\Gamma(d_{i}(x)+\frac{1}{2})}{\Gamma(d^{t}_{a}(x,z)+\frac{n_{a}(z)}{2})}}_{B(x,z)}\,.\end{split}$
(5.9)

We also have that

$\begin{split}p_{k}(z)&=\;\int_{\Pi^{k}}\prod_{a=1}^{k}{\pi_{a}}^{n_{a}({z})}\nu^{(1)}_{k}(\pi)d\pi\\\
&=\;\dfrac{\Gamma\left({k\over 2}\right)}{{\Gamma\left({1\over
2}\right)}^{k}}\int_{\Pi^{k}}\prod_{a=1}^{k}{\pi_{a}}^{n_{a}({z})-{1\over
2}}d{\pi}\\\ &=\;\underbrace{\dfrac{\Gamma\left({k\over
2}\right)}{{\Gamma\left({1\over
2}\right)}^{k}}\dfrac{\prod_{a=1}^{k}\Gamma\left(n_{a}(z)+{1\over
2}\right)}{\Gamma\left(n+{k\over 2}\right)}}_{C(z)}\,.\end{split}$ (5.10)

On the other hand, by the definition of the maximum likelihood estimators we
have that

$\begin{split}\sup_{\lambda,w}\;p(x|z,w,\lambda)&={1\over
c(x)}\underbrace{\Bigl{[}\prod_{1\leq a\leq b\leq
k}\left(\frac{o_{ab}(x,z)}{n_{ab}(z)}\right)^{o_{ab}(x,z)}e^{-o_{ab}(x,z)}\Bigr{]}}_{\widehat{A}(x,z)}\\\
&\qquad\times\underbrace{\Bigl{[}\prod_{a\in[k],i\in[n]:z_{i}=a}\left(\frac{n_{a}(z)d_{i}(x)}{d^{t}_{a}(x,z)}\right)^{d_{i}(x)}\Bigr{]}}_{\widehat{B}(x,z)}\,\end{split}$
(5.11)

and

$\begin{split}\sup_{\pi}\;p(z|\pi)&=\underbrace{\prod_{1\leq a\leq
k_{0}}\left(\frac{n_{a}(z)}{n}\right)^{n_{a}(z)}}_{\widehat{C}(z)}\,.\end{split}$
(5.12)

Now, we observe that by canceling the normalizing constant $c(x)$ we obtain
that

$\displaystyle\frac{\sup_{\theta}p(x|\theta)}{p_{k}(x)}$
$\displaystyle\;\leq\;\frac{\sum_{z}\widehat{A}(x,z)\widehat{B}(x,z)\widehat{C}(z)}{\sum_{z}A(x,z)B(x,z)C(z)}\,.$
(5.13)

Now, if we are able to find bounds $D_{1},D_{2}$ and $D_{3}$, uniform on $x$
and $z$, such that

$\frac{\widehat{A}(x,z)}{A(x,z)}\;\leq\;D_{1}\,,\quad\frac{\widehat{B}(x,z)}{B(x,z)}\;\leq\;D_{2}\,\quad\text{and}\quad\frac{\widehat{C}(x,z)}{C(x,z)}\;\leq\;D_{3}$

then we automatically get

$\dfrac{\sup_{\theta}p(x|\theta)}{p_{k}(x)}\;\leq\;D_{1}\,D_{2}\,D_{3}\,.$
(5.14)

These bounds follow by Lemmas 5.3, 5.4 and 5.5 proved below. Using these
lemmas we obtain that

$\begin{split}\log\frac{\sup_{\theta}p(x|\theta)}{p_{k}(x)}\;&\leq\;\log\Bigl{[}(n+1)^{k(k+1)}(n^{2}\log
n)^{n}n^{k}\Bigr{]}\\\ &\leq\;k(k+1)\log(n+1)+n(2\log n+\log\log n)+k\log n\\\
&\leq\;k(k+2)\log(n+1)+3n\log n\end{split}$

concluding the proof of Proposition 3.1.

######  Lemma 5.3.

For $(x,z)\in\Omega_{n}\times[k]^{n}$ we have that

$\frac{\widehat{A}(x,z)}{A(x,z)}\;\leq\;(n+1)^{k(k+1)}\,.$ (5.15)

###### Proof.

Fix any $(x,z)\in\Omega_{n}\times[k]^{n}$. We simplify the notation by writing
$o_{ab}=o_{ab}(x,z)$ and similarly for $n_{a}(z)$ and $n_{ab}(z)$. By (5.8) an
(5.11) we obtain that

$\displaystyle\frac{\widehat{A}(x,z)}{A(x,z)}$
$\displaystyle\;=\;\dfrac{\prod_{1\leq a\leq b\leq
k}\left(\frac{o_{ab}}{n_{ab}}\right)^{o_{ab}}e^{-o_{ab}}}{\dfrac{1}{\Gamma({1\over
2})^{k(k+1)\over 2}}\prod_{1\leq a\leq b\leq
k}\frac{\Gamma\left(o_{ab}+{1\over
2}\right)}{[n_{ab}+1]^{o_{ab}+\frac{1}{2}}}}$
$\displaystyle=\Gamma\left({1\over 2}\right)^{k(k+1)\over 2}\prod_{1\leq a\leq
b\leq
k}\dfrac{\left({o_{ab}}\over{n_{ab}}\right)^{o_{ab}}e^{-o_{ab}}{\left(n_{ab}+1\right)^{o_{ab}+\frac{1}{2}}}}{{\Gamma\left({o_{ab}}+{1\over
2}\right)}}.$ (5.16)

Letting

$N:=\sum_{1\leq a\leq b\leq k}o_{ab}$

we rewrite

$\frac{\widehat{A}(x,z)}{A(x,z)}=\Gamma\left({1\over 2}\right)^{k(k+1)\over
2}\prod_{1\leq a\leq b\leq k}\dfrac{\left({o_{ab}\over
N}\right)^{o_{ab}}}{\Gamma\left(o_{ab}+{1\over 2}\right)}\left({N\over
n_{ab}}\right)^{o_{ab}}\left(n_{ab}+1\right)^{o_{ab}+{1\over 2}}e^{-o_{ab}}.$
(5.17)

We now use Lemma 5.1 to get

$\prod_{1\leq a\leq b\leq k}\dfrac{\left({o_{ab}\over
N}\right)^{o_{ab}}}{\Gamma\left({o_{ab}}+{1\over
2}\right)}\;\leq\;\dfrac{1}{\Gamma\left(N+{1\over 2}\right)\Gamma\left({1\over
2}\right)^{{k(k+1)\over 2}-1}}\,.$ (5.18)

On the other hand

$\displaystyle\left({N\over
n_{ab}}\right)^{o_{ab}}\left(n_{ab}+1\right)^{o_{ab}+{1\over 2}}e^{-o_{ab}}$
$\displaystyle\;=\;N^{o_{ab}}\left(1+\frac{1}{n_{ab}}\right)^{o_{ab}}\left(n_{ab}+1\right)^{1\over
2}e^{-o_{ab}}$ $\displaystyle\;\leq\;N^{o_{ab}}\;e^{o_{ab}\over
n_{ab}}\left(n_{ab}+1\right)^{1\over 2}e^{-o_{ab}}.$ (5.19)

Putting (5.18) and (5.2) in (5.17), we get

$\displaystyle\frac{\widehat{A}(x,z)}{A(x,z)}$
$\displaystyle\;\leq\;\frac{\Gamma\left({1\over 2}\right)^{k(k+1)\over
2}}{\Gamma\left(N+{1\over 2}\right)\Gamma\left({1\over 2}\right)^{{k(k+1)\over
2}-1}}\prod_{1\leq a\leq b\leq
k}N^{o_{ab}}e^{\frac{o_{ab}}{n_{ab}}}\left(n_{ab}+1\right)^{1\over
2}e^{-o_{ab}}$ $\displaystyle=\frac{\Gamma\left({1\over
2}\right)}{\Gamma\left(N+{1\over 2}\right)}e^{-N}N^{N}e^{\sum_{1\leq a\leq
b\leq k}{o_{ab}\over n_{ab}}}\prod_{1\leq a\leq b\leq
k}\left(n_{ab}+1\right)^{1\over 2}.$ (5.20)

For any real number $r>0$, $\Gamma(r)\geq r^{r-1/2}e^{-r}\sqrt{2\pi}$, so that

$\dfrac{e^{-N}N^{N}}{\Gamma\left(N+{1\over 2}\right)}\;\leq\;\left(1+{1\over
2N}\right)^{-N}e^{1\over
2}\frac{1}{\sqrt{2\pi}}\;\leq\;\frac{1}{\sqrt{2\pi}}.$ (5.21)

Moreover, as $x\in\Omega_{n}$ we have that

$\displaystyle\sum_{1\leq a\leq b\leq k}{o_{ab}\over
n_{ab}}\;\leq\;\sum_{1\leq a\leq b\leq k}{n_{ab}\log n\over
n_{ab}}\;=\;{k(k+1)\over 2}\log n$ (5.22)

and

$\prod_{1\leq a\leq b\leq k}\left(n_{ab}+1\right)^{1\over
2}\;\leq\;\prod_{1\leq a\leq b\leq k}\left(n^{2}+1\right)^{1\over
2}\;=\;\left(n^{2}+1\right)^{k(k+1)\over 4}\;\leq\;(n+1)^{k(k+1)\over 2}.$
(5.23)

Plugging (5.21), (5.22) and (5.23) into (5.2) proves the lemma. ∎

######  Lemma 5.4.

For $(x,z)\in\Omega_{n}\times[k]^{n}$ we have

$\frac{\widehat{B}(x,z)}{B(x,z)}\;\leq\;(n^{2}\log n)^{n}.$ (5.24)

###### Proof.

For $(x,z)\in\Omega_{n}\times[k]^{n}$ we have that

$\displaystyle\frac{\widehat{B}(x,z)}{B(x,z)}$ $\displaystyle=\prod_{1\leq
a\leq
k}\frac{\prod_{i\in[n]:z_{i}=a}\left(\frac{n_{a}(z)d_{i}(x)}{d^{t}_{a}(x,z)}\right)^{d_{i}(x)}}{\frac{n_{a}(z)^{d^{t}_{a}(x,z)}\Gamma\left({{n_{a}(z)}\over
2}\right)}{{\Gamma\left({1\over 2}\right)}^{n_{a}(z)}}\frac{\prod_{i\colon
z_{i}=a}\Gamma(d_{i}(x)+\frac{1}{2})}{\Gamma(d^{t}_{a}(x,z)+\frac{n_{a}(z)}{2})}}$
$\displaystyle=\prod_{1\leq a\leq k}\frac{{\Gamma\left({1\over
2}\right)}^{n_{a}(z)}{\Gamma(d^{t}_{a}(x,z)+\frac{n_{a}(z)}{2})}}{\Gamma\left({{n_{a}(z)}\over
2}\right)}\prod_{i:z_{i}=a}\frac{\left(\frac{d_{i}(x)}{d^{t}_{a}(x,z)}\right)^{d_{i}(x)}}{\Gamma(d_{i}(x)+\frac{1}{2})}$

But for all $a\in[k]$ we have by Lemma 5.1 that

$\prod_{i:z_{i}=a}\frac{\left(\frac{d_{i}(x)}{d^{t}_{a}(x,z)}\right)^{d_{i}(x)}}{\Gamma(d_{i}(x)+\frac{1}{2})}\;\leq\;\dfrac{1}{\Gamma\left(d^{t}_{a}(x,z)+{1\over
2}\right){\Gamma\left(1\over 2\right)}^{n_{a}(z)-1}},$ (5.25)

where we used the equality $d^{t}_{a}(x,z)=\sum_{i:z_{i}=a}d_{i}(x)$. Putting
all the previous bounds together we obtain that

$\displaystyle\frac{\widehat{B}(x,z)}{B(x,z)}$
$\displaystyle\;\leq\;\prod_{1\leq a\leq k}\frac{{\Gamma\left({1\over
2}\right)}{\Gamma(d^{t}_{a}(x,z)+\frac{n_{a}(z)}{2})}}{\Gamma\left({{n_{a}(z)}\over
2}\right)\Gamma\left(d^{t}_{a}(x,z)+{1\over 2}\right)}.$

Finally, by Lemma 5.2 we conclude, as $d^{t}_{a}(x,z)\leq n^{2}\log n$ for all
$a\in[k]$ and $\sum_{a}n_{a}(z)=n$ that

$\displaystyle\frac{\widehat{B}(x,z)}{B(x,z)}\;\leq\;\prod_{1\leq a\leq
k}d^{t}_{a}(x,z)^{n_{a}(z)}\;\leq\;(n^{2}\log n)^{n}\,.$

∎

######  Lemma 5.5.

For any $z\in[k]^{n}$ we have that

$\frac{\widehat{C}(z)}{C(z)}\;\leq\;n^{k}\,.$ (5.26)

###### Proof.

By definition we have that

$\displaystyle\frac{\widehat{C}(z)}{C(z)}$
$\displaystyle=\frac{\prod_{a=1}^{k}{\left(\dfrac{n_{a}({z})}{n}\right)}^{n_{a}({z})}}{\dfrac{\Gamma\left({k\over
2}\right)}{{\Gamma\left({1\over
2}\right)}^{k}}\dfrac{\prod_{a=1}^{k}\Gamma\left(n_{a}(z)+{1\over
2}\right)}{\Gamma\left(n+{k\over 2}\right)}}\,.$

By Lemma 5.1 we obtain that

$\prod_{a=1}^{k}\dfrac{{\left(\dfrac{n_{a}(z)}{n}\right)}^{n_{a}(z)}}{\Gamma\left(n_{a}(z)+{1\over
2}\right)}\;\leq\;\dfrac{1}{\Gamma\left(n+{1\over 2}\right){\Gamma\left(1\over
2\right)}^{k-1}}\,.$ (5.27)

Then by Lemma 5.2 and (5.27) we have that

$\displaystyle\frac{\widehat{C}(z)}{C(z)}\;\leq\;\frac{{{\Gamma\left({1\over
2}\right)\Gamma\left(n+{k\over 2}\right)}}}{{\Gamma\left({k\over
2}\right)\Gamma\left(n+{1\over 2}\right)}}\;\leq\;n^{k}\,.$

∎

###  5.3 Proof of other auxiliary lemmas

######  Lemma 5.6.

Let $X=(X_{ij})_{i,j\in[n]}$ be generated by a DCSBM and let $\Omega_{n}$ be
the set defined in (3.5). Then $X\in\Omega_{n}$ eventually almost surely as
$n\to\infty$.

###### Proof.

We have that

$\begin{split}p(\Omega_{n}^{c})&\;=\;\sum_{z\in[k_{0}]^{n}}p(\Omega_{n}^{c}\cap\\{Z=z\\})\\\
&\;=\;\sum_{z\in[k_{0}]^{n}}p(z)p(\Omega_{n}^{c}|Z=z)\\\
&\leq\sum_{z\in[k_{0}]^{n}}p(z)\sum_{i,j=1}^{n}p(X_{ij}>\log
n|Z=z).\end{split}$ (5.28)

Conditionally on $Z=z$, the $X_{ij}$’s have a Poisson distribution with
parameter $(\lambda_{z_{i}z_{j}})$. From (Boucheron et al., 2013, Section
2.2), if $Y\sim\text{Poisson}(\mu)$, then for $r>0$

$\begin{split}P(Y-\mu\geq r)&\leq
e^{-\mu\left(1+\frac{r}{\mu}\right)\log\left(1+\frac{r}{\mu}\right)+r}\\\
&\leq e^{-r\left(\log\left(1+\frac{r}{\mu}\right)-1\right)},\end{split}$

thus for $n$ such that $\log n>\lambda_{z_{i}z_{j}}$

$\displaystyle p(X_{ij}\geq\log n|Z=z)$ $\displaystyle\leq e^{-(\log
n-\lambda_{z_{i}z_{j}})\left(\log\left(\frac{\log
n}{\lambda_{z_{i}z_{j}}}\right)-1\right)}$ $\displaystyle\leq e^{-(\log
n-\lambda_{\max})\left(\log\left(\frac{\log
n}{\lambda_{\max}}\right)-1\right)}$ (5.29)

where in the last line we used the notation
$\lambda_{\max}=\max_{a,b}\lambda_{ab}$. Then, by (5.28) and (5.29) we have
that

$\displaystyle p(\Omega_{n}^{c})\leq\;n^{2}e^{-(\log
n-\lambda_{\max})\left(\log\left(\frac{\log
n}{\lambda_{\max}}\right)-1\right)}\sum_{z\in[k_{0}]^{n}}p(z)=n^{3+\log\lambda_{\max}-\log(\log
n)}\left(\log
n\right)^{\lambda_{\max}}\left(e\lambda_{\max}\right)^{-\lambda_{\max}}$

which is summable in $n$ and therefore, by the Borel Cantelli Lemma we have
that $X\in\Omega_{n}$ eventually almost surely as $n\to\infty$. ∎

To state the next auxiliary result, we need some notation. Define for all
$z\in\\{1,\dots,k\\}^{n}$ and $z^{0}\in\\{1,\dots,k_{0}\\}^{n}$ the $k\times
k_{0}$ matrix $Q_{n}(z,z^{0})$ given by

$[Q_{n}(z,z^{0})]_{aa^{\prime}}\;=\;{1\over
n}\sum_{i=1}^{n}w_{i}\,\mathds{1}\\{z_{i}=a,z_{i}^{0}=a^{\prime}\\}.$ (5.30)

Observe that the counters $n_{a^{\prime}}(z^{0})$, for $a^{\prime}\in[k_{0}]$,
can be written as

$n_{a^{\prime}}(z^{0})=\sum_{i=1}^{n}w_{i}\,\mathds{1}\\{z_{i}^{0}=a^{\prime}\\}=\sum_{i=1}^{n}w_{i}\,\sum_{a=1}^{k}\mathds{1}\\{z_{i}=a,z_{i}^{0}=a^{\prime}\\}\,.$
(5.31)

Then $n_{a^{\prime}}(z^{0})=n(Q_{n}^{T}(z,z^{0}){\bf 1}_{k})_{a^{\prime}}$,
with ${\bf 1}_{k}$ a column vector of dimension $k$ with all entries equal to
1. Moreover, the matrix $Q_{n}(z,z^{0})$ satisfies

$\|Q_{n}(z,z^{0})\|_{1}\;=\;\sum_{a=1}^{k}\sum_{a^{\prime}=1}^{k_{0}}[Q_{n}(z,z^{0})]_{a,a^{\prime}}=1,\,$
(5.32)

for all $(z,z^{0})$ and

$\mathbb{E}(\tilde{o}_{ab}(x,z)\,|\,Z=z^{0})\;=\;n^{2}Q_{n}(z,z^{0})\lambda
Q_{n}(z,z^{0})^{T}\;=\;\rho_{n}n^{2}Q_{n}(z,z^{0})\tilde{\lambda}Q_{n}(z,z^{0})^{T}\,.$
(5.33)

We now prove a concentration bound for $\tilde{o}_{ab}(x,z)$ conditionally on
$Z=z^{0}$, that is a sum of independent Poisson random variables.

######  Lemma 5.7.

For any $\epsilon>0$ and $a,b\in[k]$ we have that

$\mathbb{P}\Bigl{(}\;\sup_{\bar{z}\in[k]^{n}}\;\Bigl{|}\frac{\tilde{o}_{ab}(X,\bar{z})}{\rho_{n}n^{2}}-[Q_{n}(\bar{z},Z)\tilde{\lambda}Q_{n}(\bar{z},Z)^{T}]_{ab}\Bigr{|}>\epsilon\Bigr{)}\;\leq\;\exp\Bigl{(}-\frac{\rho_{n}n^{2}\epsilon^{2}}{\tilde{\lambda}_{\max}+\epsilon}+n\log
k\Bigr{)}$

and

$\mathbb{P}\Bigl{(}\,\sup_{\bar{z}\in[k]^{n}}\,\Bigr{|}\frac{d^{t}_{a}(X,\bar{z})}{\rho_{n}n^{2}}-[Q_{n}(\bar{z},Z)\tilde{\lambda}Q_{n}(\bar{z},Z)^{T}{\bf
1}_{k}]_{a}\Bigr{|}\;>\;\epsilon\Bigr{)}\;\leq\;\exp\Bigl{(}-\frac{\rho_{n}n^{2}\epsilon^{2}}{\tilde{\lambda}_{\max}+\epsilon}+n\log
k\Bigr{)}\,,$

with $\tilde{\lambda}_{\max}=\max_{ab}\tilde{\lambda}_{ab}$.

###### Proof.

For any fixed $z\in[k_{0}]^{n}$ and $\bar{z}\in[k]^{n}$ we have that

$\begin{split}\tilde{o}_{ab}(X,\bar{z})&-n^{2}[Q_{n}(\bar{z},z)\lambda
Q_{n}(\bar{z},z)^{T}]_{ab}\\\
&=\tilde{o}_{ab}(X,\bar{z})-\rho_{n}n^{2}[Q_{n}(\bar{z},z)\tilde{\lambda}Q_{n}(\bar{z},z)^{T}]_{ab}\\\
&=\sum_{1\leq i,j\leq n}\sum_{1\leq a^{\prime},b^{\prime}\leq
k_{0}}(X_{ij}-\rho_{n}w_{i}w_{j}\tilde{\lambda}_{a^{\prime}b^{\prime}}){\mathds{1}}\\{\bar{z}_{i}=a,z_{i}=a^{\prime}\\}{\mathds{1}}\\{\bar{z}_{j}=b,z_{j}=b^{\prime}\\}\,.\end{split}$

Observe that given $Z=z$, $\tilde{o}_{ab}(X,\bar{z})$ corresponds to the sum
of $n_{a}(\bar{z})n_{b}(\bar{z})$ independent Poisson random variables, given
by $X_{ij}{\mathds{1}}\\{\bar{z}_{i}=a,\bar{z}_{i}=b\\}$, with expected value
given by $\rho_{n}w_{i}w_{j}\tilde{\lambda}_{z_{i}z_{j}}$. Then the sum is
also Poisson distributed with a parameter that is the sum of the corresponding
parameters. Using one more time (Boucheron et al., 2013, Section 2.2), we have
for $Y\sim\text{Poisson}(\mu)$ and $t>0$

$\displaystyle P(Y-\mu\geq r)$ $\displaystyle\leq
e^{-\mu\left(1+\frac{r}{\mu}\right)\log\left(1+\frac{r}{\mu}\right)+r}$
$\displaystyle P(Y-\mu\leq-r)$ $\displaystyle\leq
e^{-\mu\left(1-\frac{r}{\mu}\right)\log\left(1-\frac{r}{\mu}\right)-r}$

which, after some algebra, yields

$\mathbb{P}(|X-\mu|>r)\;\leq\;2e^{-\frac{r^{2}}{2(\mu+r)}}\,.$

Therefore, for any $\delta>0$

$\displaystyle\mathbb{P}\Bigl{(}\,\Bigl{|}\tilde{o}_{ab}(X,\bar{z})$
$\displaystyle-\rho_{n}n^{2}[Q_{n}(\bar{z},z)\tilde{\lambda}Q_{n}(\bar{z},z)^{T}]_{ab}\Bigr{|}\,>\,\delta\,|Z\,=z\Bigr{)}$
$\displaystyle\leq\;2\exp\Bigl{(}-\frac{\delta^{2}}{2(\rho_{n}n^{2}[Q_{n}(\bar{z},z)\tilde{\lambda}Q_{n}(\bar{z},z)^{T}]_{ab}+\delta)}\Bigr{)}\,.$

Since, for any $\bar{z}$ and $z$, we have that

$\rho_{n}n^{2}[Q_{n}(\bar{z},z)\tilde{\lambda}Q_{n}(\bar{z},z)^{T}]_{ab}\;\leq\;\rho_{n}n^{2}\tilde{\lambda}_{\max}$

with $\tilde{\lambda}_{\max}=\max_{ab}\tilde{\lambda}_{ab}$, it follows that,
for any $z,\bar{z}$ and $\epsilon>0$

$\displaystyle\mathbb{P}\Bigl{(}\,\Bigr{|}\frac{\tilde{o}_{ab}(X,\bar{z})}{\rho_{n}n^{2}}-[Q_{n}(\bar{z},z)\tilde{\lambda}Q_{n}(\bar{z},z)^{T}]_{ab}\Bigr{|}\;>\;\epsilon\,|\,Z=z\Bigr{)}\;$
$\displaystyle\leq\;\exp\Bigl{(}-\frac{\rho_{n}^{2}n^{4}\epsilon^{2}}{\rho_{n}n^{2}\tilde{\lambda}_{\max}+\epsilon\rho_{n}n^{2}}\Bigr{)}$
$\displaystyle\leq\;\exp\Bigl{(}-\frac{\rho_{n}n^{2}\epsilon^{2}}{\tilde{\lambda}_{\max}+\epsilon}\Bigr{)}\,.$

Now, using a union bound over all $\bar{z}\in[k]^{n}$ and integrating over $z$
we obtain that

$\mathbb{P}\Bigl{(}\,\sup_{\bar{z}\in[k]^{n}}\,\Bigr{|}\frac{\tilde{o}_{ab}(X,\bar{z})}{\rho_{n}n^{2}}-[Q_{n}(\bar{z},Z)\tilde{\lambda}Q_{n}(\bar{z},Z)^{T}]_{ab}\Bigr{|}\;>\;\epsilon\Bigr{)}\;\leq\;\exp\Bigl{(}-\frac{\rho_{n}n^{2}\epsilon^{2}}{\tilde{\lambda}_{\max}+\epsilon}+n\log
k\Bigr{)}$

and this proves the first inequality of the lemma. Now, given $Z=z$,

$d_{a}^{t}(X,\bar{z})\;=\;\sum_{b\in[k]}\tilde{o}_{ab}(X,\bar{z})$

is also a sum of independent random variables with Poisson distribution and

$\mathbb{E}(d^{t}_{a}(X,\bar{z})\,|\,Z=z)\;=\;[\rho_{n}n^{2}Q_{n}(\bar{z},z)\tilde{\lambda}Q_{n}(\bar{z},z)^{T}{\bf
1}_{k}]_{a},$

thus we also obtain that

$\mathbb{P}\Bigl{(}\,\sup_{\bar{z}\in[k]^{n}}\,\Bigr{|}\frac{d^{t}_{a}(X,\bar{z})}{\rho_{n}n^{2}}-[Q_{n}(\bar{z},Z)\tilde{\lambda}Q_{n}(\bar{z},Z)^{T}{\bf
1}_{k}]_{a}\Bigr{|}\;>\;\epsilon\Bigr{)}\;\leq\;\exp\Bigl{(}-\frac{\rho_{n}n^{2}\epsilon^{2}}{\tilde{\lambda}_{\max}+\epsilon}+n\log
k\Bigr{)}\,.$

This concludes the proof of Lemma 5.7 ∎

In the sequel, we state and prove the lemmas cited in the proof of Proposition
4.1.

######  Lemma 5.8.

For $k<k_{0}$ there exists a $k\times k$ positive matrix $\lambda^{*}$ and $k$
dimensional vector $\pi^{*}$ such that

$\begin{split}\limsup_{n\to\infty}\;\frac{1}{2}\sum_{1\leq a,b\leq
k}&\frac{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}{\rho_{n}^{2}n^{4}}\;\varphi\Bigl{(}\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,\widehat{z}_{k})}{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}\Bigr{)}\\\
&\leq\;\frac{1}{2}\sum_{1\leq a,b\leq
k}\pi^{*}_{a}\pi^{*}_{b}[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}\;\varphi\biggl{(}\dfrac{\lambda^{*}_{ab}}{[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}}\biggr{)}\,.\end{split}$
(5.34)

Moreover, $(\pi^{*},\lambda^{*})$ are given by

$\begin{split}\pi^{*}_{a}&\;=\;[R^{*}{\bf 1}_{k_{0}}]_{a},\,\qquad
a\in\\{1,\dots,k\\}\\\
\lambda^{*}_{ab}&\;=\;\frac{[R^{*}\lambda{R^{*^{T}}}]_{ab}}{[R^{*}{\bf
1}_{k_{0}}{\bf 1}_{k_{0}}^{T}R^{*^{T}}]_{ab}}\,,\qquad
a,b\in\\{1,\dots,k\\}\,,\end{split}$ (5.35)

for a $k\times k_{0}$ real matrix $R^{*}$ satisfying $\|R^{*}\|_{1}=1$ and
having one and only one non-zero entry on each column.

###### Proof.

Observe that

$\begin{split}\sum_{1\leq a,b\leq
k}&\frac{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}{\rho_{n}^{2}n^{4}}\varphi\Bigl{(}\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,\widehat{z}_{k})}{\rho_{n}\,d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}\Bigr{)}\\\
\;&=\;\sum_{1\leq a,b\leq
k}\frac{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}{\rho_{n}^{2}n^{4}}\varphi\left(\frac{\tilde{o}_{ab}(x,\widehat{z}_{k})/\rho_{n}n^{2}}{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})/\rho_{n}^{2}n^{4}}\right),\end{split}$
(5.36)

where $\varphi(u)=u\log u$. Then by Lemma 5.7, taking
$\epsilon_{n}=\rho_{n}=\frac{\log n}{n}$ we have that

$\Bigl{|}\frac{\tilde{o}_{ab}(x,\widehat{z}_{k})}{\rho_{n}n^{2}}-[Q_{n}(\widehat{z}_{k},z)\tilde{\lambda}Q_{n}^{T}(\widehat{z}_{k},z)]_{ab}\Bigr{|}\;\leq\;\epsilon_{n}$

and similarly

$\Bigl{|}\frac{d^{t}_{a}(x,\widehat{z}_{k})}{\rho_{n}n^{2}}-[Q_{n}(\widehat{z}_{k},z)\tilde{\lambda}Q_{n}(\widehat{z}_{k},z)^{T}\mathbf{1}_{k}]_{a}\Bigr{|}\;\leq\;\epsilon_{n}$

eventually almost surely as $n\to\infty$. Then as $\varphi$ is continuous,
substituting $\tilde{o}_{ab}(x,\widehat{z}_{k})/\rho_{n}n^{2}$ by
$[Q_{n}(\widehat{z}_{k},z)\tilde{\lambda}Q_{n}^{T}(\widehat{z}_{k},z)]_{ab}$
and $d^{t}_{a}(x,\widehat{z}_{k})/\rho_{n}n^{2}$ by
$[Q_{n}(\widehat{z}_{k},z)\tilde{\lambda}Q_{n}(\widehat{z}_{k},z)^{T}\mathbf{1}_{k}]_{a}$
in the right-hand side of (5.36) we obtain that

$\begin{split}\sum_{1\leq a,b\leq
k}&\frac{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}{\rho_{n}^{2}n^{4}}\,\varphi\Bigl{(}\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,\widehat{z}_{k})}{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}\Bigr{)}\\\
&\;\leq\;\;\sup_{\begin{subarray}{c}Q_{n}\colon\|Q_{n}\|_{1}=1\\\
Q_{n}^{T}{\bf 1}_{k}=n(z)/n\end{subarray}}\;\sum_{1\leq a,b\leq
k}[Q_{n}\tilde{\lambda}Q_{n}^{T}\mathbf{1}_{k}]_{a}[Q_{n}\tilde{\lambda}Q_{n}^{T}\mathbf{1}_{k}]_{b}\;\varphi\biggl{(}\dfrac{[Q_{n}\tilde{\lambda}Q_{n}^{T}]_{ab}}{[Q_{n}\tilde{\lambda}Q_{n}^{T}\mathbf{1}_{k}]_{a}[Q_{n}\tilde{\lambda}Q_{n}^{T}\mathbf{1}_{k}]_{b}}\biggr{)}+\eta_{n}\,.\end{split}$
(5.37)

for some sequence $\eta_{n}\to 0$ as $n\to\infty$. Then taking $\lim\sup$ on
both sides, we must have that

$\begin{split}\limsup_{n\to\infty}\;\sum_{1\leq a,b\leq
k}&\frac{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}{\rho_{n}^{2}n^{4}}\,\varphi\Bigl{(}\frac{\rho_{n}n^{2}\tilde{o}_{ab}(x,\widehat{z}_{k})}{d^{t}_{a}(x,\widehat{z}_{k})d^{t}_{b}(x,\widehat{z}_{k})}\Bigr{)}\\\
&\;\leq\;\;\sup_{\begin{subarray}{c}R\colon\|R\|_{1}=1\\\ R^{T}{\bf
1}_{k}=\pi\end{subarray}}\;{1\over 2}\sum_{1\leq a,b\leq
k}[R\tilde{\lambda}R^{T}{\bf 1}_{k}]_{a}[R\tilde{\lambda}R^{T}{\bf
1}_{k}]_{b}\;\varphi\biggl{(}\dfrac{[R\tilde{\lambda}R^{T}]_{ab}}{[R\tilde{\lambda}R^{T}{\bf
1}_{k}]_{a}[R\tilde{\lambda}R^{T}{\bf 1}_{k}]_{b}}\biggr{)}\end{split}$ (5.38)

almost surely. Then, the supremum in the right-hand side of (5.38) is a
maximum of a convex function over a convex polyhedron defined by
$\\{R\colon\|R\|_{1}=1,R^{T}{\bf 1}_{k}=\pi\\}$. Then, the maximum must be
attained at one of the vertices of the polyhedron; that is, on those matrixes
$R$ such that one and only one entry by column is greater than zero, given
that $\pi_{a}>0$ for all $a\in\\{1,\dots,k_{0}\\}$. We denote by $R^{*}$ one
of these maximums (if there is more than one) and let

$\begin{split}\pi^{*}_{a}&\;=\;[R^{*}{\bf 1}_{k_{0}}]_{a}\,\qquad
a\in\\{1,\dots,k\\}\\\
\lambda^{*}_{ab}&\;=\;\frac{[R^{*}\tilde{\lambda}{R^{*^{T}}}]_{ab}}{[R^{*}{\bf
1}_{k_{0}}{\bf 1}_{k_{0}}^{T}R^{*^{T}}]_{ab}}\,,\qquad
a,b\in\\{1,\dots,k\\}\,.\end{split}$ (5.39)

Then

$\begin{split}\sup_{\begin{subarray}{c}R\colon\|R\|_{1}=1\\\ R^{T}{\bf
1}_{k}=\pi\end{subarray}}\;{1\over 2}\sum_{1\leq a,b\leq
k}[R\tilde{\lambda}R^{T}{\bf 1}_{k}]_{a}&[R\tilde{\lambda}R^{T}{\bf
1}_{k}]_{b}\;\varphi\biggl{(}\dfrac{[R\tilde{\lambda}R^{T}]_{ab}}{[R\tilde{\lambda}R^{T}{\bf
1}_{k}]_{a}[R\tilde{\lambda}R^{T}{\bf 1}_{k}]_{b}}\biggr{)}\\\ &\;=\;{1\over
2}\sum_{1\leq a,b\leq
k}\pi^{*}_{a}\pi^{*}_{b}[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}\;\varphi\biggl{(}\dfrac{\lambda^{*}_{ab}}{[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}}\biggr{)}\,.\end{split}$
(5.40)

This concludes the proof of Lemma 5.8. ∎

######  Lemma 5.9.

Assume $\tilde{\lambda}$ has no two proportional columns. Then for all
$k<k_{0}$ and $(\pi^{*},\lambda^{*})$ as in Lemma 5.8 we have that

$\begin{split}\sum_{1\leq a,b\leq
k_{0}}\pi_{a}\pi_{b}&[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{b}\;\varphi\Bigl{(}\frac{\tilde{\lambda}_{ab}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{b}}\Bigr{)}\\\
&-\sum_{1\leq a,b\leq
k}\pi^{*}_{a}\pi^{*}_{b}[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}\;\varphi\biggl{(}\dfrac{\lambda^{*}_{ab}}{[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}}\biggr{)}\;>\;0\,.\end{split}$
(5.41)

###### Proof.

First consider the case $k=k_{0}-1$. As $R^{*}$ has one and only one non-zero
entry in each column, we have that there is a surjective function
$h\colon[k_{0}]\to[k]$ connecting each community in $[k_{0}]$ (columns of
$R^{*}$) with is corresponding community in $[k]$ (line with non-zero entry).
Then for $k=k_{0}-1$, there are $k-1$ communities in $\\{1,\dots,k_{0}\\}$
that are mapped into $k-1$ communities in $\\{1,\dots,k\\}$ and two
communities in $\\{1,\dots,k_{0}\\}$ that are mapped into a single community
in $\\{1,\dots,k\\}$. Without loss of generality assume that the communities
$k_{0}-1$ and $k_{0}$ satisfy $h(k_{0}-1)=h(k_{0})=k=k_{0}-1$. Moreover, as
$R^{*T}{\bf 1}_{k}=\pi$ we must have that the non-zero entries are given by

$\begin{split}R_{aa}^{*}&=\pi_{a}\,,\qquad 1\leq a\leq k_{0}-1\\\
R_{(k_{0}-1)k_{0}}^{*}&=\pi_{k_{0}}\,.\end{split}$ (5.42)

Then the parameters $\pi^{*}$ and $\lambda^{*}$ defined in (5.39) are given by

$\begin{split}\pi_{a}^{*}&=\pi_{a}\,,\qquad 1\leq a\leq k_{0}-1\\\
\pi_{k_{0}-1}^{*}&=\pi_{k_{0}-1}+\pi_{k_{0}}\end{split}$

and

$\displaystyle\lambda_{ab}^{*}$ $\displaystyle=\tilde{\lambda}_{ab}\,,\qquad
1\leq a,b\leq k_{0}-2$ $\displaystyle\lambda_{a(k_{0}-1)}^{*}$
$\displaystyle=\frac{\pi_{k_{0}-1}\tilde{\lambda}_{a(k_{0}-1)}+\pi_{k_{0}}\tilde{\lambda}_{ak_{0}}}{\pi_{k_{0}-1}+\pi_{k_{0}}}\,,\qquad
1\leq l\leq k_{0}-2,$ $\displaystyle\lambda_{(k_{0}-1)(k_{0}-1)}^{*}$
$\displaystyle=\frac{\pi_{k_{0}-1}^{2}\tilde{\lambda}_{(k_{0}-1)(k_{0}-1)}+2\pi_{k_{0}-1}\pi_{k_{0}}\tilde{\lambda}_{(k_{0}-1)k_{0}}+\pi_{k_{0}}^{2}\tilde{\lambda}_{k_{0}k_{0}}}{\pi_{k_{0}-1}^{2}+2\pi_{k_{0}-1}\pi_{k_{0}}+\pi_{k_{0}}^{2}}\,.$

Observe that for all $1\leq a\leq k_{0}-1$ we have that
$[\lambda^{*}\pi^{*}]_{a}=[\tilde{\lambda}\pi]_{a}$ then for all $1\leq
a,b\leq k_{0}-2$

$\begin{split}\pi^{*}_{a}\pi^{*}_{b}[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}\;\varphi\biggl{(}\dfrac{\lambda^{*}_{ab}}{[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{b}}\biggr{)}\;=\;\pi_{a}\pi_{b}[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{b}\;\varphi\biggl{(}\dfrac{\tilde{\lambda}_{ab}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{b}}\biggr{)}\,.\end{split}$

On the other hand we have that

$[\lambda^{*}\pi^{*}]_{k_{0}-1}=\frac{\pi_{k_{0}-1}[\tilde{\lambda}\pi]_{k_{0}-1}+\pi_{k_{0}}[\tilde{\lambda}\pi]_{k_{0}}}{\pi_{k_{0}-1}+\pi_{k_{0}}}\,.$

Then for $1\leq a\leq k_{0}-2$ it follows, by the log-sum inequality, that

$\begin{split}\pi_{a}^{*}&\pi_{k_{0}-1}^{*}[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{k_{0}-1}\varphi\biggl{(}\dfrac{\lambda^{*}_{a(k_{0}-1)}}{[\lambda^{*}\pi^{*}]_{a}[\lambda^{*}\pi^{*}]_{k_{0}-1}}\biggr{)}\\\
&=\;\pi_{a}[\tilde{\lambda}\pi]_{a}(\pi_{k_{0}-1}[\tilde{\lambda}\pi]_{k_{0}-1}+\pi_{k_{0}}[\tilde{\lambda}\pi]_{k_{0}})\varphi\left(\frac{\pi_{k_{0}-1}\tilde{\lambda}_{a(k_{0}-1)}+\pi_{k_{0}}\tilde{\lambda}_{ak_{0}}}{[\tilde{\lambda}\pi]_{a}(\pi_{k_{0}-1}[\tilde{\lambda}\pi]_{k_{0}-1}+\pi_{k_{0}}[\tilde{\lambda}\pi]_{k_{0}})}\right)\\\
&=\;\pi_{a}(\pi_{k_{0}-1}\tilde{\lambda}_{a(k_{0}-1)}+\pi_{k_{0}}\tilde{\lambda}_{ak_{0}})\log\left(\frac{\pi_{a}(\pi_{k_{0}-1}\tilde{\lambda}_{a(k_{0}-1)}+\pi_{k_{0}}\tilde{\lambda}_{ak_{0}})}{\pi_{a}[\tilde{\lambda}\pi]_{a}(\pi_{k_{0}-1}[\tilde{\lambda}\pi]_{k_{0}-1}+\pi_{k_{0}}[\tilde{\lambda}\pi]_{k_{0}})}\right)\\\
&\leq\;\pi_{a}\pi_{k_{0}-1}\tilde{\lambda}_{a(k_{0}-1)}\log\biggl{(}\frac{\tilde{\lambda}_{a(k_{0}-1)}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{k_{0}-1}}\biggr{)}+\pi_{a}\pi_{k_{0}}\tilde{\lambda}_{ak_{0}}\log\biggl{(}\frac{\tilde{\lambda}_{ak_{0}}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{k_{0}}}\biggr{)}\\\
&=\;\pi_{a}\pi_{k_{0}-1}[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{k_{0}-1}\varphi\biggl{(}\frac{\tilde{\lambda}_{a(k_{0}-1)}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{k_{0}-1}}\biggr{)}+\pi_{a}\pi_{k_{0}}[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{k_{0}}\varphi\biggl{(}\frac{\tilde{\lambda}_{ak_{0}}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{k_{0}}}\biggr{)}\,.\end{split}$
(5.43)

Moreover, we have that the inequality must be strict unless

$\frac{\tilde{\lambda}_{a(k_{0}-1)}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{k_{0}-1}}\;=\;\frac{\tilde{\lambda}_{ak_{0}}}{[\tilde{\lambda}\pi]_{a}[\tilde{\lambda}\pi]_{k_{0}}}\qquad\text{for
all }a\leq k_{0}-2\,.$ (5.44)

On the other hand, for $a=k_{0}-1$ and $b=k_{0}-1$, also by the log-sum
inequality we have that

$\begin{split}&\pi_{k_{0}-1}^{*}\pi_{k_{0}-1}^{*}[\lambda^{*}\pi^{*}]_{k_{0}-1}[\lambda^{*}\pi^{*}]_{k_{0}-1}\varphi\biggl{(}\dfrac{\lambda^{*}_{(k_{0}-1)(k_{0}-1)}}{[\lambda^{*}\pi^{*}]_{k_{0}-1}[\lambda^{*}\pi^{*}]_{k_{0}-1}}\biggr{)}\\\
&=(\pi_{k_{0}-1}^{2}\tilde{\lambda}_{(k_{0}-1)(k_{0}-1)}+2\pi_{k_{0}-1}\pi_{k_{0}}\tilde{\lambda}_{(k_{0}-1)k_{0}}+\pi_{k_{0}}^{2}\tilde{\lambda}_{k_{0}k_{0}})\\\
&\qquad\qquad\times\log\biggl{(}\dfrac{\pi_{k_{0}-1}^{2}\tilde{\lambda}_{(k_{0}-1)(k_{0}-1)}+2\pi_{k_{0}-1}\pi_{k_{0}}\tilde{\lambda}_{(k_{0}-1)k_{0}}+\pi_{k_{0}}^{2}\tilde{\lambda}_{k_{0}k_{0}}}{\pi_{k_{0}-1}^{2}[\tilde{\lambda}\pi]_{k_{0}-1}^{2}+2\pi_{k_{0}-1}\pi_{k_{0}}[\tilde{\lambda}\pi]_{k_{0}-1}[\tilde{\lambda}\pi]_{k_{0}}+\pi_{k_{0}}^{2}[\tilde{\lambda}\pi]_{k_{0}}^{2}}\biggr{)}\\\
&\leq\;\pi_{k_{0}-1}^{2}\tilde{\lambda}_{(k_{0}-1)(k_{0}-1)}\log\Bigl{(}\frac{\tilde{\lambda}_{(k_{0}-1)(k_{0}-1)}}{[\tilde{\lambda}\pi]_{k_{0}-1}^{2}}\Bigr{)}+2\pi_{k_{0}-1}\pi_{k_{0}}\tilde{\lambda}_{(k_{0}-1)k_{0}}\log\Bigl{(}\frac{\tilde{\lambda}_{(k_{0}-1)k_{0}}}{[\tilde{\lambda}\pi]_{k_{0}-1}[\tilde{\lambda}\pi]_{k_{0}}}\Bigr{)}\\\
&\qquad+\pi_{k_{0}}^{2}\tilde{\lambda}_{k_{0}k_{0}}\log\Bigl{(}\frac{\tilde{\lambda}_{k_{0}k_{0}}}{[\tilde{\lambda}\pi]_{k_{0}}^{2}}\Bigr{)}\\\
&\;=\pi_{k_{0}-1}^{2}[\tilde{\lambda}\pi]_{k_{0}-1}^{2}\varphi\biggl{(}\frac{\tilde{\lambda}_{(k_{0}-1)(k_{0}-1)}}{[\tilde{\lambda}\pi]_{k_{0}-1}^{2}}\biggr{)}+2\pi_{k_{0}-1}\pi_{k_{0}}[\tilde{\lambda}\pi]_{k_{0}-1}[\tilde{\lambda}\pi]_{k_{0}}\varphi\biggl{(}\frac{\tilde{\lambda}_{(k_{0}-1)k_{0}}}{[\tilde{\lambda}\pi]_{k_{0}-1}[\tilde{\lambda}\pi]_{k_{0}}}\biggr{)}\\\
&\qquad+\pi_{k_{0}}^{2}[\tilde{\lambda}\pi]_{k_{0}}^{2}\varphi\biggl{(}\frac{\tilde{\lambda}_{k_{0}k_{0}}}{[\tilde{\lambda}\pi]_{k_{0}}^{2}}\biggr{)}\,,\end{split}$
(5.45)

with equality if and only if

$\frac{\tilde{\lambda}_{(k_{0}-1)(k_{0}-1)}}{[\tilde{\lambda}\pi]_{k_{0}-1}^{2}}\;=\;\frac{\tilde{\lambda}_{(k_{0}-1)k_{0}}}{[\tilde{\lambda}\pi]_{k_{0}-1}[\tilde{\lambda}\pi]_{k_{0}}}\;=\;\frac{\tilde{\lambda}_{k_{0}k_{0}}}{[\tilde{\lambda}\pi]_{k_{0}}^{2}}\,.$
(5.46)

From (5.44) and (5.46) we obtain that the inequality (5.41) must be strict
unless

$\tilde{\lambda}_{a(k_{0}-1)}\;=\;\frac{[\tilde{\lambda}\pi]_{k_{0}-1}}{[\tilde{\lambda}\pi]_{k_{0}}}\tilde{\lambda}_{ak_{0}}\qquad\text{for
all }a\leq k_{0}\,$ (5.47)

which is a contradiction with the hypothesis for the identifiability of
$k_{0}$. ∎