# Degree-degree correlations in random graphs with heavy-tailed degrees

Nelli Litvak, Remco van der Hofstad

Research output: Book/ReportReportProfessional

### Abstract

We investigate degree-degree correlations for scale-free graph sequences. The main conclusion of this paper is that the assortativity coefficient is not the appropriate way to describe degree-dependences in scale-free random graphs. Indeed, we study the infinite volume limit of the assortativity coefficient, and show that this limit is always non-negative when the degrees have finite first but infinite third moment, i.e., when the degree exponent $\gamma + 1$ of the density satisfies $\gamma \in (1,3)$. More generally, our results show that the correlation coefficient is inappropriate to describe dependencies between random variables having infinite variance. We start with a simple model of the sample correlation of random variables $X$ and $Y$, which are linear combinations with non-negative coefficients of the same infinite variance random variables. In this case, the correlation coefficient of $X$ and $Y$ is not defined, and the sample covariance converges to a proper random variable with support that is a subinterval of $(-1,1)$. Further, for any joint distribution $(X,Y)$ with equal marginals being non-negative power-law distributions with infinite variance (as in the case of degree-degree correlations), we show that the limit is non-negative. We next adapt these results to the assortativity in networks as described by the degree-degree correlation coefficient, and show that it is non-negative in the large graph limit when the degree distribution has an infinite third moment. We illustrate these results with several examples where the assortativity behaves in a non-sensible way. We further discuss alternatives for describing assortativity in networks based on rank correlations that are appropriate for infinite variance variables. We support these mathematical results by simulations.
Original language Undefined Enschede University of Twente, Department of Applied Mathematics 15 Published - Oct 2012

### Publication series

Name Memorandum Department of Applied Mathematics, University of Twente 1997 1874-4850 1874-4850

### Keywords

• Multivariate extremes
• METIS-289756
• Dependencies of heavy-tailed random variables
• Degree-degree correlations
• Assortativity
• Scale-free graphs
• IR-84367
• EWI-22428
• Power laws

### Cite this

Litvak, N., & van der Hofstad, R. (2012). Degree-degree correlations in random graphs with heavy-tailed degrees. (Memorandum; No. 1997). Enschede: University of Twente, Department of Applied Mathematics.
Litvak, Nelli ; van der Hofstad, Remco. / Degree-degree correlations in random graphs with heavy-tailed degrees. Enschede : University of Twente, Department of Applied Mathematics, 2012. 15 p. (Memorandum; 1997).
@book{62a108b0f2b84497bf0ddcf8ec6d0ba9,
title = "Degree-degree correlations in random graphs with heavy-tailed degrees",
abstract = "We investigate degree-degree correlations for scale-free graph sequences. The main conclusion of this paper is that the assortativity coefficient is not the appropriate way to describe degree-dependences in scale-free random graphs. Indeed, we study the infinite volume limit of the assortativity coefficient, and show that this limit is always non-negative when the degrees have finite first but infinite third moment, i.e., when the degree exponent $\gamma + 1$ of the density satisfies $\gamma \in (1,3)$. More generally, our results show that the correlation coefficient is inappropriate to describe dependencies between random variables having infinite variance. We start with a simple model of the sample correlation of random variables $X$ and $Y$, which are linear combinations with non-negative coefficients of the same infinite variance random variables. In this case, the correlation coefficient of $X$ and $Y$ is not defined, and the sample covariance converges to a proper random variable with support that is a subinterval of $(-1,1)$. Further, for any joint distribution $(X,Y)$ with equal marginals being non-negative power-law distributions with infinite variance (as in the case of degree-degree correlations), we show that the limit is non-negative. We next adapt these results to the assortativity in networks as described by the degree-degree correlation coefficient, and show that it is non-negative in the large graph limit when the degree distribution has an infinite third moment. We illustrate these results with several examples where the assortativity behaves in a non-sensible way. We further discuss alternatives for describing assortativity in networks based on rank correlations that are appropriate for infinite variance variables. We support these mathematical results by simulations.",
keywords = "Multivariate extremes, METIS-289756, Dependencies of heavy-tailed random variables, Degree-degree correlations, Assortativity, Scale-free graphs, IR-84367, EWI-22428, Power laws",
author = "Nelli Litvak and {van der Hofstad}, Remco",
note = "arXiv:1202.307/1v3 [math.PR]",
year = "2012",
month = "10",
language = "Undefined",
series = "Memorandum",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1997",

}

