Generating maximally disassortative graphs with given degree distribution

DOI10.1287/STSY.2017.0006zbMATH Open1442.05212arXiv1607.01742OpenAlexW2963882047MaRDI QIDQ5113876FDOQ5113876

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

Publication date: 18 June 2020

Published in: Stochastic Systems (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• On nonparametric measures of dependence for random variables
• Degree-Degree Dependencies in Directed Networks with Heavy-Tailed Degrees
• 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
• Convergence of rank based degree-degree correlations in random directed networks
• Exact sampling of graphs with prescribed degree correlations
• Title not available (Why is that?)
• On the properties of some nonparametric concordance measures in the discrete case
• Constructing and sampling graphs with a prescribed joint degree distribution
• Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees
• The Construction and Properties of Assortative Configuration Graphs

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)