Average nearest neighbor degrees in scale-free networks

Dong Yao, Pim van der Hoorn, Nelly Litvak

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
35 Downloads (Pure)

Abstract

The average nearest neighbor degree (ANND) of a node of degree k is widely used to measure dependencies between degrees of neighbor nodes in a network. We formally analyze ANND in undirected random graphs when the graph size tends to infinity. The limiting behavior of ANND depends on the variance of the degree distribution. When the variance is finite, the ANND has a deterministic limit. When the variance is infinite, the ANND scales with the size of the graph, and we prove a corresponding central limit theorem in the configuration model (CM, a network with random connections). As ANND proved uninformative in the infinite variance scenario, we propose an alternative measure, the average nearest neighbor rank (ANNR). We prove that ANNR converges to a deterministic function whenever the degree distribution has finite mean. We then consider the erased configuration model (ECM), where self-loops and multiple edges are removed, and investigate the well-known 'structural negative correlations', or `finite-size effects', that arise in simple graphs, such as ECM, because large nodes can only have a limited number of large neighbors. Interestingly, we prove that for any fixed k, ANNR in ECM converges to the same limit as in CM. However, numerical experiments show that finite-size effects occur when k scales with n.
Original languageEnglish
Pages (from-to)1-38
JournalInternet mathematics
Volume2018
DOIs
Publication statusPublished - 10 Jan 2018

Fingerprint

Scale-free Networks
Complex networks
Nearest Neighbor
Configuration
Finite Size Effects
Degree Distribution
Vertex of a graph
Converge
Infinite Variance
Limiting Behavior
Graph in graph theory
Simple Graph
Random Graphs
Undirected Graph
Central limit theorem
Model
Experiments
Numerical Experiment
Infinity
Tend

Cite this

Yao, Dong ; van der Hoorn, Pim ; Litvak, Nelly. / Average nearest neighbor degrees in scale-free networks. In: Internet mathematics. 2018 ; Vol. 2018. pp. 1-38.
@article{bb23ba718f1945bd8f919d4291c156ce,
title = "Average nearest neighbor degrees in scale-free networks",
abstract = "The average nearest neighbor degree (ANND) of a node of degree k is widely used to measure dependencies between degrees of neighbor nodes in a network. We formally analyze ANND in undirected random graphs when the graph size tends to infinity. The limiting behavior of ANND depends on the variance of the degree distribution. When the variance is finite, the ANND has a deterministic limit. When the variance is infinite, the ANND scales with the size of the graph, and we prove a corresponding central limit theorem in the configuration model (CM, a network with random connections). As ANND proved uninformative in the infinite variance scenario, we propose an alternative measure, the average nearest neighbor rank (ANNR). We prove that ANNR converges to a deterministic function whenever the degree distribution has finite mean. We then consider the erased configuration model (ECM), where self-loops and multiple edges are removed, and investigate the well-known 'structural negative correlations', or `finite-size effects', that arise in simple graphs, such as ECM, because large nodes can only have a limited number of large neighbors. Interestingly, we prove that for any fixed k, ANNR in ECM converges to the same limit as in CM. However, numerical experiments show that finite-size effects occur when k scales with n.",
author = "Dong Yao and {van der Hoorn}, Pim and Nelly Litvak",
year = "2018",
month = "1",
day = "10",
doi = "10.24166/im.02.2018",
language = "English",
volume = "2018",
pages = "1--38",
journal = "Internet mathematics",
issn = "1542-7951",
publisher = "Taylor & Francis",

}

Average nearest neighbor degrees in scale-free networks. / Yao, Dong; van der Hoorn, Pim; Litvak, Nelly.

In: Internet mathematics, Vol. 2018, 10.01.2018, p. 1-38.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Average nearest neighbor degrees in scale-free networks

AU - Yao, Dong

AU - van der Hoorn, Pim

AU - Litvak, Nelly

PY - 2018/1/10

Y1 - 2018/1/10

N2 - The average nearest neighbor degree (ANND) of a node of degree k is widely used to measure dependencies between degrees of neighbor nodes in a network. We formally analyze ANND in undirected random graphs when the graph size tends to infinity. The limiting behavior of ANND depends on the variance of the degree distribution. When the variance is finite, the ANND has a deterministic limit. When the variance is infinite, the ANND scales with the size of the graph, and we prove a corresponding central limit theorem in the configuration model (CM, a network with random connections). As ANND proved uninformative in the infinite variance scenario, we propose an alternative measure, the average nearest neighbor rank (ANNR). We prove that ANNR converges to a deterministic function whenever the degree distribution has finite mean. We then consider the erased configuration model (ECM), where self-loops and multiple edges are removed, and investigate the well-known 'structural negative correlations', or `finite-size effects', that arise in simple graphs, such as ECM, because large nodes can only have a limited number of large neighbors. Interestingly, we prove that for any fixed k, ANNR in ECM converges to the same limit as in CM. However, numerical experiments show that finite-size effects occur when k scales with n.

AB - The average nearest neighbor degree (ANND) of a node of degree k is widely used to measure dependencies between degrees of neighbor nodes in a network. We formally analyze ANND in undirected random graphs when the graph size tends to infinity. The limiting behavior of ANND depends on the variance of the degree distribution. When the variance is finite, the ANND has a deterministic limit. When the variance is infinite, the ANND scales with the size of the graph, and we prove a corresponding central limit theorem in the configuration model (CM, a network with random connections). As ANND proved uninformative in the infinite variance scenario, we propose an alternative measure, the average nearest neighbor rank (ANNR). We prove that ANNR converges to a deterministic function whenever the degree distribution has finite mean. We then consider the erased configuration model (ECM), where self-loops and multiple edges are removed, and investigate the well-known 'structural negative correlations', or `finite-size effects', that arise in simple graphs, such as ECM, because large nodes can only have a limited number of large neighbors. Interestingly, we prove that for any fixed k, ANNR in ECM converges to the same limit as in CM. However, numerical experiments show that finite-size effects occur when k scales with n.

U2 - 10.24166/im.02.2018

DO - 10.24166/im.02.2018

M3 - Article

VL - 2018

SP - 1

EP - 38

JO - Internet mathematics

JF - Internet mathematics

SN - 1542-7951

ER -