1
$\begingroup$

Recently, numerous papers have been published about the stochastic block model (SBM). In the literature about SBMs, a plethora of different settings are considered. I am interested in how vertices are assigned to clusters in different versions of the SBM.

Consider a graph $G = (V,E)$ with $n$ vertices.

In [1], the SBM is defined in the following way:

Each vertex $v \in V$ is assigned independently a hidden (or planted) label $\sigma_v$ in $[k]$ under a probability distribution $p = (p_1,...,p_k)$ on $[k]$. That is, $P(\sigma_v = i) = p_i$, $i ∈ [k]$.

Then the cluster $V_i$ is given by all vertices $v$ with label $i$, i.e., $V_i = \{ v \in V : \sigma_v = i \}$.

(Then randomly add edges between the clusters. This is not relevant to this question.)

In [2], the SBM is defined as follows:

Partition the vertex set $\{1,2,...,n\}$ into $k$ clusters $V_1,V_2,...,V_k$ , of sizes $n_1,n_2,...,n_k$, respectively.

(Then randomly add edges between the clusters. This is not relevant to this question.)

Observe that in the setting of [1], the assignment of the vertices to the clusters $V_i$ is random. Even the sizes of the clusters $V_i$ are random variables. In [2], both the cluster assignments and the sizes are deterministic.

My question is as follows:

Are the models of [1] and [2] incomparable? Or does there exist a reduction s.t. the results of [1] can be used for [2] or vice versa?

[1] Abbe, Sandon: "Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery." FOCS 2015.

[2] Jalali, Han, Dumitriu, Fazel: "Exploiting Tradeoffs for Exact Recovery in Heterogeneous Stochastic Block Models." NIPS 2016.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.