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

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,Y\ge 0$ 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.

References in corpus (3)

• Systematic Topology Analysis and Generation Using Degree Correlations
• Uncovering disassortativity in large scale-free networks
• Degree-degree correlations in random graphs with heavy-tailed degrees

Cited by in corpus (34)

• Growing multiplex networks
• Fundamentals of spreading processes in single and multilayer complex networks
• Epidemic spreading on complex networks with community structures
• Aggregate Characterization of User Behavior in Twitter and Analysis of the Retweet Graph
• Uncovering disassortativity in large scale-free networks
• Degree-degree correlations in random graphs with heavy-tailed degrees
• Emergence of assortative mixing between clusters of cultured neurons
• Degree correlations in directed scale-free networks
• Disassortativity of percolating clusters in random networks
• Building Damage-Resilient Dominating Sets in Complex Networks against Random and Targeted Attacks
• Higher order assortativity in complex networks
• Hypergraph assortativity: a dynamical systems perspective
• Lower bound of assortativity coefficient in scale-free networks
• Power-law relations in random networks with communities
• A general formulation of long-range degree correlations in complex networks
• Fractality and degree correlations in scale-free networks
• A general model of hierarchical fractal scale-free networks
• Dominating Scale-Free Networks Using Generalized Probabilistic Methods
• Multilayer network analysis to study complex inter-subsystem interactions in a turbulent thermoacoustic system
• Bounds of memory strength for power-law series
• Switchover phenomenon induced by epidemic seeding on geometric networks
• Phase transitions for scaling of structural correlations in directed networks
• Robustness analysis of bimodal networks in the whole range of degree correlation
• Onion under Microscope: An in-depth analysis of the Tor network
• Mechanisms for tuning clustering and degree-correlations in directed networks
• Interplay between tie strength and neighbourhood topology in complex networks: Granovetter's theory and beyond
• Assortativity measures for weighted and directed networks
• Convergence of rank based degree-degree correlations in random directed networks
• Identification of intrinsic long-range degree correlations in complex networks
• Percolation on a maximally disassortative network
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Degree-degree dependencies in directed networks with heavy-tailed degrees
• Diversity of Skills and Collective Intelligence in GitHub
• Networks with degree-degree correlations is a special case of edge-coloured random graphs