Litvak, N & van der Hofstad, R 2012, Degree-degree correlations in random graphs with heavy-tailed degrees. Memorandum, no. 1997, University of Twente, Department of Applied Mathematics, Enschede.

Degree-degree correlations in random graphs with heavy-tailed degrees. / Litvak, Nelli; van der Hofstad, Remco.

Enschede : University of Twente, Department of Applied Mathematics, 2012. 15 p. (Memorandum; No. 1997).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Degree-degree correlations in random graphs with heavy-tailed degrees

AU - Litvak, Nelli

AU - van der Hofstad, Remco

N1 - arXiv:1202.307/1v3 [math.PR]

PY - 2012/10

Y1 - 2012/10

N2 - We investigate degree-degree correlations for scale-free graph sequences. The main conclusion of this paper is that the assortativity coefficient is not the appropriate way to describe degree-dependences in scale-free random graphs. Indeed, we study the infinite volume limit of the assortativity coefficient, and show that this limit is always non-negative when the degrees have finite first but infinite third moment, i.e., when the degree exponent $\gamma + 1$ of the density satisfies $\gamma \in (1,3)$. More generally, our results show that the correlation coefficient is inappropriate to describe dependencies between random variables having infinite variance. We start with a simple model of the sample correlation of random variables $X$ and $Y$, which are linear combinations with non-negative coefficients of the same infinite variance random variables. In this case, the correlation coefficient of $X$ and $Y$ is not defined, and the sample covariance converges to a proper random variable with support that is a subinterval of $(-1,1)$. Further, for any joint distribution $(X,Y)$ with equal marginals being non-negative power-law distributions with infinite variance (as in the case of degree-degree correlations), we show that the limit is non-negative. We next adapt these results to the assortativity in networks as described by the degree-degree correlation coefficient, and show that it is non-negative in the large graph limit when the degree distribution has an infinite third moment. We illustrate these results with several examples where the assortativity behaves in a non-sensible way. We further discuss alternatives for describing assortativity in networks based on rank correlations that are appropriate for infinite variance variables. We support these mathematical results by simulations.

AB - We investigate degree-degree correlations for scale-free graph sequences. The main conclusion of this paper is that the assortativity coefficient is not the appropriate way to describe degree-dependences in scale-free random graphs. Indeed, we study the infinite volume limit of the assortativity coefficient, and show that this limit is always non-negative when the degrees have finite first but infinite third moment, i.e., when the degree exponent $\gamma + 1$ of the density satisfies $\gamma \in (1,3)$. More generally, our results show that the correlation coefficient is inappropriate to describe dependencies between random variables having infinite variance. We start with a simple model of the sample correlation of random variables $X$ and $Y$, which are linear combinations with non-negative coefficients of the same infinite variance random variables. In this case, the correlation coefficient of $X$ and $Y$ is not defined, and the sample covariance converges to a proper random variable with support that is a subinterval of $(-1,1)$. Further, for any joint distribution $(X,Y)$ with equal marginals being non-negative power-law distributions with infinite variance (as in the case of degree-degree correlations), we show that the limit is non-negative. We next adapt these results to the assortativity in networks as described by the degree-degree correlation coefficient, and show that it is non-negative in the large graph limit when the degree distribution has an infinite third moment. We illustrate these results with several examples where the assortativity behaves in a non-sensible way. We further discuss alternatives for describing assortativity in networks based on rank correlations that are appropriate for infinite variance variables. We support these mathematical results by simulations.

KW - Multivariate extremes

KW - METIS-289756

KW - Dependencies of heavy-tailed random variables

KW - Degree-degree correlations

KW - Assortativity

KW - Scale-free graphs

KW - IR-84367

KW - EWI-22428

KW - Power laws

M3 - Report

T3 - Memorandum

BT - Degree-degree correlations in random graphs with heavy-tailed degrees

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Litvak N, van der Hofstad R. Degree-degree correlations in random graphs with heavy-tailed degrees. Enschede: University of Twente, Department of Applied Mathematics, 2012. 15 p. (Memorandum; 1997).