Optimal adaptivity of signed-polygon statistics for network testing
Optimal adaptivity of signed-polygon statistics for network testing
复制标题
DOI：
10.1214/21-aos2089
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Jiashun Jin;Z. Ke;Shengming Luo
中科院分区：
文献类型：
--
作者：
Jiashun Jin;Z. Ke;Shengming Luo
给定一个对称的社交网络，我们有兴趣测试它是只有一个社区还是多个社区。所需的测试应该（a）适应严重程度的异质性，（B）适应混合成员，（c）有一个易处理的零分布，（d）自动适应不同水平的稀疏性，并实现最佳相图。如何找到这样的测试是一个具有挑战性的问题。我们提出了一个新的测试类的签署多边形。固定$m \geq 3$，对于网络中的每个$m$-gon，使用中心邻接矩阵定义得分。这些分数的总和就是$m$阶有符号多边形统计量。符号三角形（SgnT）和符号四边形（SgnQ）是符号多边形的特殊例子。我们证明了SgnT和SgnQ测试都满足（a）-（d），特别是，它们对于非常稀疏和不太稀疏的网络都很有效。我们提出的测试与现有的测试相比，毫不逊色。例如，EZ和GC测试在稀疏度较低的情况下表现得不令人满意，并且没有实现最佳相图。此外，许多现有的测试不允许严重的异质性或混合成员，它们在我们的设置中表现得不令人满意。对SgnT和SgnQ测试的分析是微妙的，并且非常繁琐，主要原因是我们需要一个统一的证明，该证明涵盖了广泛的稀疏性水平和广泛的度异质性。对于下界理论，我们使用一个相变框架，它包括标准的极小极大参数，但信息量更大。证明使用了关于矩阵缩放的经典定理。
Given a symmetric social network, we are interested in testing whether it has only one community or multiple communities. The desired tests should (a) accommodate severe degree heterogeneity, (b) accommodate mixed-memberships, (c) have a tractable null distribution, and (d) adapt automatically to different levels of sparsity, and achieve the optimal phase diagram. How to find such a test is a challenging problem. We propose the Signed Polygon as a class of new tests. Fixing $m \geq 3$, for each $m$-gon in the network, define a score using the centered adjacency matrix. The sum of such scores is then the $m$-th order Signed Polygon statistic. The Signed Triangle (SgnT) and the Signed Quadrilateral (SgnQ) are special examples of the Signed Polygon. We show that both the SgnT and SgnQ tests satisfy (a)-(d), and especially, they work well for both very sparse and less sparse networks. Our proposed tests compare favorably with the existing tests. For example, the EZ and GC tests behave unsatisfactorily in the less sparse case and do not achieve the optimal phase diagram. Also, many existing tests do not allow for severe heterogeneity or mixed-memberships, and they behave unsatisfactorily in our settings. The analysis of the SgnT and SgnQ tests is delicate and extremely tedious, and the main reason is that we need a unified proof that covers a wide range of sparsity levels and a wide range of degree heterogeneity. For lower bound theory, we use a phase transition framework, which includes the standard minimax argument, but is more informative. The proof uses classical theorems on matrix scaling.