Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees

Remco van der Hofstad, Nelly Litvak

Research output: Contribution to journalArticleAcademicpeer-review

11 Citations (Scopus)
38 Downloads (Pure)

Abstract

Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, social, and biological networks are often characterized by degree-degree dependencies between neighboring nodes. In assortative networks, the degree-degree dependencies are positive (nodes with similar degrees tend to connect to each other), whereas in disassortative networks, these dependencies are negative. One of the problems with the commonly used Pearson correlation coefficient, also known as the assortativity coefficient, is that its magnitude decreases with the network size in disassortative networks. This makes it impossible to compare mixing patterns, for example, in two web crawls of different sizes. As an alternative, we have recently suggested to use rank correlation measures, such as Spearman’s rho. Numerical experiments have confirmed that Spearman’s rho produces consistent values in graphs of different sizes but similar structure, and it is able to reveal strong (positive or negative) dependencies in large graphs. In this study we analytically investigate degree-degree dependencies for scale-free graph sequences. In order to demonstrate the ill behavior of the Pearson’s correlation coefficient, we first study a simple model of two heavy-tailed, highly correlated, Color versions of one or more of the figures in the article can be found online at random variables $X$ and $Y$, and show that the sample correlation coefficient converges in distribution either to a proper random variable on $[−1, 1]$, or to zero, and the limit is nonnegative a.s. if $X, Y \geq 0$. We next adapt these results to the degree-degree dependencies in networks as described by the Pearson correlation coefficient, and show that it is nonnegative in the large graph limit when the asymptotic degree distribution has an infinite third moment. Furthermore, we provide examples where in the Pearson’s correlation coefficient converges to zero in a network with strong negative degree-degree dependencies, and another example where this coefficient converges in distribution to a random variable. We suggest an alternative degree-degree dependency measure, based on Spearman’s rho, and prove that this statistical estimator converges to an appropriate limit under quite general conditions. These conditions are proved to be satisfied in common network models, such as the configuration model and the preferential attachment model. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.
Original languageEnglish
Pages (from-to)287-334
Number of pages48
JournalInternet mathematics
Volume10
Issue number3-4
DOIs
Publication statusPublished - 15 Sep 2014

Fingerprint

Random Graphs
Random variables
Pearson Correlation
Correlation coefficient
Spearman's rho
Converge
Spearman's coefficient
Random variable
Graph in graph theory
World Wide Web
Non-negative
Internet
Color
Preferential Attachment
Alternatives
Biological Networks
Zero
Degree Distribution
Coefficient
Self-organizing

Keywords

  • EWI-25080
  • IR-91879
  • METIS-306033

Cite this

van der Hofstad, Remco ; Litvak, Nelly. / Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees. In: Internet mathematics. 2014 ; Vol. 10, No. 3-4. pp. 287-334.
@article{56cdc8cc07904ccf831657eb7669464f,
title = "Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees",
abstract = "Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, social, and biological networks are often characterized by degree-degree dependencies between neighboring nodes. In assortative networks, the degree-degree dependencies are positive (nodes with similar degrees tend to connect to each other), whereas in disassortative networks, these dependencies are negative. One of the problems with the commonly used Pearson correlation coefficient, also known as the assortativity coefficient, is that its magnitude decreases with the network size in disassortative networks. This makes it impossible to compare mixing patterns, for example, in two web crawls of different sizes. As an alternative, we have recently suggested to use rank correlation measures, such as Spearman’s rho. Numerical experiments have confirmed that Spearman’s rho produces consistent values in graphs of different sizes but similar structure, and it is able to reveal strong (positive or negative) dependencies in large graphs. In this study we analytically investigate degree-degree dependencies for scale-free graph sequences. In order to demonstrate the ill behavior of the Pearson’s correlation coefficient, we first study a simple model of two heavy-tailed, highly correlated, Color versions of one or more of the figures in the article can be found online at random variables $X$ and $Y$, and show that the sample correlation coefficient converges in distribution either to a proper random variable on $[−1, 1]$, or to zero, and the limit is nonnegative a.s. if $X, Y \geq 0$. We next adapt these results to the degree-degree dependencies in networks as described by the Pearson correlation coefficient, and show that it is nonnegative in the large graph limit when the asymptotic degree distribution has an infinite third moment. Furthermore, we provide examples where in the Pearson’s correlation coefficient converges to zero in a network with strong negative degree-degree dependencies, and another example where this coefficient converges in distribution to a random variable. We suggest an alternative degree-degree dependency measure, based on Spearman’s rho, and prove that this statistical estimator converges to an appropriate limit under quite general conditions. These conditions are proved to be satisfied in common network models, such as the configuration model and the preferential attachment model. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.",
keywords = "EWI-25080, IR-91879, METIS-306033",
author = "{van der Hofstad}, Remco and Nelly Litvak",
note = "eemcs-eprint-25080",
year = "2014",
month = "9",
day = "15",
doi = "10.1080/15427951.2013.850455",
language = "English",
volume = "10",
pages = "287--334",
journal = "Internet mathematics",
issn = "1542-7951",
publisher = "Taylor & Francis",
number = "3-4",

}

Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees. / van der Hofstad, Remco; Litvak, Nelly.

