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

摘要

Let p,s ε (0,1] with s> p, let m,n ε N with 1 < m < n, and define V={1,|...,n}. Let ER(n,p) denote the random graph model on V where each edge is independently included in the graph with probability p. Let k(n,p,m,s) denote the random graph model on V where each edge among the m vertices{1,...,m} is independently included in the graph with probability s and all other edges are independently included with probability p. We view graphs from the ER(n,p) model as ‘‘homogeneous’’: the probability of the presence of an edge is the same throughout such a graph. On the other hand, we view a graph generated by the k model as ‘‘anomalous’’; such a graph possesses increas ededge probability among a certain subset of its vertices. Our inference setting is to determine whether an observed graph G is ‘‘homo-geneous’’ (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≤10~(24) while lim_(n→∞)β_?/β_(|E|) < 1.