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

DOI10.1080/15427951.2013.850455MaRDI QIDQ4985358zbMATH OpenOpenAlexFDO

Authors Remco van der Hofstad, Nelly Litvak

Publication date 23 April 2021

Published in Internet Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

disassortative networksassortative networks

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

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)