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

Nelli Litvak, Remco van der Hofstad

Research output: Book/ReportReportProfessional

18 Downloads (Pure)

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
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages15
Publication statusPublished - Oct 2012

Publication series

NameMemorandum
PublisherDepartment of Applied Mathematics, University of Twente
No.1997
ISSN (Print)1874-4850
ISSN (Electronic)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.