Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees

DOI10.1080/15427951.2013.850455zbMATH Open1465.05167arXiv1202.3071OpenAlexW2097625489MaRDI QIDQ4985358FDOQ4985358

Authors: Remco van der Hofstad, Nelly Litvak 

Publication date: 23 April 2021

Published in: Internet Mathematics (Search for Journal in Brave)

Abstract: Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, social and biological networks are often characterized by degree-degree {dependencies} between neighbouring nodes. One of the problems with the commonly used Pearson's correlation coefficient (termed as the assortativity coefficient) is that {in disassortative networks its magnitude decreases} with the network size. This makes it impossible to compare mixing patterns, for example, in two web crawls of different size. We start with a simple model of two heavy-tailed highly correlated random variable $X$ and $Y$, and show that the sample correlation coefficient converges in distribution either to a proper random variable on $[-1,1]$, or to zero, and if $X,Yge0$ then the limit is non-negative. We next show that it is non-negative in the large graph limit when the degree distribution has an infinite third moment. We consider the alternative degree-degree dependency measure, based on the Spearman's rho, and prove that it converges to an appropriate limit under very general conditions. We verify that these conditions hold in common network models, such as configuration model and Preferential Attachment model. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.

Full work available at URL: https://arxiv.org/abs/1202.3071

Recommendations

• Degree-degree dependencies in directed networks with heavy-tailed degrees
• scientific article; zbMATH DE number 3847442
• Extreme degrees in random graphs
• Large degrees in scale-free inhomogeneous random graphs
• Degree correlations in scale-free random graph models
• On the degree properties of generalized random graphs
• Degree distributions in general random intersection graphs
• Directed random graphs with given degree distributions
• The degree distribution of the random multigraphs
• Some remarks about extreme degrees in a random graph

zbMATH Keywords

disassortative networksassortative networks

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07)

Cites Work

• Statistical mechanics of complex networks
• A NEW MEASURE OF RANK CORRELATION
• The Structure and Function of Complex Networks
• Probability Inequalities for Sums of Bounded Random Variables
• On rank correlation measures for non-continuous random variables
• Computing the nonnull asymptotic variance and the asymptotic relative efficiency of Spearman's rank correlation
• A critical point for random graphs with a given degree sequence
• Heavy-Tail Phenomena
• Networks. An introduction.
• Title not available (Why is that?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The degree sequence of a scale-free random graph process
• Random graphs.
• Critical behavior in inhomogeneous random graphs
• Random graph dynamics
• The probability that a random multigraph is simple
• Weighted sums of certain dependent random variables
• The asymptotic number of labeled graphs with given degree sequences
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• A Brief History of Generative Models for Power Law and Lognormal Distributions
• Mixing patterns and community structure in networks
• Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications
• An inner-outer iteration for computing PageRank
• Copulas: Tales and facts (with discussion)
• On the properties of some nonparametric concordance measures in the discrete case
• Using Polynomial Chaos to Compute the Influence of Multiple Random Surfers in the PageRank Model
• On Local Estimations of PageRank: A Mean Field Approach
• The Statistical Mechanics of Complex Product Development: Empirical and Analytical Results

Cited In (13)

• Convergence of rank based degree-degree correlations in random directed networks
• Networks with degree–degree correlations are special cases of the edge-coloured random graph
• Degree-degree dependencies in directed networks with heavy-tailed degrees
• Optimal subgraph structures in scale-free configuration models
• Higher order assortativity in complex networks
• Extreme degrees in random graphs
• Generating maximally disassortative graphs with given degree distribution
• Assortativity and Bidegree Distributions on Bernoulli Random Graph Superpositions
• Assortativity and bidegree distributions on Bernoulli random graph superpositions
• Large degrees in scale-free inhomogeneous random graphs
• Limit theorems for assortativity and clustering in null models for scale-free networks
• Nonuniversality of weighted random graphs with infinite variance degree
• Hypergraph assortativity: a dynamical systems perspective

Uses Software

• WebGraph

This page was built for publication: Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4985358)