[SBM-consistency-supp.pdf]

and

# Consistent Bayesian Community Detection

Sheng<EMAIL_ADDRESS>[ Surya T.
<EMAIL_ADDRESS>[ Duke University  Department of
Statistical Science, Duke University,

###### Abstract

Stochastic Block Models (SBMs) are a fundamental tool for community detection
in network analysis. But little theoretical work exists on the statistical
performance of Bayesian SBMs, especially when the community count is unknown.
This paper studies a special class of SBMs whose community-wise connectivity
probability matrix is diagonally dominant, i.e., members of the same community
are more likely to connect with one another than with members from other
communities. The diagonal dominance constraint is embedded within an otherwise
weak prior, and, under mild regularity conditions, the resulting posterior
distribution is shown to concentrate on the true community count and
membership allocation as the network size grows to infinity. A reversible-jump
Markov Chain Monte Carlo posterior computation strategy is developed by
adapting the allocation sampler of [19]. Finite sample properties are examined
via simulation studies in which the proposed method offers competitive
estimation accuracy relative to existing methods under a variety of
challenging scenarios.

62F12,

62F15,

Bayesian inference,

stochastic block model,

diagonal dominance,

network analysis,

community detection,

###### keywords:

[class=MSC]

###### keywords:

##  1 Introduction

Community detection is the most basic yet central statistical problem in
network analysis. To determine the number of communities, various tests have
been constructed based on modularity [29], random matrix theory [4, 17], and
likelihood ratio [28]. Methods based on information criteria [25] and network
cross-validation [5, 18] have also been designed. In the Bayesian realm, a
stochastic block model (SBM) is often employed to jointly infer the number of
communities, the connectivity probability matrix, and the membership
assignment [22, 19, 8].

Despite clear empirical evidence of good statistical performance [19, 8],
theoretical guarantees on Bayesian SBMs are a rarity when the number of
communities is unknown. As the only exception, [8] show that the community
count may be consistently estimated under the restrictive assumptions of a
homogeneous SBM with at most three communities. It is unclear if their
calculations generalize to more realistic scenarios. It is also not clear if
Bayesian SBMs can consistently recover the true membership allocation.

We study a special class of SBMs whose community-wise connectivity probability
matrix is diagonally dominant. This special class offers a stronger encoding
of the notion of communities in networks in the sense that nodes within the
same community are strictly more likely to connect with each other than with
nodes from other communities. Crucially, the diagonal dominance condition
enables membership allocations to be fully retrieved from the node-wise
connectivity probabilities, as long as each community contains at least two
nodes. Of course, the node-wise connectivity probability matrix is estimated
from data with statistical error. But as long as it is sufficiently “close” to
the truth, it is still possible to precisely recover the membership allocation
and the community count.

For a Bayesian estimation of the diagonally-dominant SBM under a modified
Nowicki-Snijders prior [22], we show the posterior on the node-wise
connectivity matrix contracts to the truth in the sup-norm topology. Posterior
contraction under sup-norm is necessary to the identification strategy
detailed above. [13] establish near minimax optimal posterior contraction
rates in the $L_{2}$ norm for dense networks with the true number of
communities assumed known. However, posterior contraction in $L_{2}$ or other
norms that are weaker than the sup-norm do not grant the identification of the
number of communities or the membership assignment from node-wise connectivity
probabilities. Our sup-norm posterior contraction calculation applies the
Schwartz method [10, 11, 12]. The key observation is that the sup-norm is
dominated by the Hellinger distance in the special context of SBMs, so the
tests required by the Schwartz method exist.

The theoretical gains of the diagonally dominant SBMs come at the price of
losing conjugacy with respect to the original Nowicki-Snijders prior. But
posterior computation may be carried out with a reasonably efficient
reversible-jump Markov chain Monte Carlo (MCMC) algorithm based of the
allocation sampler in [19]. Results from extensive numerical studies show that
our Bayesian diagonally-dominant SBM offers comparable and competitive
statistical performance against various alternatives in estimating the
community count and membership assignment.

##  2 The Diagonally Dominant Stochastic Block Model

Suppose an $n\times n$ binary adjacency matrix $A$ is observed, with entry
$A_{ij}=1$ if node $i$ and node $j$ are connected and $A_{ij}=0$ otherwise.
The stochastic block model (SBM) assumes there are $K\in{\mathbb{Z}}_{+}$
communities among the $n$ nodes and the connection between nodes exclusively
depends on their community membership. The community assignment $Z$ partitions
nodes $\\{1,...,n\\}$ into $K$ non-empty groups and assigns each node with a
community label. Let the community-wise connectivity probability matrix be
$P\in[0,1]^{K\times K}$. Then,

$A_{ij}|Z\mathbin{\overset{ind}{\kern
0.0pt\leavevmode\resizebox{10.25664pt}{3.66875pt}{$\sim$}}}Ber({P_{{Z(i)}{Z(j)}}})\text{
for }1\leq i<j\leq n,$ (1)

and $P\left({{A_{ii}}=0|Z}\right)=1$ for $i\in\\{1,...,n\\}$, assuming no
self-loops. We denote the above SBM model as $SBM(Z,P,n,k)$. Due to its
simplicity and expressiveness, SBM and its variants are fundamental tools for
community detection [e.g., 15, 2, 23].

###  2.1 Bayesian SBM with conjugate priors

For Bayesian estimation of the SBM, [22] propose the following conjugate
prior: given $K$,

$\begin{split}{P_{ab}}&\mathbin{\overset{iid}{\kern
0.0pt\leavevmode\resizebox{8.46658pt}{3.66875pt}{$\sim$}}}U\left({0,1}\right),a,b=1,...,K\\\
Z_{i}&\mathbin{\overset{iid}{\kern
0.0pt\leavevmode\resizebox{8.46658pt}{3.66875pt}{$\sim$}}}MN(\pi),i=1,...,n\\\
\pi&\sim Dir\left(\alpha\right).\end{split}$ (2)

This prior is widely used and adapted to more complicated cases in the
Bayesian SBM literature [13, 27, 8, 19].

For the unknown $K$ case, to maintain conjugacy, it is natural to place a
Poisson prior on $K$ [19, 8]. With conjugacy, [19] marginalize out $P$ from
the posterior $\Pi_{n}(Z,K,P|A)$ and develop an efficient “allocation sampler”
to directly sample from $\Pi_{n}(Z,K|A)$; [8] adapt the idea of MFM sampler of
[20] to the SBM case: marginalize out $K$ from the posterior
$\Pi_{n}(Z,K,P|A)$, and develop a Gibbs sampler sampling from
$\Pi_{n}(Z,P|A)$.

###  2.2 Our proposal: diagonally dominant SBM

In this paper, we propose to modify the conjugate specification of Nowicki and
Snijders’ prior on the connectivity matrix $P$ by imposing a diagonal
dominance constraint. The constraint is imposed in two steps: first specify a
prior distribution for the diagonal entries of $P$, then conditional on the
diagonal entries, specify a prior distribution on the off-diagonal entries
such that the off-diagonal entries are strictly less than their corresponding
diagonal entries.

For instance, we specify the following prior:

$\begin{split}&{P_{aa}}|K,\delta\mathbin{\overset{iid}{\kern
0.0pt\leavevmode\resizebox{8.46658pt}{3.66875pt}{$\sim$}}}U(\delta,1],a\in\\{1,...,K\\},\\\
&{P_{ab}}|K,\delta,\\{P_{aa}\\}_{a\in\\{1,...,K\\}}\mathbin{\overset{ind}{\kern
0.0pt\leavevmode\resizebox{10.25664pt}{3.66875pt}{$\sim$}}}U(0,P_{aa}\wedge
P_{bb}-\delta),a<b\in\\{1,...,K\\},\\\ &\delta\propto{\rm log}(n)/n,\\\ &K\sim
Pois(1),\end{split}$ (3)

where the hyperparameter $\delta$ is chosen to be a deterministic sequence
that goes to 0 as the network size grows to infinity. Uniform distributions in
(3) are used for simplicity and can be replaced with other distributions.

In contrast to the Nowicki and Snijders’ priors, our prior specification
directly imposes conditional dependence between diagonal entries and off-
diagonal entries. The dependence matches the idea of “community” at the price
of losing conjugacy.

The modification is mainly for two reasons. Firstly, the prior constraint of
diagonal dominance offers a neat identification of the number of communities,
and allows us to consistently estimate the number of communities and
membership. (See more details in section 3.1.)

Secondly, the resulting posterior under the modified prior is more
interpretable. Though the prior specification following [22] is conjugate,
off-diagonal entries can be greater than diagonal entries under the prior,
that is, nodes can be more likely to be connected to nodes from other
communities than nodes from their own community. Such configurations violate
the idea of “community”. Consequently, posterior samples of connectivity
matrices can violate diagonal dominance and are hard to interprete within the
framework of SBM.

###  2.3 $L_{2}$ minimax rate

This paper studies a special sub-class of SBM. One may wonder if the
diagonally dominant (DD) SBM actually solves a simpler community detection
problem. To answer this question, we calculate the $L_{2}$ minimax rate of
estimation for DD-SBM and compare it with the minimax rates derived in [6].

Now, we define the parameter space of DD-SBM. DD-SBM has the following space
of connectivity matrix

${S_{k,\delta}}=\left\\{{P\in{{\left[{0,1}\right]}^{k\times
k}}:{P^{T}}=P,{P_{ii}}>\delta+\mathop{\mathop{\rm max}\nolimits}\limits_{j\neq
i}\left({{P_{ij}}}\right),i\in\\{1,...,k\\}}\right\\},$ (4)

where $\delta\in[0,1)$ is a constant. The key departure from the literature is
the diagonal dominance constraint: ${P_{ii}}>\delta+\mathop{\mathop{\rm
max}\nolimits}\limits_{j\neq i}\left({{P_{ij}}}\right)$, for all
$i\in\\{1,...,k\\}$. Under this constraint, between community connection
probabilities are less than within community connection probabilities by
$\delta$. The gap is inherited by the node-wise connectivity probability
matrix.

Further with the membership assignment $Z$, we can define the space for node-
wise connectivity probability matrix:

${\Theta_{k,\delta}}=\left\\{{T({ZPZ^{T}})\in[0,1]^{n\times n}:P\in
S_{k,\delta},Z\in{{\mathcal{Z}}_{n,k}}}\right\\},$ (5)

where ${\mathcal{Z}}_{n,k}$ denotes the collection of all possible assignment
of $n$ nodes into $k$ communities which have at least two elements, and
$T(M):=M-\mathop{\rm diag}\nolimits(M)$ for any square matrix $M$. The node-
wise connectivity probability matrix inherits the structural assumption of
diagonal dominance. The minimum community size assumption allows recovering
community membership from node-wise connectivity probability matrix. It is
worthwhile to emphasize that singleton communities are ruled out.

The following $L_{2}$ minimax result implies that DD-SBM estimation is as
difficult as the original SBM estimation problem, as long as the dominance gap
is shrinking at certain rate. In our calculation, the gap squared
($\delta^{2}$) is dominated by the “clustering rate” ${\rm log}(k)/n$ [6, 7,
16].

######  Proposition 1.

For any $k\in\\{1,..,n\\}$ and $\delta\precsim\sqrt{{\rm log}(k)/n}$,

$\inf\limits_{\hat{\theta}}\sup\limits_{\theta\in\Theta_{k,\delta}}{\mathbb{E}}\left[||\hat{\theta}-\theta||_{2}^{2}\right]\asymp\frac{k^{2}}{n^{2}}+\frac{{\rm
log}(k)}{n}.$ (6)

###### Proof.

The upper bound follows theorem 2.1 of [6] as the diagonally dominant
connectivity matrix space is a subset of the unconstrained connectivity matrix
space.

The lower bound follows the proof of theorem 2.2 of [6] but their construction
violates the diagonally dominant constraint. It turns out a diagonally
dominant version of their construction is available. For brevity, we only
highlight the differences from the proof in [6].

For the nonparametric rate, we construct the $Q^{\omega}$ matrix by
$Q^{\omega}_{ab}=Q^{\omega}_{ba}=\frac{1}{2}-\delta-\frac{c_{1}k}{n}\omega_{ab}$,
for $a>b\in\\{1,...,k\\}$ and $Q^{\omega}_{aa}=\frac{1}{2}$, for
$a\in\\{1,...,k\\}$. The rest of the proof for the nonparametric rate remains
the same.

For the clustering rate, we construct the $Q$ matrix with the following form
$\begin{bmatrix}D_{1}&B\\\ B^{T}&D_{2}\end{bmatrix}$, where
$D_{1}=\frac{1}{2}I_{k/2}$, $B$ follows the same construction of [6] except
that $B_{a}=\frac{1}{2}-\delta-\sqrt{\frac{c_{2}{\rm log}k}{n}}\omega_{a}$ for
$a\in\\{1,...,k/2\\}$, $D_{2}=(\frac{1}{2}-\delta-\sqrt{\frac{{\rm
log}k}{n}})1_{k/2}1^{T}_{k/2}+(\delta+\sqrt{\frac{{\rm log}k}{n}})I_{k/2}$. As
$\delta\precsim\sqrt{{\rm log}(k)/n}$, the KL divergence upper bound remains
the same. The rest of the proof for the clustering rate remains the same as
the entropy calculation and the volume argument are unaffected.

∎

##  3 Consistent Bayesian Community Detection

###  3.1 Identification Strategy

The first consequence of diagonal dominance is that the node-wise connectivity
probability matrix spaces of different ranks are non-overlapping. This
observation offers a neat partition of the parameter space by the number of
communities.

######  Lemma 3.1.

Suppose $k\neq k^{\prime}\in{\mathbb{N}}$, then
$\Theta_{k,\delta}\cap\Theta_{k^{\prime},\delta^{\prime}}=\emptyset$ for any
$\delta,\delta^{\prime}\geq 0$.

Secondly, with diagonal dominance, it is possible to exactly identify the
number of communities, the membership of every node and the community-wise
connectivity probability matrix from node-wise connectivity probability matrix
under mild conditions. A more rigorous statement is presented in Lemma 3.2.
The recovery is based on checking each node’s connectivity probabilities with
other nodes, as each node is connected with nodes from its own community with
the highest probability.

######  Lemma 3.2.

Suppose $P\in S_{k,\delta}$ for some constant $\delta>0$, $\theta=T(ZPZ^{T})$
for some $Z\in{\mathcal{Z}}_{n,k}$, $T^{-1}$ recovers both community
assignment $Z$ and connectivity matrix $P$ from $\theta$.

###### Proof.

Without loss of generality, assume the nodes are ordered by community and we
can write $Z=[{\bf{1}}_{n_{1}},...,{\bf{1}}_{n_{k}}]$ where $n_{j}$ denotes
the number of nodes in community $j$ and ${\bf{1}}_{n_{j}}$ is a $n\times 1$
vector with entries in the $j^{th}$ block being 1. Therefore, the off-diagonal
terms of $\theta$ are the off-diagonal terms of $ZP{Z^{T}}$.

Suppose we hope to pin down $i^{th}$ node’s community membership. We take
$i^{th}$ row of $\theta$ and it contains the connectivity probabilities of
node $i$ and all other nodes. As $Z\in{\mathcal{Z}}_{n,k}$ whose minimum
community size is two,
${\mathcal{C}}_{i}\equiv\\{j:\theta_{ij}=\mathop{\mathop{\rm
max}\nolimits}\limits_{\ell}\theta_{i\ell}\\}$ is exactly the set of node(s)
from the community of node $i$. If ${\mathcal{C}}_{i}$ contains node(s) from
other communities, then the connectivity probabilities of node $i$ with those
node(s) are cross-community which are strictly less than the within-community
connectity probabiilty of node $i$, contradicting the construction of
${\mathcal{C}}_{i}$. If ${\mathcal{C}}_{i}$ misses node(s) from the community
of node $i$, then the connectivity probabilities of node $i$ with those
node(s) are within-community which have to match the connectivity
probabilities of nodes in ${\mathcal{C}}_{i}$. Therefore, by enumerating the
above procedure for all rows of $\theta$, $Z$ is identified up to a
permutation of columns.

To recover $P$ from $\theta$, it suffices to use $Z$ and plug in corresponding
values from $\theta$.

∎

In practice, the exact knowledge of node-wise connectivity probability matrix
is not available. However, the precise recovery in Lemma 3.2 is possible with
the estimated node-wise connectivity probability matrix. This is formalized in
Lemma 3.3. We use sup-norm to characterize the accuracy of the knowledge of
node-wise connectivity probability matrix. For any node-wise connectivity
matrix $\theta^{0}$, there exists $Z_{0}$ and $P^{0}$ such that
$\theta^{0}=T(Z_{0}P^{0}Z_{0}^{T})$. Without loss of generality, we can fix
the column ordering of $Z_{0}$ so that $P^{0}$ is consequently defined.

######  Lemma 3.3.

Suppose ${\theta^{0}}=T(Z_{0}P^{0}Z_{0}^{T})$ for some
$Z_{0}\in{\mathcal{Z}}_{n,{k_{0}}}$, ${P^{0}}\in{S_{{k_{0}},\delta}}$ and
$\delta>0$. Then, $\\{\theta=T(ZPZ^{T}):||\theta-\theta^{0}||_{\infty}\leq
r,Z\in{\mathcal{Z}}_{n,k},P\in
S_{k,\delta}\\}=\\{T(Z_{0}PZ_{0}^{T}):||P-P^{0}||_{\infty}\leq
r,P\in{S_{k_{0},\delta}}\\}$ holds for all $r<\delta/2$.

###### Proof.

Pick any $\theta\in\\{\theta=T(ZPZ^{T}):||\theta-\theta^{0}||_{\infty}\leq
r,Z\in{\mathcal{Z}}_{n,k},P\in S_{k,\delta}\\}$, define
${\mathcal{C}}_{i}=\\{j:\theta_{ij}=\mathop{\mathop{\rm
max}\nolimits}\limits_{\ell}\theta_{i\ell}\\}$; similarly, for $\theta^{0}$,
define ${\mathcal{C}}_{i}^{0}=\\{j:\theta^{0}_{ij}=\mathop{\mathop{\rm
max}\nolimits}\limits_{\ell}\theta^{0}_{i\ell}\\}$. The statement is
equivalent to ${\mathcal{C}}_{i}={\mathcal{C}}_{i}^{0}$ for all
$i\in\\{1,...,n\\}$ and all $\theta$.

First, note for any $j\in{\mathcal{C}}^{0}_{i}$ and
$\ell\in\\{1,...,n\\}\backslash{\mathcal{C}}^{0}_{i}$,
${\theta_{ij}}-{\theta_{i\ell}}={\theta_{ij}}-\theta_{ij}^{0}+\theta_{ij}^{0}-\theta_{i\ell}^{0}+\theta_{i\ell}^{0}-{\theta_{i\ell}}>\delta-2r>0$.
That is, ${\mathcal{C}}^{0}_{i}$ identifies a set of nodes with higher
connectivity probabilities with node $i$ relative to nodes from
$\\{1,...,n\\}\backslash{\mathcal{C}}^{0}_{i}$. Recall ${\mathcal{C}}_{i}$ is
the collection of nodes with the highest connectivity probability. Then,
${\mathcal{C}}_{i}\subseteq{\mathcal{C}}_{i}^{0}$ for all $i\in\\{1,...,n\\}$.

If ${\mathcal{C}}_{i}^{0}$ contains nodes from at least two communities of
$\theta$, then there exist $j_{1},j_{2}\in{\mathcal{C}}^{0}_{i}$, such that
$|\theta_{ij_{1}}-\theta_{ij_{2}}|>\delta$ as $P\in S_{k,\delta}$. Note for
all $j_{1},j_{2}\in{\mathcal{C}}^{0}_{i}$,
$\theta_{ij_{1}}^{0}=\theta_{ij_{2}}^{0}$, then it follows
$|{\theta_{ij_{1}}}-{\theta_{ij_{2}}}|=|{\theta_{ij_{1}}}-\theta_{ij_{1}}^{0}+\theta_{ij_{1}}^{0}-\theta_{ij_{2}}^{0}+\theta_{ij_{2}}^{0}-{\theta_{ij_{2}}}|\leq|{\theta_{ij_{1}}}-\theta_{ij_{1}}^{0}|+|\theta_{ij_{2}}^{0}-{\theta_{ij_{2}}}|\leq
2r<\delta$. Then, the contradiction implies
${\mathcal{C}}_{i}={\mathcal{C}}_{i}^{0}$ for all $i$. As $\theta$ is
arbitrary, ${\mathcal{C}}_{i}={\mathcal{C}}_{i}^{0}$ for all
$i\in\\{1,...,n\\}$ and for all $\theta$. ∎

###  3.2 Posterior Concentration

To study the asymptotic behavior of the diagonally dominated SBM, we make the
following assumptions on the prior specification. The prior specification in
Assumption 1 and 2 is indexed by $n$, the number of nodes in the network , and
can be interpreted as a sequence of prior distributions.

######  Assumption 1.

(Prior mass on the parameter space) There exists $\bar{\delta}\in(0,1)$ such
that for all $0<\delta<\bar{\delta}$ and $k>1$,
${\Pi_{n}}\left({{S_{k,\delta}}}|K=k\right)\geq 1-{e^{-{n^{2}}{\delta}}}$.

Assumption 1 requires that the prior specification is essentially diagonally
dominant. Under Nowicki and Snijders’ prior, conditional on $k$ communities,
the prior probability of diagonal dominance is $1/k^{k}$. Therefore, Nowicki
and Snijders’ prior does not satisfy Assumption 1.

######  Assumption 2.

(Prior decay rates)

  1. 1.

(Prior on $P$ conditional on $K$ and $\delta$)

For $a\in\\{1,...,k\\}$, diagonal entries $\\{P_{aa}\\}$ are independent with
prior density $\pi_{n}(P_{aa}|K,\delta)\geq e^{-C{\rm
log}(n)P_{aa}}1_{\\{P_{aa}\in(\delta,1)\\}}$ for some positive constant $C$
independent of $a\in\\{1,...,k\\}$.

For $a<b\in\\{1,...,k\\}$, off-diagonal entries
$\\{P_{ab}\\}_{a\in\\{1,...,k\\}}$ are conditionally independent on diagonal
entries with conditional prior density

${\pi_{n}}\left({P_{ab}}|\\{P_{aa}\\}_{a\in\\{1,...,k\\}},\delta,K\right)\geq
e^{-C{\rm
log}(n)({P_{aa}}\wedge{P_{bb}})}1_{\\{P_{ab}\in[0,{P_{aa}}\wedge{P_{bb}}-\delta]\\}}$
(7)

for some positive constant $C$ independent of $a,b\in\\{1,...,k\\}$.

  2. 2.

(Prior on $Z$ conditional on $K$)

The prior on the membership assignment $Z$ satisfies
${\Pi_{n}}\left({Z=z|K=k}\right)\geq{e^{-Cn{\rm log}(k)}}$ for all
$z\in{\mathcal{Z}}_{n,k}$ and for some universal positive constant $C$.

  3. 3.

(Prior on $K$)

The support of $K$ is $[K_{n}]$ with $K_{n}\precsim\sqrt{n}$. For
$k\in[K_{n}]$, the prior on $K$ satisfies ${\Pi_{n}}\left({K=k}\right)\geq
e^{-Ck{\rm log}(k)}$ for some universal positive constant $C$.

Assumption 2 makes more specific decay rate assumptions on the prior mass of
connectivity matrix $P$, the assignment $Z$, and the number of communities
$K$. The rate assumption of the prior on $P$ given $K$ and $\delta$
essentially requires the prior density on $P$ is lower bounded away from 0.
For instance, the uniform prior on $P$ and the Poisson prior on $K$ in (3)
satisfy Assumption 2.

######  Theorem 3.4.

Suppose adjacency matrix $A\sim SBM(Z_{0},P^{0},n,k_{0})$, let
$\theta^{0}=T(Z_{0}P^{0}Z_{0}^{T})$, $P^{0}\in\Theta_{k_{0},\delta_{0}}$ for
some $k_{0}\precsim\sqrt{n}$ and $\delta_{0}>0$, and the number of zero and
one entries of $\theta^{0}$ is at most $O(n^{2}\varepsilon_{n})$ where
$\varepsilon_{n}^{2}\asymp\frac{{\rm log}(k_{0})}{n}$. The prior $\Pi_{n}$
satisfies Assumption 1 and 2. Then, for all sufficiently large $M$,

${{\mathbb{P}}_{0,n}}{\Pi_{n}}\left({\theta:||\theta-\theta^{0}||_{\infty}\geq
M\varepsilon_{n}}|A\right)\to 0.$

The proof of Theorem 3.4 follows Schwartz method [26, 3, 9, 11]. Details of
the proof are deferred to Section 3.3.

Though exact $L_{\infty}$ minimax rates of SBM or DD SBM are unknown,
$L_{\infty}$ minimax rates are lower bounded by $L_{2}$ minimax rates. The
$L_{2}$ minimax rate calculation of DD SBM in Proposition 1 can be useful for
judging the sharpness of the posterior contraction rate in Theorem 3.4. As we
assume $k_{0}\precsim\sqrt{n}$, the posterior contraction rate in
$||\cdot||_{\infty}$ matches the $L_{2}$ minimax rates in Proposition 1, and
the posterior contraction rate is minimax-optimal.

With Theorem 3.4 and Lemma 3.3, we can establish the consistent estimation of
the true number of communties and true membership assignment. The main result
is summarized as follows.

######  Theorem 3.5.

Under the same assumptions of Theorem 3.4,

${{\mathbb{P}}_{0,n}}\left[{{\Pi_{n}}\left(\\{K=k_{0}\\}\cap\\{Z={Z_{0}}\\}|A\right)}\right]\to
1.$

###### Proof.

In light of Theorem 3.4, the posterior mass is essentially on
$\\{\theta:||\theta-\theta_{n}^{0}|{|_{\infty}}\leq{\varepsilon_{n}}\\}$.
Therefore, we leverage Lemma 3.3 to identify $k_{0}$ and $Z_{0}$ on the set.

Define $E_{0}=\\{K=k_{0}\\}\cap\\{Z=Z_{0}\\}$. Note the decomposition

$E^{c}_{0}=\left(E^{c}_{0}\cap\\{||\theta-\theta^{0}|{|_{\infty}}\leq{\varepsilon_{n}}\\}\right)\cup\left(E^{c}_{0}\cap\\{||\theta-\theta^{0}|{|_{\infty}}>{\varepsilon_{n}}\\}\right)$

for some $\varepsilon_{n}$, then

${\Pi_{n}}\left({E^{c}_{0}|A}\right)\leq{\Pi_{n}}\left({E^{c}_{0},||\theta-\theta^{0}|{|_{\infty}}\leq{\varepsilon_{n}}|A}\right)+{\Pi_{n}}\left({||\theta-\theta^{0}|{|_{\infty}}>{\varepsilon_{n}}|A}\right)$
(8)

where $\varepsilon_{n}\to 0$ is chosen to match the posterior contraction rate
in sup-norm.

Then, the posterior probability of choosing wrong number of communities or
wrong membership assignment can be upper bounded via the identification
assumption and convergence of the posterior distribution of $\theta$. For the
first part of Equation (8), the $\delta$ gap assumption of $\theta^{0}$
satisfies $\delta_{0}\succsim\varepsilon_{n}$. Then, by Lemma 3.3, for all
sufficiently small $\varepsilon_{n}$,
$\\{||\theta-\theta^{0}|{|_{\infty}}\leq{\varepsilon_{n}}\\}$ is the same as
its $Z_{0}$ slice where the implied number of communities is $k_{0}$.

For the second part, Theorem 3.4 implies
${\mathbb{P}}_{0}[{\Pi_{n}}\left({||\theta-\theta^{0}|{|_{\infty}}>{\varepsilon_{n}}|A}\right)]\to
0$.

∎

###  3.3 Proof of Theorem 3.4

Pioneered by [26] and further developed by [3, 9, 11], Schwartz method is the
major tool to study posterior concentration properties of Bayesian procedures
as sample size grows to infinity [12]. Schwartz method seeks for two
sufficient conditions to guarantee posterior concentration: the existence of
certain tests and prior mass condition. The existence of certain tests often
reduces to the construction of certain sieves and an entropy condition
associated with the sieve, if the metric under which we wish to obtain
posterior contraction is dominated by Hellinger distance. The prior mass
condition requires sufficient amount of prior mass on some KL neighborhood
near the truth.

Establishing convergence in $||\cdot||_{\infty}$ via the general framework of
Schwartz method requires $||\cdot||_{\infty}$ to be dominated by Hellinger
distance. In general, $||\cdot||_{\infty}$ is (weakly) stronger than Hellinger
distance and not dominated by Hellinger distance. However, in the special case
of SBM, the parameter space is constrained and the desired dominance holds.
This observation is shown in Lemma 3.6.

######  Lemma 3.6.

Suppose $A_{ij}|\theta\mathbin{\overset{IND}{\kern
0.0pt\leavevmode\resizebox{16.00371pt}{3.66875pt}{$\sim$}}}Ber(\theta_{ij})$
for $i<j$ and $i,j\in\\{1,...,n\\}$, then $||\cdot||_{\infty}$ is dominated by
Hellinger distance: $||{\theta^{0}}-{\theta^{1}}|{|_{\infty}}\leq
2H\left({{\mathbb{P}}_{\theta^{0}},{\mathbb{P}}_{\theta^{1}}}\right)$.

With the norm dominance, the existence of certain tests reduces to construct a
suitable sieve which charges sufficient prior mass and whose metric entropy is
under control. In our proof, the sieve is constructed as the set of all well
separated node-wise connectivity probability matrices:
$\bigcup\nolimits_{k=1}^{{K_{n}}}{{\Theta_{k,\delta_{n}}}}$ for some carefully
chosen $\delta_{n}$ and $K_{n}$.

In light of Lemma 3.1, the metric entropy of the sieve can be neatly bounded.
The entropy calculation is summarized in Lemma 3.7.

######  Lemma 3.7.

Suppose $\varepsilon_{n}\to 0$ as $n\to\infty$, and
$\varepsilon_{n}\precsim\delta_{n}$, then metric entropy satisfies

${\rm
log}N\left({{\varepsilon_{n}},\bigcup\nolimits_{k=1}^{{K_{n}}}{{\Theta_{k,\delta_{n}}}},||\cdot|{|_{\infty}}}\right)\precsim\left({n+1}\right){\rm
log}{K_{n}}+\frac{1}{2}{K_{n}}\left({{K_{n}}+1}\right){\rm
log}\left({1/{\varepsilon_{n}}}\right).$ (9)

The prior mass condition in terms of KL divergence can be reduced to a prior
mass condition in terms of $||\cdot||_{\infty}$ norm. This observation is
summarized in Lemma 3.8.

######  Lemma 3.8.

The observation model is $A_{ij}|\theta^{0}\mathbin{\overset{IND}{\kern
0.0pt\leavevmode\resizebox{16.00371pt}{3.66875pt}{$\sim$}}}Ber(\theta^{0}_{ij})$
for $i<j$ and $i,j\in\\{1,...,n\\}$. Suppose $C_{0}={{\mathop{\mathop{\rm
min}\nolimits}\nolimits_{i<j:0<\theta_{ij}^{0}<1}\theta_{ij}^{0}\left({1-\theta_{ij}^{0}}\right)}}>0$,
and the number of zero and one entries of ${\theta^{0}}$ is less than
$O(n^{2}\varepsilon_{n})$ for some $\varepsilon_{n}\to 0$ such that
$n^{2}\varepsilon_{n}\to\infty$. If
$||{\theta}-\theta^{0}|{|_{\infty}}\leq\varepsilon_{n}$, then
$KL\left({{{\mathbb{P}}_{{\theta^{0}}}},{{\mathbb{P}}_{\theta}}}\right)\precsim
C_{0}^{-1}{n^{2}}\varepsilon_{n}^{2}$, and
${V_{2,0}}\left({{{\mathbb{P}}_{{\theta^{0}}}},{{\mathbb{P}}_{\theta}}}\right)\precsim
C_{0}^{-1}{n^{2}}\varepsilon_{n}^{2}$.

Lemma 3.8 simplifies the prior mass condition to element-wise probability
calculation. Immediately with Assumption 2, we obtain the following prior mass
calculation.

######  Lemma 3.9 (prior mass condition).

Suppose $P^{0}\in S_{k_{0},\delta_{0}}$ for some $k_{0}\precsim\sqrt{n}$ and
constant $\delta_{0}\in(0,1)$, and $\varepsilon_{n}^{2}\asymp{\rm
log}(k_{0})/n$, then under Assumption 2, there exists a constant $C$ only
dependent on $P^{0}$ and $C_{0}$ such that

${\Pi_{n}}\left({P:||P-{P^{0}}|{|_{\infty}}<C_{0}{\varepsilon_{n}}};Z=Z_{0};K=k_{0}|\delta\right)\geq
e^{-Cn^{2}\varepsilon_{n}^{2}}$ (10)

holds for all sufficiently large $n$.

With the above preparation, the proof of Theorem 3.4 is as follows. The
structure of the proof follows [11].

###### Proof.

We first verify prior mass condition. By Lemma 3.8, the set

$\left\\{{\theta\in\bigcup\nolimits_{k=1}^{{K_{n}}}{{\Theta_{k,0}}}:KL\left({{{\mathbb{P}}_{{\theta_{n}^{0}}}},{{\mathbb{P}}_{\theta}}}\right)<n^{2}\varepsilon_{n}^{2},{V_{2,0}}\left({{{\mathbb{P}}_{{\theta_{n}^{0}}}},{{\mathbb{P}}_{\theta}}}\right)<n^{2}\varepsilon_{n}^{2}}\right\\}$

contains a sup-norm ball
$\left\\{{\theta\in\bigcup\nolimits_{k=1}^{{K_{n}}}{{\Theta_{k,0}}}:||\theta-{\theta_{n}^{0}}|{|_{\infty}}<C_{0}{\varepsilon_{n}}}\right\\}$
for some constant $C_{0}$ only dependent on $\theta^{0}$. Choose
$1\succ{\tau_{n}}\succ{\varepsilon_{n}}$, the sup-norm ball further contains
the following sup-norm ball
$\left\\{{\theta\in{{\Theta_{k_{0},\tau_{n}}}}:||\theta-{\theta_{n}^{0}}|{|_{\infty}}<C_{0}{\varepsilon_{n}}}\right\\}$.
By Lemma 3.3, the sup-norm ball is essentially its $Z_{0}$ slice which reduces
to

${\Pi_{n}}\left({P\in
S_{k_{0},\tau_{n}}:||P-{P^{0}}|{|_{\infty}}<C{\varepsilon_{n}}};Z=Z_{0};K=k_{0}\right).$

By Lemma 3.9, the prior mass is further lower bounded by
$e^{-Cn^{2}\varepsilon_{n}^{2}}$ for some constant $C$ only dependent on
$P^{0}$ and $C_{0}$.

Next, we check the existence of tests. The existence of tests boils down to
metric entropy condition and prior mass condition of the sieve. The sieve is
constructed as $\bigcup\nolimits_{k=1}^{{K_{n}}}{{\Theta_{k,\delta_{n}}}}$
with $1\succ{\delta_{n}}\succsim{\varepsilon_{n}^{2}}$.

Metric entropy condition of the sieve requires the metric entropy is upper
bounded by $Cn^{2}\varepsilon_{n}^{2}$. Clearly, this is satisfied by Lemma
3.7.

It is left to show the prior mass on the sieve. Note
${\Pi_{n}}\left({{{\left({\bigcup\nolimits_{k=1}^{{K_{n}}}{\Theta_{k,{\delta_{n}}}}}\right)}^{c}}}\right)\leq{\Pi_{n}}\left({\Theta_{K_{n},{\delta_{n}}}^{c}}\right)={\Pi_{n}}\left({\Theta_{K_{n},{\delta_{n}}}^{c}|K=K_{n}}\right)\Pi_{n}(K=K_{n})$,
then the prior mass on the sieve is also satisfied by a union bound:

$\begin{array}[]{lll}{\Pi_{n}}\left({\Theta_{k,{\delta_{n}}}^{c}|K=k}\right)&\leq&\sum\nolimits_{z\in{{\mathcal{Z}}_{n,k}}}{{\Pi_{n}}\left({\Theta_{k,{\delta_{n}}}^{c}|Z=z,K=k}\right){\Pi_{n}}\left({Z=z|K=k}\right)}\\\
&\leq&\mathop{\mathop{\rm
max}\nolimits}\nolimits_{z\in{{\mathcal{Z}}_{n,k}}}{\Pi_{n}}\left({\Theta_{k,{\delta_{n}}}^{c}|Z=z,K=k}\right)\\\
&=&\mathop{\mathop{\rm
max}\nolimits}\nolimits_{z\in{{\mathcal{Z}}_{n,k}}}{\Pi_{n}}\left({T(zPz^{T}):P\in
S_{k,{\delta_{n}}}^{c}|Z=z,K=k}\right)\\\
&\leq&{\Pi_{n}}\left({S_{k,{\delta_{n}}}^{c}|K=k}\right)\\\
&\leq&e^{-n^{2}\delta_{n}}\\\
&\precsim&{e^{-C{n^{2}}\varepsilon_{n}^{2}}}\end{array}$

for some constant $C$.

∎

##  4 Posterior Sampler and Inference

###  4.1 Reversible-jump MCMC algorithm

Under the diagonally dominant prior (3), the posterior distribution is as
follows,

${\Pi_{n}}\left({Z,K,P|A}\right)\propto\Pi\left({A|Z,P}\right){\Pi_{n}}\left({P|Z}\right){\Pi_{n}}\left({Z|K}\right){\Pi_{n}}\left(K\right)$
(11)

with

$\begin{array}[]{lll}\Pi\left({A|Z,P}\right)&=&\prod\nolimits_{1\leq a\leq
b\leq
K}{P_{ab}^{{O_{ab}}\left(Z\right)}{{\left({1-{P_{ab}}}\right)}^{{n_{ab}}\left(Z\right)-{O_{ab}}\left(Z\right)}}}\\\
{\Pi_{n}}\left({P|Z,K,\delta_{n}}\right)&=&\prod\nolimits_{1\leq a<b\leq
K}{\frac{{{1_{\left({0\leq{P_{ab}}\leq\left({{P_{aa}}\wedge{P_{bb}}}\right)-{\delta_{n}}}\right)}}}}{{\left({{P_{aa}}\wedge{P_{bb}}}\right)-{\delta_{n}}}}}\\\
{\Pi_{n}}\left({Z|K}\right)&=&\frac{{\Gamma\left(K\right)}}{{\Gamma\left(n+K\right)}}\prod\nolimits_{1\leq
c\leq K}{\Gamma\left({{n_{c}}\left(Z\right)}+1\right)}\\\
{\Pi_{n}}\left(K\right)&\propto&\frac{1}{{K!}}{1_{1\leq
K\leq{K_{n}}}}.\end{array}$

For comparison, the Nowicki and Snijders’ prior is conjugate and the
community-wise connectivity probability matrix $P$ can be marginalized out in
the posterior distribution. Therefore, posterior inference on $K$ is directly
based on posterior draws from $\Pi_{n}(Z,K|A)$. However, the truncated Nowicki
and Snijders’ prior loses conjugacy. Our posterior inference needs to sample
from $\Pi_{n}(P,Z,K|A)$.

We propose an Metropolis-Hastings algorithm to sample from (11). The proposal
$(Z^{*},K^{*},P^{*})$ is accepted with probability

$\mathop{\rm
min}\nolimits\left(1,\frac{{\Pi_{n}}\left({Z^{*},K^{*},P^{*}|A}\right)}{{\Pi_{n}}\left({Z,K,P|A}\right)}\frac{\Pi_{prop}(Z,K,P|Z^{*},K^{*},P^{*})}{\Pi_{prop}(Z^{*},K^{*},P^{*}|Z,K,P)}\right)$
(12)

where $\Pi_{prop}$ denotes the density function of the proposal distribution
and $(Z,K,P)$ denotes the current iteration.

To be specific, the proposal distribution is adapted from the allocation
sampler developed in [19]. For each iteration of the sampler, the proposal
distribution first sample $(Z,K)$ in the spirit of the allocation sampler,
then sample $P$ given $(Z,K)$. The proposal distribution is decomposed into
two parts: conditional on the previous draw $(P,Z,K)$ and data matrix $A$,

${\Pi_{prop}}\left({{Z^{*}},{K^{*}},{P^{*}}|Z,K,P,A}\right)\propto{\Pi_{prop}}\left({{P^{*}}|{Z^{*}},A}\right){\Pi_{prop}}\left({{Z^{*}},{K^{*}}|Z,K,P,A}\right)$

where $P_{ab}^{*}|{Z^{*}},A\mathbin{\overset{ind}{\kern
0.0pt\leavevmode\resizebox{10.25664pt}{3.66875pt}{$\sim$}}}Beta\left({{O_{ab}^{*}}+1,{n_{ab}^{*}}-{O_{ab}^{*}}+1}\right)$
with $O_{ab}^{*}\equiv O_{ab}(Z^{*})$ and $n_{ab}^{*}\equiv n_{ab}(Z^{*})$,
and $(Z^{*},K^{*})|(Z,K,P,A)$ are simulated in the spirit of the allocation
sampler developed in [19, 21].

The proposal distribution of $(Z^{*},K^{*})|(Z,K,P,A)$ follows the allocation
sampler of [19] but it is different in the way that connectivity probability
matrix $P$ is involved and used for likelihood evaluation. In contrast, the
allocation sampler of [19] explores the $(Z,K)$ space with $P$ marginalized
out. Details of the posterior sampler are in the Supplement.

The expectation of the proposal distribution $\Pi_{prop}(P^{*}|(Z^{*},A))$ is
the ordinary block constant least squares estimator which is widely used to
estimate the connectivity probability matrix in the literature [see 6, 16, 27,
for instance]. As the proposal density matches the likelihood component
$\Pi(A|P^{*},Z^{*})$, the acceptance rate is a product of prior density ratios
and proposal density ratios.

###  4.2 Posterior Inference

Under the 0-1 loss function $\ell(k,k_{0})=1_{k=k_{0}}$, the Bayes estimate of
$K$ is its posterior mode. As in the Metropolis-Hastings sampler, $K$
communities may contain empty communities, we compute the effective number of
communities based on samples of $Z$.

The community assignment is identified up to a label switching. In our matrix
formulation, the assignment $Z$ is identified up to a column permutation. That
is, $ZZ^{T}$ is invariant to column permutations. If the $(i,j)^{th}$ entry of
$ZZ^{T}$ is 1, node $i$ and node $j$ are classified into the same community by
$Z$. In addition, the node-wise connectivity $\theta$ is also identified
without relabelling concerns. With the 0-1 loss function
$\ell(Z,Z_{0})=1_{({ZZ^{T}=Z_{0}Z_{0}^{T}})}$, Bayes estimate of $Z$ is its
posterior mode. To pin down the posterior mode of $Z$, we can find the
posterior mode of $ZZ^{T}$ and the corresponding $Z$ is the posterior mode of
$Z$.

##  5 Numerical Experiments

Section 3 presents asymptotic properties of Bayesian SBM with diagonally
dominant priors which is henceforth abbreviated as “DD-SBM”. This section
assesses finite sample properties of DD-SBM under various settings.

###  5.1 Simulation design

We perform simulation studies for different configurations of the number of
communities, network size, and overall sparsity of connectivity. In
particular, we choose
$(k_{0},n,\rho)\in\\{3,5,7\\}\times\\{50,75\\}\times\\{\frac{1}{2},1\\}$, and
for each $(k_{0},n,\rho)$ configuration, 100 networks are generated from
$SBM(Z_{0},\rho P^{0},n,k_{0})$.

To control the source of variation in the synthetic networks, the 100 networks
share the same community structure $Z_{0}$ where nodes are deterministically
and uniformly assigned to $k_{0}$ communities; the 100 networks also share the
same connectivity matrix $\rho P^{0}$. The randomness in the 100 synthetic
networks is only from the stochastic generation of Bernoulli trials of
$SBM(Z_{0},\rho P^{0},n,k_{0})$.

We choose the following cases for $P^{0}$.

  * •

Case 1: $P^{0}=0.6\times I_{k_{0}}+0.2\times 1_{k_{0}}1_{k_{0}}^{T}$,

  * •

Case 2: $P^{0}=0.2\times I_{k_{0}}+0.6\times 1_{k_{0}}1_{k_{0}}^{T}$,

  * •

Case 3: $P^{0}=0.4\times I_{k_{0}}+0.4\times 1_{k_{0}}1_{k_{0}}^{T}$,

  * •

Case 4: $P^{0}=0.2\times I_{k_{0}}+0.2\times 1_{k_{0}}1_{k_{0}}^{T}+0.4\times
1_{k_{0},\lceil{k_{0}/2\rceil{}}}1_{k_{0},\lceil{k_{0}/2\rceil{}}}^{T}$,

where $I_{k}$ denotes identity matrix of rank $k$, $1_{k}$ denotes the
$k-$dimensional vector of ones, and $1_{n,k}$ denotes the $n-$dimensional
vector with the first $k$ elements being 1 and the rest $(n-k)$ elements being
0.

In the four cases, within community connectivity probabilities are all 0.8.
For simplicity, the between community connectivity probabilities are the same
for Case 1-3; in Case 1, cross community connectivity is weak; in Case 2,
cross community connectivity is strong; and in Case 3, cross community
connectivity is medium. Case 4 combines the structure of Case 1 and Case 3 and
half of the cross community connectivity is strong.

The reasons for choosing $n\in\\{50,75\\}$ are as follows. Firstly, many
networks in natural and social sciences are often of moderate size. Secondly,
asymptotically consistent estimators can perform poorly when sample size is
moderate. It is more informative to compare methods for networks of moderate
size than that for networks with thousands of nodes. Thirdly, MCMC algorithms
are computationally expensive, and the computation bottleneck prevents us from
networks with more than thousands of nodes.

As the number of parameters in the SBM grows in the order of $O(k^{2}_{0})$,
the difficulty of community detection increases as $k_{0}$ grows. The case of
$k_{0}=7$ imitates the situation of many communities, while the cases of
$k_{0}\in\\{3,5\\}$ imitate networks with moderately many communties.

###  5.2 Simulation results

For comparison, we also implement Bayesian SBM with the Nowicki and Snijders’
prior [21, 8], composite likelihood BIC method [25], and network cross-
validation [5]. Two posterior samplers for the Nowicki and Snijders’ prior are
available in the literature: the allocation sampler of [19], and the MFM
adapted MCMC algorithm of [8]. We use the code provided in the supplementary
materials of [8] and choose default values for the hyperparameters in their
algorithm. The Bayesian SBM of [8, 19] is henceforth denoted as “c-SBM”
(Bayesian SBM with conjugate priors). [25] propose composite likelihood BIC to
choose the number of communities, and this method is henceforth denoted as
“CLBIC”. [5] design a cross-validation strategy to choose the number of
communities for SBM, and it is henceforth denoted as “NCV”.

|  |  | Case 1 | Case 2 | Case 3 | Case 4
---|---|---|---|---|---|---
$k_{0}$ | $n$ | Method | $\rho=\mbox{\tiny$\frac{1}{2}$}$ | $\rho=1$ | $\rho=\mbox{\tiny$\frac{1}{2}$}$ | $\rho=1$ | $\rho=\mbox{\tiny$\frac{1}{2}$}$ | $\rho=1$ | $\rho=\mbox{\tiny$\frac{1}{2}$}$ | $\rho=1$
$3$ | $50$ | DD-SBM | $1.8_{\mbox{\tiny(1.3)}}$ | $1.9_{\mbox{\tiny(1.9)}}$ | $1.8_{\mbox{\tiny(-1.6)}}$ | $1.3_{\mbox{\tiny(0.0)}}$ | $0.3_{\mbox{\tiny(0.1)}}$ | $2.0_{\mbox{\tiny(-1.9)}}$ | $0.3_{\mbox{\tiny(0.1)}}$ | $1.0_{\mbox{\tiny(-0.6)}}$
c-SBM | $0.8_{\mbox{\tiny(-0.5)}}$ | $1.9_{\mbox{\tiny(-1.9)}}$ | $1.9_{\mbox{\tiny(-1.8)}}$ | $1.0_{\mbox{\tiny(-1.0)}}$ | $0.2_{\mbox{\tiny(-0.0)}}$ | $1.9_{\mbox{\tiny(-1.9)}}$ | $0.6_{\mbox{\tiny(-0.1)}}$ | $0.9_{\mbox{\tiny(-0.8)}}$
CLBIC | $0.5_{\mbox{\tiny(-0.2)}}$ | $1.3_{\mbox{\tiny(-1.2)}}$ | $1.3_{\mbox{\tiny(-1.2)}}$ | $1.3_{\mbox{\tiny(-1.1)}}$ | $0.0_{\mbox{\tiny(0.0)}}$ | $1.4_{\mbox{\tiny(-1.3)}}$ | $0.6_{\mbox{\tiny(-0.3)}}$ | $1.0_{\mbox{\tiny(-0.9)}}$
NCV | $0.9_{\mbox{\tiny(-0.6)}}$ | $2.0_{\mbox{\tiny(-2.0)}}$ | $2.0_{\mbox{\tiny(-2.0)}}$ | $2.0_{\mbox{\tiny(-2.0)}}$ | $0.0_{\mbox{\tiny(0.0)}}$ | $2.0_{\mbox{\tiny(-2.0)}}$ | $0.9_{\mbox{\tiny(-0.3)}}$ | $0.9_{\mbox{\tiny(-0.8)}}$
$75$ | DD-SBM | $1.0_{\mbox{\tiny(0.5)}}$ | $2.0_{\mbox{\tiny(-1.9)}}$ | $1.6_{\mbox{\tiny(-1.1)}}$ | $1.1_{\mbox{\tiny(-0.6)}}$ | $0.1_{\mbox{\tiny(0.0)}}$ | $1.9_{\mbox{\tiny(-1.9)}}$ | $0.2_{\mbox{\tiny(0.0)}}$ | $0.9_{\mbox{\tiny(-0.7)}}$
c-SBM | $0.5_{\mbox{\tiny(-0.1)}}$ | $2.0_{\mbox{\tiny(-1.9)}}$ | $1.6_{\mbox{\tiny(-1.3)}}$ | $1.0_{\mbox{\tiny(-1.0)}}$ | $0.3_{\mbox{\tiny(0.0)}}$ | $1.8_{\mbox{\tiny(-1.6)}}$ | $0.4_{\mbox{\tiny(0.0)}}$ | $0.9_{\mbox{\tiny(-0.8)}}$
CLBIC | $0.0_{\mbox{\tiny(0.0)}}$ | $1.0_{\mbox{\tiny(-1.0)}}$ | $0.9_{\mbox{\tiny(-0.8)}}$ | $1.0_{\mbox{\tiny(-0.9)}}$ | $0.0_{\mbox{\tiny(0.0)}}$ | $1.0_{\mbox{\tiny(-1.0)}}$ | $0.0_{\mbox{\tiny(0.0)}}$ | $1.0_{\mbox{\tiny(-0.9)}}$
NCV | $0.1_{\mbox{\tiny(0.0)}}$ | $2.0_{\mbox{\tiny(-2.0)}}$ | $1.9_{\mbox{\tiny(-1.9)}}$ | $2.0_{\mbox{\tiny(-1.9)}}$ | $0.0_{\mbox{\tiny(0.0)}}$ | $2.0_{\mbox{\tiny(-2.0)}}$ | $0.0_{\mbox{\tiny(0.0)}}$ | $1.0_{\mbox{\tiny(-0.9)}}$
$5$ | $50$ | DD-SBM | $3.0_{\mbox{\tiny(-2.5)}}$ | $3.9_{\mbox{\tiny(-3.9)}}$ | $3.9_{\mbox{\tiny(-3.8)}}$ | $2.3_{\mbox{\tiny(-2.0)}}$ | $1.2_{\mbox{\tiny(0.7)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $3.6_{\mbox{\tiny(-3.6)}}$ | $2.8_{\mbox{\tiny(-2.7)}}$
c-SBM | $3.7_{\mbox{\tiny(-3.7)}}$ | $3.9_{\mbox{\tiny(-3.9)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $3.0_{\mbox{\tiny(-3.0)}}$ | $1.4_{\mbox{\tiny(-1.0)}}$ | $3.9_{\mbox{\tiny(-3.9)}}$ | $3.8_{\mbox{\tiny(-3.7)}}$ | $2.9_{\mbox{\tiny(-2.9)}}$
CLBIC | $3.1_{\mbox{\tiny(-3.1)}}$ | $3.4_{\mbox{\tiny(-3.4)}}$ | $3.3_{\mbox{\tiny(-3.3)}}$ | $3.5_{\mbox{\tiny(-3.4)}}$ | $1.9_{\mbox{\tiny(-1.6)}}$ | $3.4_{\mbox{\tiny(-3.3)}}$ | $3.2_{\mbox{\tiny(-3.2)}}$ | $2.9_{\mbox{\tiny(-2.8)}}$
NCV | $4.0_{\mbox{\tiny(-4.0)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $2.0_{\mbox{\tiny(-1.5)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $3.2_{\mbox{\tiny(-3.0)}}$
$75$ | DD-SBM | $2.0_{\mbox{\tiny(-1.1)}}$ | $3.9_{\mbox{\tiny(-3.9)}}$ | $3.9_{\mbox{\tiny(-3.9)}}$ | $2.6_{\mbox{\tiny(-2.4)}}$ | $0.5_{\mbox{\tiny(0.0)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $2.3_{\mbox{\tiny(-2.0)}}$ | $2.9_{\mbox{\tiny(-2.8)}}$
c-SBM | $2.7_{\mbox{\tiny(-2.5)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $3.0_{\mbox{\tiny(-3.0)}}$ | $0.8_{\mbox{\tiny(-0.3)}}$ | $4.0_{\mbox{\tiny(-3.9)}}$ | $2.3_{\mbox{\tiny(-2.0)}}$ | $2.9_{\mbox{\tiny(-2.9)}}$
CLBIC | $2.6_{\mbox{\tiny(-2.5)}}$ | $3.0_{\mbox{\tiny(-3.0)}}$ | $3.0_{\mbox{\tiny(-3.0)}}$ | $2.9_{\mbox{\tiny(-2.9)}}$ | $0.0_{\mbox{\tiny(0.0)}}$ | $3.0_{\mbox{\tiny(-3.0)}}$ | $2.8_{\mbox{\tiny(-2.8)}}$ | $2.7_{\mbox{\tiny(-2.7)}}$
NCV | $3.9_{\mbox{\tiny(-3.8)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $3.9_{\mbox{\tiny(-3.9)}}$ | $0.0_{\mbox{\tiny(0.0)}}$ | $4.0_{\mbox{\tiny(-4.0)}}$ | $3.9_{\mbox{\tiny(-3.8)}}$ | $2.7_{\mbox{\tiny(-2.6)}}$
$7$ | $50$ | DD-SBM | $5.6_{\mbox{\tiny(-5.5)}}$ | $5.9_{\mbox{\tiny(-5.9)}}$ | $5.9_{\mbox{\tiny(-5.9)}}$ | $4.1_{\mbox{\tiny(-3.9)}}$ | $3.5_{\mbox{\tiny(-3.1)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $4.6_{\mbox{\tiny(-4.5)}}$
c-SBM | $5.9_{\mbox{\tiny(-5.9)}}$ | $5.9_{\mbox{\tiny(-5.9)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $5.1_{\mbox{\tiny(-5.0)}}$ | $4.8_{\mbox{\tiny(-4.7)}}$ | $6.0_{\mbox{\tiny(-5.9)}}$ | $5.9_{\mbox{\tiny(-5.9)}}$ | $5.0_{\mbox{\tiny(-4.9)}}$
CLBIC | $5.2_{\mbox{\tiny(-5.2)}}$ | $5.3_{\mbox{\tiny(-5.3)}}$ | $5.3_{\mbox{\tiny(-5.3)}}$ | $5.5_{\mbox{\tiny(-5.4)}}$ | $4.9_{\mbox{\tiny(-4.8)}}$ | $5.3_{\mbox{\tiny(-5.3)}}$ | $5.3_{\mbox{\tiny(-5.3)}}$ | $4.9_{\mbox{\tiny(-4.8)}}$
NCV | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $5.6_{\mbox{\tiny(-5.5)}}$
$75$ | DD-SBM | $4.7_{\mbox{\tiny(-4.6)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-5.9)}}$ | $4.4_{\mbox{\tiny({-4.3})}}$ | $2.0_{\mbox{\tiny(-1.4)}}$ | $6.0_{\mbox{\tiny(-5.9)}}$ | $5.5_{\mbox{\tiny(-5.5)}}$ | $4.8_{\mbox{\tiny(-4.8)}}$
c-SBM | $5.4_{\mbox{\tiny(-5.4)}}$ | $5.9_{\mbox{\tiny(-5.9)}}$ | $5.9_{\mbox{\tiny(-5.9)}}$ | $5.0_{\mbox{\tiny(-5.0)}}$ | $2.6_{\mbox{\tiny(-2.3)}}$ | $5.9_{\mbox{\tiny(-5.9)}}$ | $5.4_{\mbox{\tiny(-5.3)}}$ | $5.0_{\mbox{\tiny(-5.0)}}$
CLBIC | $4.9_{\mbox{\tiny(-4.8)}}$ | $5.0_{\mbox{\tiny(-5.0)}}$ | $5.0_{\mbox{\tiny(-5.0)}}$ | $4.9_{\mbox{\tiny(-4.8)}}$ | $3.5_{\mbox{\tiny(-3.4)}}$ | $5.0_{\mbox{\tiny(-5.0)}}$ | $5.0_{\mbox{\tiny(-5.0)}}$ | $4.7_{\mbox{\tiny(-4.7)}}$
NCV | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $3.5_{\mbox{\tiny(-3.2)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $6.0_{\mbox{\tiny(-6.0)}}$ | $4.8_{\mbox{\tiny(-4.8)}}$
Table 1: RMSE and bias of $\hat{K}$ with bias in parentheses.

Compared with c-SBM, DD-SBM achieves similar accuracy across different
configurations. To be specific, when $k_{0}=3$, DD-SBM tends to over-estimate
the number of communities; when $\rho=\frac{1}{2}$ and $k_{0}\in\\{5,7\\}$,
DD-SBM is slightly more accurate than c-SBM in Case 1 and 3 and similarly
accurate to c-SBM in Case 2 and 4. When the posterior samples of connectivity
matrix of c-SBM are also diagonally dominant, c-SBM is essentially DD-SBM.
Therefore, it is reasonable to expect DD-SBM and c-SBM have similar accuracy
in networks generated from diagonally dominant SBM.

Compared with CLBIC, DD-SBM is less accurate in most cases. This is due to the
design of $P^{0}$ in Case 1 - 3, such that the working likelihood of CLBIC is
close to the true likelihood. In Case 4, the true likelihood is more
complicated than the working likelihood of CLBIC, and the advantage of CLBIC
over DD-SBM is less obvious.

Compared with NCV, DD-SBM is more accurate in most cases. To be specific, when
$k_{0}=3$ and $\rho=\frac{1}{2}$, DD-SBM tends to over-estimate the number of
communities; in other configurations, DD-SBM is more accurate than NCV.

Case 2 is the most difficult as the between community connectivity probability
is very close to within community connectivity probability. Indeed, the
methods nearly uniformly choose one big community, except that CLBIC sometimes
chooses two communities.

To assess the membership assignment accuracy, we use the Hubert-Arabie
adjusted Rand index [14, 24] to measure the agreement between two clustering
assignments. The index is expected to be 0 if two independent assignments are
compared, and is 1 if two equivalent assignments are compared. Though the
adjusted Rand index tends to capture the disagreement among large clusters,
community sizes in our simulation study are about the same and the adjusted
Rand index is still a meaningful metric.

|  |  | Case 1 | Case 2 | Case 3 | Case 4
---|---|---|---|---|---|---
$k_{0}$ | $\rho$ | $n$ | DD-SBM | c-SBM | DD-SBM | c-SBM | DD-SBM | c-SBM | DD-SBM | c-SBM
$3$ | $\frac{1}{2}$ | $50$ | 0.62 | 0.63 | 0.00 | 0.00 | 0.05 | 0.01 | 0.37 | 0.42
$75$ | 0.87 | 0.91 | 0.00 | 0.00 | 0.12 | 0.05 | 0.47 | 0.51
$1$ | $50$ | 0.97 | 0.98 | 0.01 | 0.01 | 0.86 | 0.86 | 0.56 | 0.58
$75$ | 0.99 | 0.99 | 0.03 | 0.03 | 0.96 | 0.97 | 0.58 | 0.57
$5$ | $\frac{1}{2}$ | $50$ | 0.10 | 0.03 | 0.00 | 0.00 | 0.01 | 0.00 | 0.20 | 0.22
$75$ | 0.25 | 0.11 | 0.00 | 0.00 | 0.01 | 0.00 | 0.28 | 0.30
$1$ | $50$ | 0.83 | 0.86 | 0.00 | 0.00 | 0.06 | 0.03 | 0.33 | 0.34
$75$ | 0.94 | 0.99 | 0.00 | 0.00 | 0.32 | 0.17 | 0.35 | 0.36
$7$ | $\frac{1}{2}$ | $50$ | 0.03 | 0.00 | 0.00 | 0.00 | 0.01 | 0.00 | 0.12 | 0.12
$75$ | 0.07 | 0.01 | 0.00 | 0.00 | 0.00 | 0.00 | 0.19 | 0.20
$1$ | $50$ | 0.24 | 0.12 | 0.00 | 0.00 | 0.01 | 0.00 | 0.24 | 0.24
$75$ | 0.57 | 0.43 | 0.00 | 0.00 | 0.04 | 0.02 | 0.27 | 0.27
Table 2: Adjusted Rand index

Given a synthetic network $A$ and draws from the posterior distribution
$\Pi(\cdot|A)$, we can compute the adjusted Rand index of posterior draws of
$Z$ against $Z_{0}$ and use their mean as the accuracy metric for
$\Pi(\cdot|A)$. Like the adjusted Rand index for two clustering assignments,
the averaged index assesses the agreement of the posterior distribution of $Z$
against the truth $Z_{0}$.

Table 2 presents the average of adjusted Rand indices of the 100 synthetic
networks under different $(k_{0},\rho,n)$ configurations in the four cases.
Overall, the average adjusted Rand index of DD-SBM is similar to that of
c-SBM. This echoes the similar estimation accuracy of $k$ of DD-SBM and c-SBM,
as community detection is highly sensitive to the number of communities. When
$\rho=1/2$ and $k_{0}\in\\{5,7\\}$, DD-SBM is slightly better than c-SBM in
Case 1 and 3. When data is less informative, the regularity in the prior of
DD-SBM improves estimation accuracy over c-SBM. The advantage disappears in
Case 2 and 4 where cross community connectivity is close to within community
connectivity.

##  6 Sparse Networks

The framework in Section 3 can be extended to sparse networks whose overall
connectivity probability shrinks to 0 as network size increases [e.g. 16, 7].
We state the posterior contraction rates and the posterior consistency results
for those sparse networks as follows. Their proofs follow exactly the same
argument except that the derivations involve the sparse factor $\rho_{n}$.

######  Theorem 6.1.

Suppose adjacency matrix $A\in\\{0,1\\}^{n\times n}$ is generated from the SBM
with $\theta_{n}^{0}={\rho_{n}}T(Z_{0}P^{0}Z_{0}^{T})$, ${\rm
log}(k_{0})/n\precsim\rho_{n}\precsim 1$, $P^{0}\in\Theta_{k_{0},\delta_{0}}$
for some $k_{0}\precsim\sqrt{n}$ and $\delta_{0}>0$, and the number of zero
and one entries of $T(Z_{0}P^{0}Z_{0}^{T})$ is at most
$O(n^{2}\varepsilon_{n})$ where $\varepsilon_{n}^{2}\asymp\frac{{\rm
log}(k_{0})}{n}$. The prior $\Pi_{n}$ satisfies Assumption 2. Then, for all
sufficiently large $M$,

${{\mathbb{P}}_{0,n}}{\Pi_{n}}\left({\theta:||\theta-\theta_{n}^{0}||_{\infty}\geq
M\varepsilon_{n}}|A\right)\to 0.$

The posterior contraction rate in Theorem 6.1 is independent of the sparsity
level. In contrast, $L_{2}$ minimax rates of error derived in [16, 7] are
proportional to the sparsity level. We conjecture that $L_{\infty}$ minimax
rates of error are also proportional to the sparsity level. It is likely that
the posterior contraction rate in Theorem 6.1 is sub-optimal.

######  Theorem 6.2.

Under the same assumptions of Theorem 6.1 except that the sparsity level
satisfies ${\rm log}(k_{0})/n\precsim\rho^{2}_{n}\precsim 1$, then

${{\mathbb{P}}_{0,n}}\left[{{\Pi_{n}}\left(\\{K=k_{0}\\}\cap\\{Z={Z_{0}}\\}|A\right)}\right]\to
1.$

In the sparse network setting, the diagonal dominance gap also vanishes at the
rate of $\rho_{n}$. Our identification strategy for the number of communities
requires $\rho_{n}\delta_{0}\succsim\varepsilon_{n}\asymp\sqrt{{\rm
log}(k_{0})/n}$ to guarantee consistent community detection. In contrast, some
work in the sparse network literature works for networks with sparser sparsity
levels [e.g. 1, for a recent survey]. The Bayesian model outlined in (3) may
need additional modifications to adapt to networks at various sparse levels.

##  7 Concluding Remarks

In this paper, we have shown Bayesian SBM can consistently estimate the number
of communities and the membership assignment. Towards this end, we propose the
diagonally dominant Nowicki-Snijders’ prior and trade conjugacy of Nowicki-
Snijders’ prior for simpler and clearer asymptotic analysis.

In the simulation studies, c-SBM has similar finite sample estimation accuracy
to DD-SBM. We conjecture that c-SBM can also consistently estimate the number
of communities and the membership assignment for networks generated from
diagonally dominant SBM. However, the proof technique adopted in this paper
cannot be applied to c-SBM.

The price of losing conjugacy is on the computation side. The posterior
sampler in [8] is much faster than our allocation sampler as they successfully
adapt the idea of MFM sampler of [20] to the SBM case. It remains unclear if
the MFM idea can be applied to the non-conjugate case.

## References

  * Abbe [2017] [author] Abbe, EmmanuelE. (2017). Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research 18 6446–6531.
  * Airoldi et al. [2008] [author] Airoldi, Edoardo ME. M., Blei, David MD. M., Fienberg, Stephen ES. E. and Xing, Eric PE. P. (2008). Mixed membership stochastic blockmodels. Journal of machine learning research 9 1981–2014.
  * Barron, Schervish and Wasserman [1999] [author] Barron, AndrewA., Schervish, Mark JM. J. and Wasserman, LarryL. (1999). The consistency of posterior distributions in nonparametric problems. The Annals of Statistics 27 536–561.
  * Bickel and Sarkar [2016] [author] Bickel, Peter JP. J. and Sarkar, PurnamritaP. (2016). Hypothesis testing for automated community detection in networks. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 78 253–273.
  * Chen and Lei [2018] [author] Chen, KehuiK. and Lei, JingJ. (2018). Network cross-validation for determining the number of communities in network data. Journal of the American Statistical Association 113 241–251.
  * Gao, Lu and Zhou [2015] [author] Gao, ChaoC., Lu, YuY. and Zhou, Harrison HH. H. (2015). Rate-optimal graphon estimation. The Annals of Statistics 43 2624–2652.
  * Gao and Ma [2018] [author] Gao, ChaoC. and Ma, ZongmingZ. (2018). Minimax rates in network analysis: Graphon estimation, community detection and hypothesis testing. arXiv preprint arXiv:1811.06055.
  * Geng, Bhattacharya and Pati [2019] [author] Geng, JunxianJ., Bhattacharya, AnirbanA. and Pati, DebdeepD. (2019). Probabilistic community detection with unknown number of communities. Journal of the American Statistical Association 114 893–905.
  * Ghosal, Ghosh and Ramamoorthi [1999] [author] Ghosal, SubhashisS., Ghosh, Jayanta KJ. K. and Ramamoorthi, RVR. (1999). Posterior consistency of Dirichlet mixtures in density estimation. Ann. Statist 27 143–158.
  * Ghosal, Ghosh and van der Vaart [2000] [author] Ghosal, SubhashisS., Ghosh, Jayanta KJ. K. and van der Vaart, Aad WA. W. (2000). Convergence rates of posterior distributions. Annals of Statistics 28 500–531.
  * Ghosal and van der Vaart [2007] [author] Ghosal, SubhashisS. and van der Vaart, AadA. (2007). Convergence rates of posterior distributions for noniid observations. The Annals of Statistics 35 192–223.
  * Ghosal and van der Vaart [2017] [author] Ghosal, SubhashisS. and van der Vaart, AadA. (2017). Fundamentals of nonparametric Bayesian inference 44\. Cambridge University Press.
  * Ghosh, Pati and Bhattacharya [2019] [author] Ghosh, PrasenjitP., Pati, DebdeepD. and Bhattacharya, AnirbanA. (2019). Posterior Contraction Rates for Stochastic Block Models. Sankhya A 1–29.
  * Hubert and Arabie [1985] [author] Hubert, LawrenceL. and Arabie, PhippsP. (1985). Comparing partitions. Journal of classification 2 193–218.
  * Karrer and Newman [2011] [author] Karrer, BrianB. and Newman, Mark EJM. E. (2011). Stochastic blockmodels and community structure in networks. Physical review E 83 016107\.
  * Klopp, Tsybakov and Verzelen [2017] [author] Klopp, OlgaO., Tsybakov, Alexandre BA. B. and Verzelen, NicolasN. (2017). Oracle inequalities for network models and sparse graphon estimation. The Annals of Statistics 45 316–354.
  * Lei [2016] [author] Lei, JingJ. (2016). A goodness-of-fit test for stochastic block models. The Annals of Statistics 44 401–424.
  * Li, Levina and Zhu [2020] [author] Li, TianxiT., Levina, ElizavetaE. and Zhu, JiJ. (2020). Network cross-validation by edge sampling. Biometrika 107 257–276.
  * McDaid et al. [2013] [author] McDaid, Aaron FA. F., Murphy, Thomas BrendanT. B., Friel, NialN. and Hurley, Neil JN. J. (2013). Improved Bayesian inference for the stochastic block model with application to large networks. Computational Statistics & Data Analysis 60 12–31.
  * Miller and Harrison [2018] [author] Miller, Jeffrey WJ. W. and Harrison, Matthew TM. T. (2018). Mixture models with a prior on the number of components. Journal of the American Statistical Association 113 340–356.
  * Nobile and Fearnside [2007] [author] Nobile, AgostinoA. and Fearnside, Alastair TA. T. (2007). Bayesian finite mixtures with an unknown number of components: The allocation sampler. Statistics and Computing 17 147–162.
  * Nowicki and Snijders [2001] [author] Nowicki, KrzysztofK. and Snijders, Tom A BT. A. B. (2001). Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association 96 1077–1087.
  * Peixoto [2014] [author] Peixoto, Tiago PT. P. (2014). Hierarchical block structures and high-resolution model selection in large networks. Physical Review X 4 011047\.
  * Rand [1971] [author] Rand, William MW. M. (1971). Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association 66 846–850.
  * Saldana, Yu and Feng [2017] [author] Saldana, D FrancoD. F., Yu, YiY. and Feng, YangY. (2017). How many communities are there? Journal of Computational and Graphical Statistics 26 171–181.
  * Schwartz [1965] [author] Schwartz, LorraineL. (1965). On Bayes procedures. Probability Theory and Related Fields 4 10–26.
  * van der Pas and van der Vaart [2018] [author] van der Pas, SLS. and van der Vaart, AWA. (2018). Bayesian community detection. Bayesian Analysis 13 767–796.
  * Wang and Bickel [2017] [author] Wang, YX RachelY. R. and Bickel, Peter JP. J. (2017). Likelihood-based model selection for stochastic block models. The Annals of Statistics 45 500–528.
  * Zhao, Levina and Zhu [2011] [author] Zhao, YunpengY., Levina, ElizavetaE. and Zhu, JiJ. (2011). Community extraction for social networks. Proceedings of the National Academy of Sciences 108 7321–7326.

Supplement to “Consistent Bayesian Community Detection”. This Supplement
contains additional results and proofs in the text.

Supplement to “Consistent Bayesian Community Detection”

The supplement file contains complete proofs for Lemma 3.1, 3.6, 3.7, 3.8 and
3.9, details of the sampler, and complete simulation results for all
configurations.

##  8 Proofs

#### Proof of Lemma 3.1

###### Proof.

Suppose $\theta\in\Theta_{k,\delta}$, it suffices to show
$\theta\notin\Theta_{k^{\prime},\delta^{\prime}}$ for all $k^{\prime}<k$ and
$\delta^{\prime}\geq 0$. Now prove the statement by contradiction.

If $\theta\in\Theta_{k^{\prime},\delta^{\prime}}$ for some $k^{\prime}<k$ and
$\delta^{\prime}\geq 0$, then some nodes from some communities implied by
$\theta$ are merged. But by construction of $\Theta_{k,\delta}$, between-
community connectivity probabilities of $\theta$ are strictly less than
corresponding within community connectivity probabilities. Therefore, once
merged, the connectivity probabilities of the merged block are not identical.
This is a contradiction.

∎

#### Proof of Lemma 3.6

###### Proof.

The Hellinger distance between two Bernoulli random variables satisfies

$\begin{array}[]{lll}{H^{2}}\left({{{\mathbb{P}}_{\theta_{ij}^{0}}},{{\mathbb{P}}_{\theta_{ij}^{1}}}}\right)&=&\frac{1}{2}\left[{{{\left({\sqrt{\theta_{ij}^{0}}-\sqrt{\theta_{ij}^{1}}}\right)}^{2}}+{{\left({\sqrt{1-\theta_{ij}^{0}}-\sqrt{1-\theta_{ij}^{1}}}\right)}^{2}}}\right]\\\
&=&\frac{1}{2}\left[{{{\left({\frac{1}{2}2|\sqrt{\theta_{ij}^{0}}-\sqrt{\theta_{ij}^{1}}|}\right)}^{2}}+{{\left({\frac{1}{2}2|\sqrt{1-\theta_{ij}^{0}}-\sqrt{1-\theta_{ij}^{1}}|}\right)}^{2}}}\right]\\\
&\geq&\frac{1}{4}{\left({\theta_{ij}^{0}-\theta_{ij}^{1}}\right)^{2}}\end{array}$

as $\theta_{ij}^{0}$ and $\theta_{ij}^{1}$ are in $[0,1]$,
$|\sqrt{\theta_{ij}^{0}}+\sqrt{\theta_{ij}^{1}}|\leq 2$ and
$|\sqrt{1-\theta_{ij}^{0}}+\sqrt{1-\theta_{ij}^{1}}|\leq 2$.

By independence, ${P_{\theta}}={\otimes_{i<j}}{P_{{\theta_{ij}}}}$. Then, the
Hellinger distance between ${\mathbb{P}}_{\theta^{0}}$ and
${\mathbb{P}}_{\theta^{1}}$ satisfies

$\begin{array}[]{lll}{H^{2}}\left({{P_{{\theta^{0}}}},{P_{{\theta^{1}}}}}\right)&=&2-2\prod\nolimits_{i<j}{\left({1-\frac{1}{2}{H^{2}}\left({{P_{\theta_{ij}^{0}}},{P_{\theta_{ij}^{1}}}}\right)}\right)}\\\
&\geq&2-2\prod\nolimits_{i<j}{\left({1-\frac{1}{8}{\left({\theta_{ij}^{0}-\theta_{ij}^{1}}\right)^{2}}}\right)}\\\
&\geq&2-2\mathop{\mathop{\rm
min}\nolimits}\nolimits_{i<j}\left({1-\frac{1}{8}{\left({\theta_{ij}^{0}-\theta_{ij}^{1}}\right)^{2}}}\right)\\\
&=&\frac{1}{4}\mathop{\mathop{\rm
max}\nolimits}\nolimits_{i<j}\left({\theta_{ij}^{0}-\theta_{ij}^{1}}\right)^{2}\\\
&=&\frac{1}{4}||{\theta^{0}}-{\theta^{1}}||_{\infty}^{2}.\end{array}$

∎

#### Proof of Lemma 3.7

###### Proof.

Note
${\Theta_{k,\delta_{n}}}={\cup_{Z\in{{\mathcal{Z}}_{n,k}}}}\Theta_{k,\delta_{n}}^{Z}$,
where
$\Theta_{k,\delta_{n}}^{Z}=\left\\{T(ZPZ^{T}):P\in{S_{k,\delta_{n}}}\right\\}$
denotes the $Z$ slice of the parameter space.

By Lemma 3.3 and the assumption on $\delta_{n}$ and $\varepsilon_{n}$, node-
wise connectivity probability matrix space can be simplified via
$\left\\{{\theta:||\theta-{\theta^{0}}|{|_{\infty}}<{\varepsilon_{n}}}\right\\}=\left\\{T(Z_{0}PZ_{0}^{T}):||P-{P^{0}}|{|_{\infty}}<{\varepsilon_{n}}\right\\}$.
This relation implies the covering number
$N\left({{\varepsilon_{n}},\Theta_{k,\delta_{n}}^{Z},||\cdot|{|_{\infty}}}\right)\leq{\left({1/{\varepsilon_{n}}}\right)^{k\left({k+1}\right)/2}}$,
and then union bound implies the covering number
$N\left({{\varepsilon_{n}},\Theta_{k,\delta_{n}},||\cdot|{|_{\infty}}}\right)\leq{k^{n}}{\left({1/{\varepsilon_{n}}}\right)^{k\left({k+1}\right)/2}}$.

By Lemma 3.1, $\Theta_{k,\delta}$ are non-overlapping for different $k$, then
another union bound implies the statement (9).

∎

#### Proof of Lemma 3.8

###### Proof.

First recall some basic expansions from calculus. For $x_{0}\in(0,1)$, define
$f\left(x\right)=-{x_{0}}{\rm
log}\frac{x}{{x{{}_{0}}}}-\left({1-{x_{0}}}\right){\rm
log}\frac{{1-x}}{{1-{x_{0}}}}$ for $x\in[0,1]$. Taylor expand $f(x)$ around
$x_{0}$:

$\begin{array}[]{lll}f\left(x\right)&=&f\left({{x_{0}}}\right)+{f^{\prime}}\left({{x_{0}}}\right)\left({x-{x_{0}}}\right)+\frac{1}{2}{f^{\prime\prime}}\left({{x_{0}}}\right){\left({x-{x_{0}}}\right)^{2}}+O\left({|x-{x_{0}}{|^{3}}}\right)\\\
&=&\frac{1}{{2{x_{0}}\left({1-{x_{0}}}\right)}}{\left({x-{x_{0}}}\right)^{2}}+O\left({|x-{x_{0}}{|^{3}}}\right).\end{array}$

For $x_{0}=0$, the above $f(x)=-{\rm log}(1-x)$ with the convention $0{\rm
log}0=0$. Its Taylor expansion around $0$ is $f\left(x\right)=-{\rm
log}(1-x)=x+O\left({{x^{2}}}\right)$. For $x_{0}=1$, the above $f(x)=-{\rm
log}(x)$ also with the convention $0{\rm log}0=0$. Its Taylor expansion around
$1$ is $f\left(x\right)=-{\rm
log}(x)=1-x+O\left({{{\left({1-x}\right)}^{2}}}\right)$.

With $||\theta-\theta^{0}||_{\infty}\leq\varepsilon_{n}$ and the assumption on
$\theta^{0}$, expand KL divergence at $\theta^{0}$,

$\begin{array}[]{lll}KL\left({{{\mathbb{P}}_{{\theta^{0}}}},{{\mathbb{P}}_{\theta}}}\right)&=&-\sum\nolimits_{i<j:\theta_{ij}^{0}>0}{\theta_{ij}^{0}{\rm
log}\frac{{{\theta_{ij}}}}{{\theta_{ij}^{0}}}}-\sum\nolimits_{i<j:\theta_{ij}^{0}<1}{\left({1-\theta_{ij}^{0}}\right){\rm
log}\frac{{1-{\theta_{ij}}}}{{1-\theta_{ij}^{0}}}}\\\
&\leq&\left({{N_{0}}+{N_{1}}}\right)\left({{\varepsilon_{n}}+O\left({\varepsilon_{n}^{2}}\right)}\right)+\frac{{n\left({n-1}\right)}}{2}C_{0}^{-1}\left({\varepsilon_{n}^{2}+O\left({|{\varepsilon_{n}}{|^{3}}}\right)}\right)\\\
&\precsim&{n^{2}}\varepsilon_{n}^{2}/{C_{0}}\end{array}$

where ${N_{0}}=\\#\left\\{{\left({i,j}\right):\theta_{ij}^{0}=0,i<j}\right\\}$
denotes the number of zero entries in $\theta^{0}$, and
${N_{1}}=\\#\left\\{{\left({i,j}\right):\theta_{ij}^{0}=1,i<j}\right\\}$
denotes the number of one entries in $\theta^{0}$.

To bound $V_{2,0}$, note the Taylor expansion of $f\left(x\right)={\rm
log}\frac{x}{{1-x}}$ around $x_{0}\in(0,1)$ satisfies $f\left(x\right)={\rm
log}\frac{x}{{1-x}}={\rm
log}\frac{{{x_{0}}}}{{1-{x_{0}}}}+\frac{1}{{{x_{0}}\left({1-{x_{0}}}\right)}}\left({x-{x_{0}}}\right)+O\left({{{\left({x-{x_{0}}}\right)}^{2}}}\right)$.

By independence of different entries and with
$||\theta-\theta^{0}||_{\infty}\leq\varepsilon_{n}$, KL variation can be
bounded similarly by an expansion of $f(x)={\rm log}(x/(1-x))$:

$\begin{array}[]{lll}{V_{2,0}}\left({{{\mathbb{P}}_{{\theta^{0}}}},{{\mathbb{P}}_{\theta}}}\right)&=&{{\mathbb{P}}_{0}}\left\\{{{{\left[{\sum\limits_{i<j}{\left({{A_{ij}}{\rm
log}\frac{{{\theta_{ij}}}}{{\theta_{ij}^{0}}}+\left({1-{A_{ij}}}\right){\rm
log}\frac{{1-{\theta_{ij}}}}{{1-\theta_{ij}^{0}}}}\right)}+KL\left({{{\mathbb{P}}_{{\theta^{0}}}},{{\mathbb{P}}_{\theta}}}\right)}\right]}^{2}}}\right\\}\\\
&=&\sum\limits_{i<j}{{{\mathbb{P}}_{0}}\left\\{{{{\left[{\left({{A_{ij}}{\rm
log}\frac{{{\theta_{ij}}}}{{\theta_{ij}^{0}}}+\left({1-{A_{ij}}}\right){\rm
log}\frac{{1-{\theta_{ij}}}}{{1-\theta_{ij}^{0}}}}\right)+KL\left({{{\mathbb{P}}_{\theta_{ij}^{0}}},{{\mathbb{P}}_{{\theta_{ij}}}}}\right)}\right]}^{2}}}\right\\}}\\\
&=&\sum\nolimits_{i<j}{\theta_{ij}^{0}\left({1-\theta_{ij}^{0}}\right){{\left({{\rm
log}\frac{{{\theta_{ij}}}}{{1-{\theta_{ij}}}}-{\rm
log}\frac{{\theta_{ij}^{0}}}{{1-\theta_{ij}^{0}}}}\right)}^{2}}}\\\
&\precsim&\sum\nolimits_{i<j}\frac{1}{\theta_{ij}^{0}\left({1-\theta_{ij}^{0}}\right)}\varepsilon_{n}^{2}\\\
&\precsim&{n^{2}}\varepsilon_{n}^{2}/{C_{0}}\end{array}$

∎

#### Proof of Lemma 3.9

###### Proof.

By the dependence assumption made in Assumption 2, the prior mass has the
factorization

${\Pi_{n}}\left({P:||P-{P^{0}}|{|_{\infty}}<C_{0}{\varepsilon_{n}}}|K=k_{0}\right){\Pi_{n}}\left({Z={Z_{0}}|K={k_{0}}}\right){\Pi_{n}}\left({K={k_{0}}}\right).$
(13)

Next, we bound individual components of (13) respectively.

To bound the first component of (13), the conditional indepence of the off-
diagonal entries of $P$ on the diagonal entries of $P$ suggests the following
factorization,

$\begin{array}[]{ll}&{\Pi_{n}}\left({P:||P-{P^{0}}|{|_{\infty}}<C_{0}{\varepsilon_{n}}}|K=k_{0}\right)\\\
=&{\Pi_{n}}\left({\bigcap_{1\leq a\leq b\leq k_{0}}E_{n,ab}}|K=k_{0}\right)\\\
=&\prod_{1\leq a\leq k_{0}}\left\\{\int_{E_{n,aa}}\left[\prod\nolimits_{1\leq
a<b\leq
k_{0}}{\Pi_{n}}\left(E_{n,ab}|\\{P_{aa}\\},K=k_{0}\right)\right]d\Pi_{n}(P_{aa}|K=k_{0})\right\\}\end{array}$

where $E_{n,ab}=\\{P_{ab}:|P_{ab}-{P_{ab}^{0}}|<C_{0}{\varepsilon_{n}}\\}$. As
${\varepsilon_{n}}=o(1)$ and $P^{0}\in S_{k_{0},\delta_{0}}$, (conditional)
prior density of $P_{ab}$ is positive on $E_{n,ab}$ for all $a,b\in[k_{0}]$.

By Assumption 2 (2), for $a<b\in[k_{0}]$, the prior probability
$\Pi_{n}(E_{n,ab}|\\{P_{aa}\\},K=k_{0})\geq|E_{n,ab}|\mathop{\rm
min}\nolimits\limits_{P_{ab}\in
E_{n,ab}}\pi_{n}(P_{ab}|\\{P_{aa}\\},K=k_{0},\delta)\succsim\varepsilon_{n}e^{-C{\rm
log}(n)(P_{aa}\wedge P_{bb})}$ for some universal constant $C$. As $P_{aa}\in
E_{n,aa}$ for $a\in[k_{0}]$, $P_{aa}\wedge P_{bb}\leq(P^{0}_{aa}\wedge
P^{0}_{bb})+C_{0}\varepsilon_{n}\leq||P^{0}||_{\infty}+C_{0}\varepsilon_{n}$,
which gives a bound independent of $\\{P_{aa}\\}$.

Similarly, Assumption 2 (2) implies
$\Pi_{n}(E_{n,aa}|K=k_{0})\succsim\varepsilon_{n}e^{-C{\rm
log}(n)(P^{0}_{aa}+C_{0}\varepsilon_{n})}$.

Therefore, combining the bounds for $P_{ab}$’s gives

${\Pi_{n}}\left({P:||P-{P^{0}}|{|_{\infty}}<C_{0}{\varepsilon_{n}}}|K=k_{0}\right)\succsim
e^{Ck_{0}^{2}{\rm log}(\varepsilon_{n})-Ck_{0}^{2}{\rm
log}(n)(||P^{0}||_{\infty}+C_{0}\varepsilon_{n})}$

where $k_{0}^{2}$ has the same order as $\frac{1}{2}k_{0}(k_{0}+1)$ and is
used for simpler notation, and the constant $C$ is universal.

As $\varepsilon_{n}^{2}\asymp{\rm log}(k_{0})/n$ and $1\succsim{\rm
log}(k_{0})/n$, ${\rm log}(n)\succsim-{\rm log}(\varepsilon_{n})$. As
$k_{0}\precsim\sqrt{n}$, $k_{0}^{2}{\rm log}(n)\precsim n{\rm log}(k_{0})$.
Then,
${\Pi_{n}}\left({P:||P-{P^{0}}|{|_{\infty}}<C_{0}{\varepsilon_{n}}}|K=k_{0}\right)\succsim
e^{-Cn{\rm log}(k_{0})}$ for some constant $C$ dependent on $P^{0}$.

To bound the second and the third component of (13), by Assumption 2 (3) and
(4), there exists a universal constant $C$ such that
${\Pi_{n}}\left({Z={Z_{0}}|K={k_{0}}}\right)\geq e^{-Cn{\rm log}(k_{0})}$ and
${\Pi_{n}}\left({K={k_{0}}}\right)\geq e^{-Cn{\rm log}(k_{0})}$.

Note $n^{2}\varepsilon_{n}^{2}\asymp n{\rm log}(k_{0})$, the right hand side
of the inequality (10) can be replaced with $e^{-Cn{\rm log}(k_{0})}$ and (10)
holds for some constant $C$ dependent on $P^{0}$.

∎

##  9 Posterior Sampler

This section presents details of the Metropolis-Hastings algorithm used to
draw posterior samples from (11). The proposal has two stages: in the first
stage, sample $(Z,K)$; in the second stage, sample $P$ given $(Z,K)$. The
first stage is adapted from the allocation sampler [19].

At $t^{th}$ iteration, the proposal
$\Pi_{prop}\left(Z^{*},K^{*}|A,Z^{(t)},K^{(t)},P^{(t)}\right)$ consists of the
four steps MK, GS, M3 and AE with equal probability $\frac{1}{4}$. With
proposal $(Z^{*},K^{*})$, sample $P^{*}|(Z^{*},A)$ by independently sampling
each entry of $P^{*}$ from the Beta distribution
$Beta\left({{O_{ab}^{*}}+1,{n_{ab}^{*}}-{O_{ab}^{*}}+1}\right)$. With proposal
$(P^{*},Z^{*},K^{*})$, the acceptance rates in the allocation sampler regimes
are computed.

###  9.1 MK

MK: choose “add” or “delete” one empty cluster with probability $1/2$. If
“add” move is chosen, randomly pick one community identifier from $[K+1]$ for
the new empty community and rename the others as necessary; if “delete” move
is chosen, randomly pick one community from $[K]$, delete the community if it
is empty and abandon the MK move if it is not empty.

In the step MK, if “add” one empty community is chosen, accept the proposal
with probability $\mathop{\rm
min}\nolimits\left({1,\frac{{{\Pi_{n}}\left({{P^{*}}|{Z^{*}}}\right)}}{{{\Pi_{n}}\left({{P^{\left(t\right)}}|{Z^{\left(t\right)}}}\right)}}\frac{K}{{{K^{*}}}}}\frac{1}{n+K}\right)$;
if “delete” one empty community is chosen, accept the proposal with
probability

$\mathop{\rm
min}\nolimits\left({1,\frac{{{\Pi_{n}}\left({{P^{*}}|{Z^{*}}}\right)}}{{{\Pi_{n}}\left({{P^{\left(t\right)}}|{Z^{\left(t\right)}}}\right)}}\frac{K}{{{K^{*}}}}}{(n+K-1)}\right).$

###  9.2 GS

GS: relabel a random node. First randomly pick $i$ then generate $Z^{*}(i)$
according to
$\Pi_{prop}(Z^{*}(i)=k)\propto\beta(Z^{*},A)^{-1}\Pi(Z^{*}|K^{*})$ where
$K^{*}=K^{(t)}$, the prior probability
$\Pi(Z^{*}|K^{*})=\int\Pi(Z^{*}|\alpha,K^{*})\Pi(\alpha|K^{*})d\alpha=\frac{\Gamma(K^{*})}{\Gamma(n+K^{*})}\prod_{1\leq
c\leq K}\Gamma(n_{c}^{*}+1)$ due to multinomial-Dirichlet conjugacy, and
$\beta(Z^{*},A)=\prod_{1\leq a\leq b\leq
K}\frac{\Gamma(n_{ab}^{*}+2)}{\Gamma(O_{ab}^{*}+1)\Gamma(n_{ab}^{*}-O_{ab}^{*}+1)}$
is the coefficient corresponding to the proposal distribution of $P$. Clearly,
$Z^{*}(j)=Z(j)$ for all $j\neq i\in[n]$.

In the step GS, suppose node $i$ is chosen and its original label $c_{1}$ is
relabeled with $c_{2}$, then accept the proposal with probability $\mathop{\rm
min}\nolimits\left(1,\frac{{{\Pi_{n}}\left({{P^{*}}|{Z^{*}}}\right)}}{{{\Pi_{n}}\left({{P^{\left(t\right)}}|{Z^{\left(t\right)}}}\right)}}\right)$.

###  9.3 M3

M3: randomly pick two communities $c_{1},c_{2}\in[K]$, reassign nodes
$\\{i:Z(i)\in\\{c_{1},c_{2}\\}\\}$ to $\\{c_{1},c_{2}\\}$ sequentially
according to the following scheme. Start with $B_{0}=B_{1}=\emptyset$ and
$A_{0}$ being the sub-network without nodes from community $c_{1}$ and
$c_{2}$, define the assignment $B_{h}=\\{Z^{*}(x_{i})\\}_{i=1}^{h-1}$ with
$x_{i}$ being the node index of the $i^{th}$ element in
$\\{i:Z(i)\in\\{c_{1},c_{2}\\}\\}$, define the sub-network
$A_{h}=A_{h-1}\cup\\{x_{h}\\}$ by appending one more node, define the
assignment $Z_{B_{h}}^{c_{j}}$ for the sub-network $A_{h}$ as the assignment
with the node $x_{h}$ assigned to $c_{j}$, and define the size of communities
in the sub-network $A_{h-1}$ as $\\{n_{h,c}\\}_{c\in[K]}$. For $i\in[n_{c}]$,
assign the $i^{th}$ node of $\\{i:Z(i)\in\\{c_{1},c_{2}\\}\\}$ to $c_{1}$ with
probability $p_{B_{i}}^{c_{1}}$ and to $c_{2}$ with probability
$p_{B_{i}}^{c_{2}}\equiv 1-p_{B_{i}}^{c_{1}}$, where
$\frac{p_{B_{i}}^{c_{1}}}{p_{B_{i}}^{c_{2}}}=\frac{\Pi(A_{i},Z_{B_{i}}^{c_{1}},K,P)}{\Pi(A_{i},Z_{B_{i}}^{c_{2}},K,P)}=\frac{\Pi(A_{i}|P,Z_{B_{i}}^{c_{1}})\Pi(P|Z_{B_{i}}^{c_{1}},K)\Pi(Z_{B_{i}}^{c_{1}}|K)\Pi(K)}{\Pi(A_{i}|P,Z_{B_{i}}^{c_{2}})\Pi(P|Z_{B_{i}}^{c_{2}},K)\Pi(Z_{B_{i}}^{c_{2}}|K)\Pi(K)}=\frac{\Pi(A_{i}|P,Z_{B_{i}}^{c_{1}})(n_{i,c_{1}}+1)}{\Pi(A_{i}|P,Z_{B_{i}}^{c_{2}})(n_{i,c_{2}}+1)}$.

To improve mixing, once $c_{1}$ and $c_{2}$ are drawn, shuffle
$\\{i:Z(i)\in\\{c_{1},c_{2}\\}\\}$ before the sequential reassignment.
Therefore, the ordering of node indices in the sequential reassignment is
random.

In the step M3, suppose community $c_{1}$ and $c_{2}$ are chosen, then accept
the proposal with probability $\mathop{\rm
min}\nolimits\left({1,\frac{{{\Pi_{n}}\left({{P^{*}}|{Z^{*}}}\right)}}{{{\Pi_{n}}\left({{P^{\left(t\right)}}|{Z^{\left(t\right)}}}\right)}}\frac{\prod_{i=1}^{n_{c}}p_{B_{i}}^{Z(i)}}{\prod_{i=1}^{n_{c}}p_{B_{i}}^{Z^{*}(i)}}\frac{{\Gamma\left({n_{{c_{1}}}^{*}+1}\right)\Gamma\left({n_{{c_{2}}}^{*}+1}\right)}}{{\Gamma\left({n_{{c_{1}}}^{(t)}+1}\right)\Gamma\left({n_{{c_{2}}}^{(t)}+1}\right)}}\frac{{\beta\left({{Z^{\left(t\right)}},A}\right)}}{{\beta\left({{Z^{*}},A}\right)}}}\right)$,
where $n_{c}=n_{c_{1}}+n_{c_{2}}$.

###  9.4 AE

AE: merge two random clusters or split one cluster into two clusters with
probability $1/2$. If “merge” is chosen, randomly merge two clusters $c_{1}$
and $c_{2}$ with $Z^{*}(i)=c_{1}$ for all
$i\in\\{j:Z(j)\in\\{c_{1},c_{2}\\}\\}$ and $Z^{*}(i)=Z(i)$ for all
$i\notin\\{j:Z(j)\in\\{c_{1},c_{2}\\}\\}$. The proposal probability is
$\binom{K}{2}^{-1}$. If “split” is chosen, randomly pick two cluster
identifiers $\\{c_{1},c_{2}\\}$ from $[K+1]$, renaming others’ identifiers as
necessary, and assign the nodes in cluster $c_{1}$ to the cluster $c_{2}$ with
the random probability $p_{c}\sim U(0,1)$. By integrating out $p_{c}$, the
proposal probability is
$\frac{{\Gamma\left({{n_{{c_{1}}}}+1}\right)\Gamma\left({{n_{{c_{2}}}}+1}\right)}}{K(K+1){\Gamma\left({{n_{c}}+2}\right)}}$.

In the step AE, if “merge” two communities is chosen, accept the proposal with
probability $\mathop{\rm
min}\nolimits\left({1,\frac{{{\Pi_{n}}\left({{P^{*}}|{Z^{*}}}\right)}}{{{\Pi_{n}}\left({{P^{\left(t\right)}}|{Z^{\left(t\right)}}}\right)}}\frac{{{K^{\left(t\right)}}}}{{{K^{*}}}}\frac{{\beta\left({{Z^{\left(t\right)}},A}\right)}}{{\beta\left({{Z^{*}},A}\right)}}\frac{K^{*}+n}{{{n_{c_{1}}^{\left(t\right)}+1}}}}\right)$;
if “split” is chosen, accept the proposal with probability $\mathop{\rm
min}\nolimits\left({1,\frac{{{\Pi_{n}}\left({{P^{*}}|{Z^{*}}}\right)}}{{{\Pi_{n}}\left({{P^{\left(t\right)}}|{Z^{\left(t\right)}}}\right)}}\frac{{{K^{\left(t\right)}}}}{{{K^{*}}}}\frac{{\beta\left({{Z^{\left(t\right)}},A}\right)}}{{\beta\left({{Z^{*}},A}\right)}}\frac{n_{c_{1}}^{(t)}+1}{K+n}}\right)$.

##  10 Complete simulation results

This section provides complete simulation results. We choose
$(k_{0},n,\rho)\in\\{3,5,7\\}\times\\{50,75\\}\times\\{\frac{1}{2},1\\}$, and
for each $(k_{0},n,\rho)$ configuration, 100 networks are generated from
$SBM(Z_{0},\rho P^{0},n,k_{0})$.

To reduce Monte Carlo error and reach reasonable mixing, the Metropolis-
Hastings algorithm and the allocation sampler collect $2\times 10^{4}$
posterior draws for each synthetic dataset after discarding first $10^{4}$
draws as burn-in. Both algorithms are initialized at $K=2$ and random
membership assignment.

|  |  |  | Case 1 | Case 2 | Case 3 | Case 4
---|---|---|---|---|---|---|---
$k_{0}$ | $n$ | $\rho$ | Method | Bias | RMSE | Bias | RMSE | Bias | RMSE | Bias | RMSE
$3$ | $50$ | $\frac{1}{2}$ | DD-SBM | 1.3 | 1.8 | -1.9 | 1.9 | -1.6 | 1.8 | 0.0 | 1.3
c-SBM | -0.5 | 0.8 | -1.9 | 1.9 | -1.8 | 1.9 | -1.0 | 1.0
CLBIC | -0.2 | 0.5 | -1.2 | 1.3 | -1.2 | 1.3 | -1.1 | 1.3
NCV | -0.6 | 0.9 | -2.0 | 2.0 | -2.0 | 2.0 | -2.0 | 2.0
$1$ | DD-SBM | 0.1 | 0.3 | -1.9 | 2.0 | 0.1 | 0.3 | -0.6 | 1.0
c-SBM | -0.0 | 0.2 | -1.9 | 1.9 | -0.1 | 0.6 | -0.8 | 0.9
CLBIC | 0.0 | 0.0 | -1.3 | 1.4 | -0.3 | 0.6 | -0.9 | 1.0
NCV | 0.0 | 0.0 | -2.0 | 2.0 | -0.3 | 0.9 | -0.8 | 0.9
$3$ | $75$ | $\frac{1}{2}$ | DD-SBM | 0.5 | 1.0 | -1.9 | 2.0 | -1.1 | 1.6 | -0.6 | 1.1
c-SBM | -0.1 | 0.5 | -1.9 | 2.0 | -1.3 | 1.6 | -1.0 | 1.0
CLBIC | 0.0 | 0.0 | -1.0 | 1.0 | -0.8 | 0.9 | -0.9 | 1.0
NCV | 0.0 | 0.1 | -2.0 | 2.0 | -1.9 | 1.9 | -1.9 | 2.0
$1$ | DD-SBM | 0.0 | 0.1 | -1.9 | 1.9 | 0.0 | 0.2 | -0.7 | 0.9
c-SBM | 0.0 | 0.3 | -1.6 | 1.8 | 0.0 | 0.4 | -0.8 | 0.9
CLBIC | 0.0 | 0.0 | -1.0 | 1.0 | 0.0 | 0.0 | -0.9 | 1.0
NCV | 0.0 | 0.0 | -2.0 | 2.0 | 0.0 | 0.0 | -0.9 | 1.0
$5$ | $50$ | $\frac{1}{2}$ | DD-SBM | -2.5 | 3.0 | -3.9 | 3.9 | -3.8 | 3.9 | -2.0 | 2.3
c-SBM | -3.7 | 3.7 | -3.9 | 3.9 | -4.0 | 4.0 | -3.0 | 3.0
CLBIC | -3.1 | 3.1 | -3.4 | 3.4 | -3.3 | 3.3 | -3.4 | 3.5
NCV | -4.0 | 4.0 | -4.0 | 4.0 | -4.0 | 4.0 | -4.0 | 4.0
$1$ | DD-SBM | 0.7 | 1.2 | -4.0 | 4.0 | -3.6 | 3.6 | -2.7 | 2.8
c-SBM | -1.0 | 1.4 | -3.9 | 3.9 | -3.7 | 3.8 | -2.9 | 2.9
CLBIC | -1.6 | 1.9 | -3.3 | 3.4 | -3.2 | 3.2 | -2.8 | 2.9
NCV | -1.5 | 2.0 | -4.0 | 4.0 | -4.0 | 4.0 | -3.0 | 3.2
$5$ | $75$ | $\frac{1}{2}$ | DD-SBM | -1.1 | 2.0 | -3.9 | 3.9 | -3.9 | 3.9 | -2.4 | 2.6
c-SBM | -2.5 | 2.7 | -4.0 | 4.0 | -4.0 | 4.0 | -3.0 | 3.0
CLBIC | -2.5 | 2.6 | -3.0 | 3.0 | -3.0 | 3.0 | -2.9 | 2.9
NCV | -3.8 | 3.9 | -4.0 | 4.0 | -4.0 | 4.0 | -3.9 | 3.9
$1$ | DD-SBM | 0.0 | 0.5 | -4.0 | 4.0 | -2.0 | 2.3 | -2.8 | 2.9
c-SBM | -0.3 | 0.8 | -3.9 | 4.0 | -2.0 | 2.3 | -2.9 | 2.9
CLBIC | 0.0 | 0.0 | -3.0 | 3.0 | -2.8 | 2.8 | -2.7 | 2.7
NCV | 0.0 | 0.0 | -4.0 | 4.0 | -3.8 | 3.9 | -2.6 | 2.7
$7$ | $50$ | $\frac{1}{2}$ | DD-SBM | -5.5 | 5.6 | -5.9 | 5.9 | -5.9 | 5.9 | -3.9 | 4.1
c-SBM | -5.9 | 5.9 | -5.9 | 5.9 | -6.0 | 6.0 | -5.0 | 5.1
CLBIC | -5.2 | 5.2 | -5.3 | 5.3 | -5.3 | 5.3 | -5.4 | 5.5
NCV | -6.0 | 6.0 | -6.0 | 6.0 | -6.0 | 6.0 | -6.0 | 6.0
$1$ | DD-SBM | -3.1 | 3.5 | -6.0 | 6.0 | -6.0 | 6.0 | -4.5 | 4.6
c-SBM | -4.7 | 4.8 | -5.9 | 6.0 | -5.9 | 5.9 | -4.9 | 5.0
CLBIC | -4.8 | 4.9 | -5.3 | 5.3 | -5.3 | 5.3 | -4.8 | 4.9
NCV | -6.0 | 6.0 | -6.0 | 6.0 | -6.0 | 6.0 | -5.5 | 5.6
$7$ | $75$ | $\frac{1}{2}$ | DD-SBM | -4.6 | 4.7 | -6.0 | 6.0 | -5.9 | 6.0 | -4.3 | 4.4
c-SBM | -5.4 | 5.4 | -5.9 | 5.9 | -5.9 | 5.9 | -5.0 | 5.0
CLBIC | -4.8 | 4.9 | -5.0 | 5.0 | -5.0 | 5.0 | -4.8 | 4.9
NCV | -6.0 | 6.0 | -6.0 | 6.0 | -6.0 | 6.0 | -6.0 | 6.0
$1$ | DD-SBM | -1.4 | 2.0 | -5.9 | 6.0 | -5.5 | 5.5 | -4.8 | 4.8
c-SBM | -2.3 | 2.6 | -5.9 | 5.9 | -5.3 | 5.4 | -5.0 | 5.0
CLBIC | -3.4 | 3.5 | -5.0 | 5.0 | -5.0 | 5.0 | -4.7 | 4.7
NCV | -3.2 | 3.5 | -6.0 | 6.0 | -6.0 | 6.0 | -4.8 | 4.8
Table 3: Bias and RMSE of $\hat{K}$.