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

Onderzoeksoutput: Boek/rapportRapportAcademic

Uittreksel

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 \emph{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.
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's15
StatusGepubliceerd - 2012

Publicatie series

NaamarXiv.org [math.PR]
Volume1202.3071

Vingerafdruk

Infinite Variance
Random Graphs
Non-negative
Random variable
Correlation coefficient
Coefficient
Moment
Spearman's coefficient
Power-law Distribution
Degree Distribution
Graph in graph theory
Joint Distribution
Linear Combination
Exponent
Converge
Alternatives
Simulation

Citeer dit

@book{850e6b89615c46dd914a9becd4b1878d,
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 \emph{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.",
author = "N. Litvak and {Hofstad, van der}, R.W.",
year = "2012",
language = "English",
series = "arXiv.org [math.PR]",
publisher = "s.n.",

}

Degree-degree correlations in random graphs with heavy-tailed degrees. / Litvak, N.; Hofstad, van der, R.W.

s.n., 2012. 15 blz. (arXiv.org [math.PR]; Vol. 1202.3071).

Onderzoeksoutput: Boek/rapportRapportAcademic

TY - BOOK

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

AU - Litvak, N.

AU - Hofstad, van der, R.W.

PY - 2012

Y1 - 2012

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 \emph{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 \emph{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.

UR - http://arxiv.org/pdf/1202.3071

M3 - Report

T3 - arXiv.org [math.PR]

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

PB - s.n.

ER -