### Abstract

Original language | English |
---|---|

Pages (from-to) | 287-334 |

Number of pages | 48 |

Journal | Internet mathematics |

Volume | 10 |

Issue number | 3-4 |

DOIs | |

Publication status | Published - 15 Sep 2014 |

### Fingerprint

### Keywords

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

### Cite this

*Internet mathematics*,

*10*(3-4), 287-334. https://doi.org/10.1080/15427951.2013.850455

}

*Internet mathematics*, vol. 10, no. 3-4, pp. 287-334. https://doi.org/10.1080/15427951.2013.850455

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

Research output: Contribution to journal › Article › Academic › peer-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 -