Consistency of adjacency spectral embedding for the mixed membership stochastic blockmodel
Consistency of adjacency spectral embedding for the mixed membership stochastic blockmodel
复制标题
DOI：
--
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Patrick Rubin-Delanchy;C. Priebe;M. Tang
中科院分区：
文献类型：
--
作者：
Patrick Rubin-Delanchy;C. Priebe;M. Tang
混合隶属随机块模型是一种图的统计模型，它通过允许每个节点在每次决定是否形成边时随机选择不同的社区来扩展随机块模型。尽管随机块模型的谱分析日益完善，但混合隶属度情况的理论却相当不发达。在这里，我们展示了将邻接谱嵌入到 $\mathbb{R}^k$ 中，然后将包围凸 $k$-多胞体的最小体积拟合到 $k-1$ 主成分，从而得到 $k$-社区混合成员资格随机块模型的一致估计。关键是找到混合隶属随机块模型和随机点积图之间的直接对应关系，这极大地方便了理论分析。具体来说，利用随机点积图的 $2 \rightarrow \infty$ 范数和中心极限定理来分别显示一致性并部分纠正过程的偏差。
The mixed membership stochastic blockmodel is a statistical model for a graph, which extends the stochastic blockmodel by allowing every node to randomly choose a different community each time a decision of whether to form an edge is made. Whereas spectral analysis for the stochastic blockmodel is increasingly well established, theory for the mixed membership case is considerably less developed. Here we show that adjacency spectral embedding into $\mathbb{R}^k$, followed by fitting the minimum volume enclosing convex $k$-polytope to the $k-1$ principal components, leads to a consistent estimate of a $k$-community mixed membership stochastic blockmodel. The key is to identify a direct correspondence between the mixed membership stochastic blockmodel and the random dot product graph, which greatly facilitates theoretical analysis. Specifically, a $2 \rightarrow \infty$ norm and central limit theorem for the random dot product graph are exploited to respectively show consistency and partially correct the bias of the procedure.