Statistical analysis of network structure: A cautionary tale

Igor Smolyarenko (Brunel University)

It is well-known that degrees of nodes belonging to the same network exhibit correlations. However, empirical determination of degree distribution of a given network usually relies on the assumption that a collection of degrees harvested from a large network can be viewed as a sample from a marginal distribution of node degrees, relying on the fact that these correlations are typically weak. We show that in most cases this assumption is unwarranted. For example, in both Erdos-Renyi and Barabasi-Albert networks the distribution of the Kolmogorov-Smirnov distance obtained from a single instance of a network is finitely different from the universal form. Furthermore, even the sign of the effect is not universal. Hence some a priori knowledge of the structure of the network is required to apply statistical hypothesis testing methods, defeating the use of degree distribution as a diagnostic of the structure, as is commonly done when, for example, inferring scale-free property from observed power-law distribution of degrees.