In: Internet mathematics, Vol. 10, No. 3-4, 15.09.2014, p. 287-334.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees

AU - van der Hofstad, Remco

AU - Litvak, Nelly

N1 - eemcs-eprint-25080

PY - 2014/9/15

Y1 - 2014/9/15

N2 - Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, social, and biological networks are often characterized by degree-degree dependencies between neighboring nodes. In assortative networks, the degree-degree dependencies are positive (nodes with similar degrees tend to connect to each other), whereas in disassortative networks, these dependencies are negative. One of the problems with the commonly used Pearson correlation coefficient, also known as the assortativity coefficient, is that its magnitude decreases with the network size in disassortative networks. This makes it impossible to compare mixing patterns, for example, in two web crawls of different sizes. As an alternative, we have recently suggested to use rank correlation measures, such as Spearman’s rho. Numerical experiments have confirmed that Spearman’s rho produces consistent values in graphs of different sizes but similar structure, and it is able to reveal strong (positive or negative) dependencies in large graphs. In this study we analytically investigate degree-degree dependencies for scale-free graph sequences. In order to demonstrate the ill behavior of the Pearson’s correlation coefficient, we first study a simple model of two heavy-tailed, highly correlated, Color versions of one or more of the figures in the article can be found online at random variables $X$ and $Y$, and show that the sample correlation coefficient converges in distribution either to a proper random variable on $[−1, 1]$, or to zero, and the limit is nonnegative a.s. if $X, Y \geq 0$. We next adapt these results to the degree-degree dependencies in networks as described by the Pearson correlation coefficient, and show that it is nonnegative in the large graph limit when the asymptotic degree distribution has an infinite third moment. Furthermore, we provide examples where in the Pearson’s correlation coefficient converges to zero in a network with strong negative degree-degree dependencies, and another example where this coefficient converges in distribution to a random variable. We suggest an alternative degree-degree dependency measure, based on Spearman’s rho, and prove that this statistical estimator converges to an appropriate limit under quite general conditions. These conditions are proved to be satisfied in common network models, such as the configuration model and the preferential attachment model. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.

AB - Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, social, and biological networks are often characterized by degree-degree dependencies between neighboring nodes. In assortative networks, the degree-degree dependencies are positive (nodes with similar degrees tend to connect to each other), whereas in disassortative networks, these dependencies are negative. One of the problems with the commonly used Pearson correlation coefficient, also known as the assortativity coefficient, is that its magnitude decreases with the network size in disassortative networks. This makes it impossible to compare mixing patterns, for example, in two web crawls of different sizes. As an alternative, we have recently suggested to use rank correlation measures, such as Spearman’s rho. Numerical experiments have confirmed that Spearman’s rho produces consistent values in graphs of different sizes but similar structure, and it is able to reveal strong (positive or negative) dependencies in large graphs. In this study we analytically investigate degree-degree dependencies for scale-free graph sequences. In order to demonstrate the ill behavior of the Pearson’s correlation coefficient, we first study a simple model of two heavy-tailed, highly correlated, Color versions of one or more of the figures in the article can be found online at random variables $X$ and $Y$, and show that the sample correlation coefficient converges in distribution either to a proper random variable on $[−1, 1]$, or to zero, and the limit is nonnegative a.s. if $X, Y \geq 0$. We next adapt these results to the degree-degree dependencies in networks as described by the Pearson correlation coefficient, and show that it is nonnegative in the large graph limit when the asymptotic degree distribution has an infinite third moment. Furthermore, we provide examples where in the Pearson’s correlation coefficient converges to zero in a network with strong negative degree-degree dependencies, and another example where this coefficient converges in distribution to a random variable. We suggest an alternative degree-degree dependency measure, based on Spearman’s rho, and prove that this statistical estimator converges to an appropriate limit under quite general conditions. These conditions are proved to be satisfied in common network models, such as the configuration model and the preferential attachment model. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.

KW - EWI-25080

KW - IR-91879

KW - METIS-306033

U2 - 10.1080/15427951.2013.850455

DO - 10.1080/15427951.2013.850455

M3 - Article

VL - 10

SP - 287

EP - 334

JO - Internet mathematics

JF - Internet mathematics

SN - 1542-7951

IS - 3-4

ER -