Nearest neighbor degree and finite size effects in scale-free networks

Dependencies between the degree of a node and its neighbors, known as degree-degree correlations, or network assortativity, affect many important properties of networks, e.g. their robustness to attacks and spreading processes. In this talk I will focus a commonly used correlation measure – the average nearest neighbor degree (ANND). ANND is the average degree of neighbors of a node with degree k, as a function of k. I will discuss convergence properties of the ANND as the graph size goes to infinity, and its limitations. In particular, in the infinite variance scenario ANND fails to converge to a deterministic function but obeys a stable-law CLT. As a remedy to this, we propose a new correlation measure, the average nearest neighbor rank (ANNR), and prove its point-wise convergence to a deterministic function. Under the condition that the graph is simple, physics literature often mentions `finite-size effects’ or `structural correlations’. Such effects arise in a simple graph because large nodes can have only limited number of large neighbors. Using the example of the erased configuration model (ECM), we prove that most of the convergence results for the ANNR remain to hold in the ECM, but we do observe interesting finite-side effects for very large k. I will devote part of the talk to numerical results and open questions.