We connect two random graph models, the Popularity Adjusted Block Model (PABM) and the Generalized Random Dot Product Graph (GRDPG), by demonstrating that the PABM is a special case of the GRDPG in which communities correspond to mutually orthogonal subspaces of latent vectors. This insight allows us to construct new algorithms for community detection and parameter estimation for the PABM, as well as improve an existing algorithm that relies on Sparse Subspace Clustering. Using established asymptotic properties of Adjacency Spectral Embedding for the GRDPG, we derive asymptotic properties of these algorithms. In particular, we demonstrate that the absolute number of community detection errors tends to zero as the number of graph vertices tends to infinity. Simulation experiments illustrate these properties.
翻译:我们连接了两个随机图表模型,即大众调整区块模型(PABM)和通用随机点产品图(GRDPG),通过证明PABM是GRDPG的一个特例,其中社区与潜向矢量的正对分空间相对应。这种洞察使我们能够为PABM建立社区探测和参数估计的新算法,并改进依靠微粒子空间组合的现有算法。我们利用GRDPG相邻相光嵌嵌的既定无光特性,得出这些算法的无光特性。特别是,我们证明社区探测错误的绝对数为零,因为图形脊椎的数量往往不尽。模拟实验说明了这些特性。