A comparative power analysis of the maximum degree and size invariants for random graph inference

Our inference setting is to determine whether an observed graph G is “homogeneous” (with some known p) or “anomalous”. In this article, we analyze the statistical power β of the size invariant |E(G)| (the number of edges in the graph) and the maximum degree invariant Δ(G) in detecting such anomalies. In particular, we demonstrate an interesting phenomenon when comparing the powers of these statistics: the limit theory can be at odds with the finite-sample evidence even for astronomically large graphs. For example, under certain values of p,s and m=m(n), we show that the maximum degree statistic is more powerful (βΔ>β|E|) for n⩽1024 while limn→∞βΔ/β|E|<1.