Generating maximally disassortative graphs with given degree distribution

DOI10.1287/STSY.2017.0006MaRDI QIDQ5113876zbMATH OpenOpenAlexFDO

Authors Pim Van der Hoorn, Liudmila Ostroumova Prokhorenkova, Egor Samosvat

Publication date 18 June 2020

Published in Stochastic Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

random graphsdegree distributiondisassortativitydegree-degree correlation

Mathematics Subject Classification ID

Measures of association (correlation, canonical correlation, etc.) (62H20) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: In this paper we consider the optimization problem of generating graphs with a prescribed degree distribution, such that the correlation between the degrees of connected nodes, as measured by Spearman's rho, is minimal. We provide an algorithm for solving this problem and obtain a complete characterization of the joint degree distribution in these maximally disassortative graphs, in terms of the size-biased degree distribution. As a result we get a lower bound for Spearman's rho on graphs with an arbitrary given degree distribution. We use this lower bound to show that for any fixed tail exponent, there exist scale-free degree sequences with this exponent such that the minimum value of Spearman's rho for all graphs with such degree sequences is arbitrary close to zero. This implies that specifying only the tail behavior of the degree distribution, as is often done in the analysis of complex networks, gives no guarantees for the minimum value of Spearman's rho.

Recommendations

• Generating simple random graphs with prescribed degree distribution
• Construction of directed assortative configuration graphs
• Common greedy wiring and rewiring heuristics do not guarantee maximum assortative graphs of given degree
• Efficient and simple generation of random simple connected graphs with prescribed degree sequence
• A sequential algorithm for generating random graphs

Cites work

• scientific article; zbMATH DE number 1334601 (Why is no real title available?)
• 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
• Constructing and sampling graphs with a prescribed joint degree distribution
• Convergence of rank based degree-degree correlations in random directed networks
• Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees
• Degree-degree dependencies in directed networks with heavy-tailed degrees
• Exact sampling of graphs with prescribed degree correlations
• On nonparametric measures of dependence for random variables
• On the properties of some nonparametric concordance measures in the discrete case
• The construction and properties of assortative configuration graphs

Cited in

(1)

• Common greedy wiring and rewiring heuristics do not guarantee maximum assortative graphs of given degree

This page was built for publication: Generating maximally disassortative graphs with given degree distribution

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