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 -