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

Let p,s is an element of (0,1] with s > p, let m, n is an element of 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 kappa(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 kappa model as "anomalous": such a graph possesses increased edge probability among a certain subset of its vertices. 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 beta of the size invariant vertical bar E(G)vertical bar (the number of edges in the graph) and the maximum degree invariant, Delta(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 (beta(Delta) > beta(vertical bar E vertical bar)) for n <= 10(24) while lim(n ->infinity)beta(Delta)/beta(vertical bar E vertical bar) < 1. (C) 2010 Elsevier B.V. All rights reserved.