Degree-based connected graph construction with assortativity constraint

Abstract Degree-based graph construction is a fundamental problem in network science. A graph is simple if there are no self-loops and no multiple links between any pair of nodes in the graph. A degree sequence <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>=</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>d</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>d</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>d</mml:mi> <mml:mrow> <mml:mi>N</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> is graphical if d can be represented as the degree sequence of at least one simple graph, where the graph is called a realization of the sequence d . In this work, we introduce a novel method (LSFGR) for generating simple graphs from graphical degree sequences, focusing additionally on connectedness and on assortativity. LSFGR guarantees connected graphs for all potentially connected degree sequences. In the case where a degree sequence has no simple realization, LSFGR produces graphs with at most one node with self-loops. In addition, the graphs generated from LSFGR characterize real-world networks with medium assortativity.