Reconstruction in the Labelled Stochastic Block Model
Reconstruction in the Labelled Stochastic Block Model
复制标题
标记随机块模型中的重建
DOI：
10.1109/tnse.2015.2490580
复制
发表时间：
2015
影响因子：
6.6
通讯作者：
Jiaming Xu
中科院分区：
文献类型：
--
作者：
M. Lelarge;L. Massoulié;Jiaming Xu
标号随机块模型是一种表示具有社区结构和多种类型相互作用的网络的随机图模型。在最简单的形式中，它由两个大小大致相等的社区组成，边缘被随机绘制和标记，概率取决于它们的两个端点是否属于同一社区。文献[1]推测，当且仅当模型参数超过阈值时，相关重建(即识别与底层社区的真实分区相关的分区)将是可行的。我们证明了这个猜想的一半，即当低于阈值时，重建是不可能的。在正方向上，我们引入了一个加权图来利用标签信息。通过适当选择权函数，我们证明了当超过阈值一定的常数时，通过(1)最小平分，(2)最小平分的半定松弛，(3)结合高次顶点边缘去除的谱方法来实现重建。此外，我们还证明了标记随机分块模型和标记Erdos-Renyi随机图模型之间的假设检验在假设的重建阈值下显示出相变。
The labelled stochastic block model is a random graph model representing networks with community structure and interactions of multiple types. In its simplest form, it consists of two communities of approximately equal size, and the edges are drawn and labelledat random with probability depending on whether their two endpoints belong to the same community or not. It has been conjectured in [1] that correlated reconstruction (i.e., identification of a partition correlated with the true partition into the underlying communities) would be feasible if and only if a model parameter exceeds a threshold. We prove one half of this conjecture, i.e., reconstruction is impossible when below the threshold. In the positive direction, we introduce a weighted graph to exploit the label information. With a suitable choice of weight function, we show that when above the threshold by a specific constant, reconstruction is achieved by (1) minimum bisection, (2) a semidefinite relaxation of minimum bisection, and (3) a spectral method combined with removal of edges incident to vertices of high degree. Furthermore, we show that hypothesis testing between the labelled stochastic block model and the labelled Erdos-Renyi random graph model exhibits a phase transition at the conjectured reconstruction threshold.
DOI：
10.1214/15-aap1145
发表时间：
2013-09
期刊：
--
影响因子：
--
作者：
Elchanan Mossel;Joe Neeman;A. Sly
通讯作者：
Elchanan Mossel;Joe Neeman;A. Sly