Spectral recovery of binary censored block models
Spectral recovery of binary censored block models
复制标题
二元删失块模型的谱恢复
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Colin Sandon
中科院分区：
文献类型：
--
作者：
Souvik Dhara;Julia Gaudio;Elchanan Mossel;Colin Sandon
社区检测是识别图中社区结构的问题。图通常被建模为随机块模型的样本，其中每个顶点属于一个社区。两个顶点通过边连接的概率取决于这些顶点的社区。在本文中，我们考虑了一个模型的{em censored}社区检测与两个社区，其中大部分的数据是失踪的状态，只有一小部分的潜在边缘被揭示。在该模型中，同一社区中的顶点以概率p$连接，而相反社区中的顶点以概率q$连接。给定顶点对${u，v}$的连通性状态以概率$alpha$显示，独立于所有对，其中$alpha = frac{t log（n）}{n}$。我们建立了信息论阈值$t_c（p，q）$，使得当$tt_c（p，q）$，一个简单的基于加权有符号邻接矩阵的谱算法，成功地精确恢复社区时，没有算法能成功地精确恢复社区。虽然频谱算法在对称的情况下具有接近最优的性能，我们表明，他们可能会失败的不对称的情况下，允许两个社区内的连接概率是不同的。特别是，我们展示了一个简单的两阶段算法成功的参数制度的存在，但任何算法的基础上的前两个特征向量的加权，签署邻接矩阵失败。
Community detection is the problem of identifying community structure in graphs. Often the graph is modeled as a sample from the Stochastic Block Model, in which each vertex belongs to a community. The probability that two vertices are connected by an edge depends on the communities of those vertices. In this paper, we consider a model of {em censored} community detection with two communities, where most of the data is missing as the status of only a small fraction of the potential edges is revealed. In this model, vertices in the same community are connected with probability $p$ while vertices in opposite communities are connected with probability $q$. The connectivity status of a given pair of vertices ${u,v}$ is revealed with probability $alpha$, independently across all pairs, where $alpha = frac{t log(n)}{n}$. We establish the information-theoretic threshold $t_c(p,q)$, such that no algorithm succeeds in recovering the communities exactly when $tt_c(p,q)$, a simple spectral algorithm based on a weighted, signed adjacency matrix succeeds in recovering the communities exactly. While spectral algorithms are shown to have near-optimal performance in the symmetric case, we show that they may fail in the asymmetric case where the connection probabilities inside the two communities are allowed to be different. In particular, we show the existence of a parameter regime where a simple two-phase algorithm succeeds but any algorithm based on the top two eigenvectors of the weighted, signed adjacency matrix fails.