Contiguity and non-reconstruction results for planted partition models: the dense case
Contiguity and non-reconstruction results for planted partition models: the dense case
复制标题
种植分区模型的连续性和非重构结果：密集情况
DOI：
10.1214/17-ejp128
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Debapratim Banerjee
中科院分区：
文献类型：
--
作者：
Debapratim Banerjee
我们考虑$n$个节点上具有渐近相等簇大小的两块随机块模型。集群内部和集群之间的连接概率分别用$p_n:=\frac{a_n}{n}$和$q_n:=\frac{b_n}{n}$表示。Mossel et al.（2012）考虑了$a_n=a$和$b_n=b$固定的情况。证明了随机块模型的概率模型与具有相同平均度的Erd{\ ' o} - r {\'e}nyi图的概率模型在$(a-b)^ 22 (a+b)$时是互连续的。Mossel et al.（2012）也证明了$(a-b)^ 22 (1-p)(a_n+b_n)$。进一步证明，当$(a_n-b_n)^2< 2(1-p)(a_n+b_n)$时，不可能找到与真实标记正相关的节点标记的估计。本文的结果证明了Decelle等人（2011）对密集图的猜想的否定部分。
We consider the two block stochastic block model on $n$ nodes with asymptotically equal cluster sizes. The connection probabilities within and between cluster are denoted by $p_n:=\frac{a_n}{n}$ and $q_n:=\frac{b_n}{n}$ respectively. Mossel et al.(2012) considered the case when $a_n=a$ and $b_n=b$ are fixed. They proved the probability models of the stochastic block model and that of Erd{\"o}s-R{\'e}nyi graph with same average degree are mutually contiguous whenever $(a-b)^2 2(a+b)$. Mossel et al.(2012) also proved that when $(a-b)^2 2(1-p)(a_n+b_n)$. Further we also prove it is impossible find an estimate of the labeling of the nodes which is positively correlated with the true labeling whenever $(a_n-b_n)^2< 2(1-p)(a_n+b_n)$. The results of this paper justify the negative part of a conjecture made in Decelle et al.(2011) for dense graphs.