论文标题
组合 - 培养基权衡折衷：随机块模型中的社区属性测试
Combinatorial-Probabilistic Trade-Off: Community Properties Test in the Stochastic Block Models
论文作者
论文摘要
在本文中，我们提出了一个推论框架测试随机块模型的一般社区组合特性。我们没有估计社区作业，而是旨在检验有关某个社区财产是否满足的假设。例如，我们建议测试给定的一组节点是否属于同一社区，或者不同的网络社区是否具有相同的大小。我们提出了一个可以应用于所有对称社区属性的一般推理框架。为了缓解社区特性的组合性质所带来的挑战，我们开发了一种新颖的阴影引导测试方法。通过利用对称性，我们的方法可以找到真实分配的阴影代表，并且可以大大减少在替代方案中测试的分配数量。从理论上讲，我们在两个社区阶层之间介绍了组合距离，并在社区属性测试中显示了组合培养基的权衡现象。我们的测试是诚实的，只要两个社区之间的组合距离的产物和两个分配概率之间的概率距离足够大。另一方面，我们表明，社区房地产测试的信息理论下限也存在这种权衡。我们还在合成数据和蛋白质相互作用应用上实施数值实验，以显示我们方法的有效性。
In this paper, we propose an inferential framework testing the general community combinatorial properties of the stochastic block model. Instead of estimating the community assignments, we aim to test the hypothesis on whether a certain community property is satisfied. For instance, we propose to test whether a given set of nodes belong to the same community or whether different network communities have the same size. We propose a general inference framework that can be applied to all symmetric community properties. To ease the challenges caused by the combinatorial nature of communities properties, we develop a novel shadowing bootstrap testing method. By utilizing the symmetry, our method can find a shadowing representative of the true assignment and the number of assignments to be tested in the alternative can be largely reduced. In theory, we introduce a combinatorial distance between two community classes and show a combinatorial-probabilistic trade-off phenomenon in the community properties test. Our test is honest as long as the product of combinatorial distance between two communities and the probabilistic distance between two assignment probabilities is sufficiently large. On the other hand, we shows that such trade-off also exists in the information-theoretic lower bound of the community property test. We also implement numerical experiments on both the synthetic data and the protein interaction application to show the validity of our method.
