Degree correlations in scale-free random graph models

DOI10.1017/JPR.2019.45MaRDI QIDQ5235048zbMATH OpenOpenAlexFDO

Authors Clara Stegehuis

Publication date 7 October 2019

Published in Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

degree correlationsrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05)

Abstract: We study the average nearest neighbor degree $a(k)$ of vertices with degree $k$. In many real-world networks with power-law degree distribution $a(k)$ falls off in $k$, a property ascribed to the constraint that any two vertices are connected by at most one edge. We show that $a(k)$ indeed decays in $k$ in three simple random graph null models with power-law degrees: the erased configuration model, the rank-1 inhomogeneous random graph and the hyperbolic random graph. We consider the large-network limit when the number of nodes $n$ tends to infinity. We find for all three null models that $a(k)$ starts to decay beyond $n^{(au-2)/(au-1)}$ and then settles on a power law $a(k)sim{k}^{au-3}$, with $au$ the degree exponent.

Recommendations

• scientific article; zbMATH DE number 5763194
• Degree distribution of a scale-free random graph model
• Random degree -- degree correlated networks
• Scale-free property for degrees and weights in an \(N\)-interactions random graph model
• Large degrees in scale-free inhomogeneous random graphs
• The correlation of the degrees of Bernoulli random graphs
• On degree-degree correlations in multilayer networks
• The degree sequences and spectra of scale-free random graphs
• Scale-free property for degrees and weights in a preferential attachment random graph model

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A simple solution to the k‐core problem
• Clustering and the hyperbolic geometry of complex networks
• Continuum limit of critical inhomogeneous random graphs
• Distances in random graphs with finite variance degrees
• Generating simple random graphs with prescribed degree distribution
• Hierarchical organization of modularity in complex networks
• scientific article; zbMATH DE number 5004850 (Why is no real title available?)
• scientific article; zbMATH DE number 486467 (Why is no real title available?)
• scientific article; zbMATH DE number 5070369 (Why is no real title available?)
• Limit theorems for assortativity and clustering in null models for scale-free networks
• Mixed degree-degree correlations in directed social networks
• Network science. With Márton Pósfai
• On the largest component of a hyperbolic model of complex networks
• On the two-body permutation-parity combinatorial transformation
• Optimal subgraph structures in scale-free configuration models
• Random graphs and complex networks. Volume 1
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Sampling geometric inhomogeneous random graphs in linear time
• Stability criteria and localization of the matrix spectrum in terms of trace functions
• The average distances in random graphs with given expected degrees
• The probability of connectivity in a hyperbolic model of complex networks
• Universality for critical heavy-tailed network models: metric structure of maximal components
• Universality for first passage percolation on sparse random graphs
• Universality for the distance in finite variance random graphs
• Upper bounds for number of removed edges in the erased configuration model

Cited in

(21)

• Degree distribution and assortativity in line graphs of complex networks
• Triadic closure in configuration models with unbounded degree fluctuations
• Degree distribution of a scale-free random graph model
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Large degrees in scale-free inhomogeneous random graphs
• Optimal subgraph structures in scale-free configuration models
• Asymptotics for cliques in scale-free random graphs
• Degrees in random self-similar bipolar networks
• Random degree -- degree correlated networks
• scientific article; zbMATH DE number 5139256 (Why is no real title available?)
• Upper bounds for number of removed edges in the erased configuration model
• scientific article; zbMATH DE number 5763194 (Why is no real title available?)
• Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees
• Limit theorems for assortativity and clustering in null models for scale-free networks
• Networks with degree–degree correlations are special cases of the edge-coloured random graph
• The correlation of the degrees of Bernoulli random graphs
• An ensemble of random graphs with identical degree distribution
• Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph
• Relations between scaling exponents in unimodular random graphs
• Large deviations for subgraphs in inhomogeneous random graphs
• Counting triangles in power-law uniform random graphs

Describes a project that uses

Uses Software

• SNAP

This page was built for publication: Degree correlations in scale-free random graph models

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