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

Nelli Litvak, Remco van der Hofstad

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 languageUndefined
Place of PublicationEnschede
PublisherDepartment of Applied Mathematics, University of Twente
Number of pages15
StatePublished - Oct 2012

Publication series

NameMemorandum
PublisherDepartment of Applied Mathematics, University of Twente
No.1997
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Fingerprint

Non-negative
Infinite variance
Random variable
Correlation coefficient
Coefficient
Moment
Graph in graph theory
Spearman's coefficient
Power-law distribution
Degree distribution
Random graphs
Joint distribution
Linear combination
Exponent
Converge
Alternatives
Simulation
Model

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: Department of Applied Mathematics, University of Twente.

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

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

Research output: ProfessionalReport

@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",
series = "Memorandum",
publisher = "Department of Applied Mathematics, University of Twente",
number = "1997",

}

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

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

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

Research output: ProfessionalReport

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 - Department of Applied Mathematics, University of Twente

ER -

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