Nelly Litvak - Average nearest neighbor degrees in scale-free networks

The average nearest neighbor degree (ANND) of a node of degree k, as a function of k, is often used to characterize dependencies between degrees of a node and its neighbors. If ANND is increasing (decreasing) in k, then the dependencies are positive (negative). We study the limiting behavior of the ANND in undirected random graphs with i.i.d. regularly varying degree sequences and arbitrary joint degree distribution of neighbor nodes. When degrees have a finite variance, we prove that ANND converges to a deterministic function. In particular, in the configuration model, where nodes are connected at random, this limit is, naturally, a constant. When degrees have infinite variance, we obtain that ANND in the configuration model scales as a positive power of the graph size, up to a slowly varying factor, and we prove the CLT for the ANND. The neutral wiring of the network is reflected in the fact that the limiting distribution is the same for each finite k. The CLT holds for the configuration model represented by a multi-graph, and for the erased configuration model, where self-loops and multiple edges are removed. Our asymptotic results imply that the ANND is uninformative in the infinite variance scenario. Therefore, we propose an alternative measure, the average nearest neighbor rank (ANNR) and prove its convergence to a deterministic function for networks, in which joint degree distributions have finite expectations. 
This is a joint work with Dong Yao and Pim van der Hoorn