Spectral thresholds in the bipartite stochastic block model
Spectral thresholds in the bipartite stochastic block model
复制标题
DOI：
--
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Laura Florescu;Will Perkins
中科院分区：
文献类型：
--
作者：
Laura Florescu;Will Perkins
我们考虑一个二分随机块模型的顶点集$V_1$和$V_2$，种植分区在每个，并要求在什么密度有效的算法可以恢复分区的较小的顶点集。当$|V_2|\gg| V_1| $，多个阈值出现。我们首先定位一个尖锐的阈值检测的分区，在意义上的结果\cite{mossel 2012 stochastic，mossel 2013 proof}和\cite{massoulie 2014 community}的随机块模型。然后，我们表明，在一个较高的边缘密度，奇异向量的矩形biadjacency矩阵表现出本地化/离域相变，恢复阈值以上，没有恢复以下。然而，我们提出了一个简单的频谱算法，对角删除SVD，恢复分区在一个接近最佳的边缘密度。本文所研究的二部随机块模型被\cite{Escherman 2014 algorithm}用来分别给出恢复随机超图和随机$k$-SAT公式中的种植划分和分配的统一算法。我们的研究结果给出了最知名的界限，在这些模型中，可以有效地找到解决方案的条款密度，以及显示通过这种减少二分块模型的进一步改进的障碍。
We consider a bipartite stochastic block model on vertex sets $V_1$ and $V_2$, with planted partitions in each, and ask at what densities efficient algorithms can recover the partition of the smaller vertex set. When $|V_2| \gg |V_1|$, multiple thresholds emerge. We first locate a sharp threshold for detection of the partition, in the sense of the results of \cite{mossel2012stochastic,mossel2013proof} and \cite{massoulie2014community} for the stochastic block model. We then show that at a higher edge density, the singular vectors of the rectangular biadjacency matrix exhibit a localization / delocalization phase transition, giving recovery above the threshold and no recovery below. Nevertheless, we propose a simple spectral algorithm, Diagonal Deletion SVD, which recovers the partition at a nearly optimal edge density. The bipartite stochastic block model studied here was used by \cite{feldman2014algorithm} to give a unified algorithm for recovering planted partitions and assignments in random hypergraphs and random $k$-SAT formulae respectively. Our results give the best known bounds for the clause density at which solutions can be found efficiently in these models as well as showing a barrier to further improvement via this reduction to the bipartite block model.