7
$\begingroup$

DegreeGraphDistribution supports directed graphs because it has a DirectedEdges option.

How can I specify the in-degree sequence and the out-degree sequence separately when generating random directed graphs?

For example,

RandomGraph@DegreeGraphDistribution[{2, 2, 1, 1}, DirectedEdges -> True]

gives a graph where the vertices have the following {in, out} degree combinations: {{2,2}, {2,2}, {1,1}, {1,1}}. This syntax worked, but the in and out-degree sequences are identical for each vertex. How can I specify them separately?


I'd like to note that as a workaround it is possible to use igraph's degree.sequence.game function through the IGraphR package. However, now I am looking to do this in pure Mathematica though. If you do end up using igraph, be sure to read the documentation in detail, and be aware of the quirks of each method that is available (does it guarantee uniform sampling? does it produce simple graphs? does it support directed graphs? there are several options).

$\endgroup$
1
  • $\begingroup$ As a first observation, what it has there now seems to always produce a balanced digraph (unless somehow I've failed to generate/notice a counterexample). That's something you're noting for this small example, but in general random examples (among those that are valid degree sequences) do work. That makes me think that there should be a way to do it.. but the syntax that seems obvious to me doesn't seem to work. $\endgroup$ Sep 7, 2014 at 17:45

2 Answers 2

6
+100
$\begingroup$

There is a undocumented input form such as:

DegreeGraphDistribution[indegree, outdegree]

For example:

g = RandomGraph[
   DegreeGraphDistribution[{1, 3, 3, 1, 2}, {3, 1, 3, 2, 1}]];

VertexInDegree[g]

{1, 3, 3, 1, 2}

VertexOutDegree[g]

{3, 1, 3, 2, 1}

$\endgroup$
2
  • $\begingroup$ Thanks, I was hoping you'd chime in! Since this is undocumented, are you aware of any issues with this? Does it use the same type of algorithm as the undirected case? $\endgroup$
    – Szabolcs
    Sep 8, 2014 at 15:53
  • $\begingroup$ not sure about issues but it seems to use the same type of algorithm. $\endgroup$
    – halmir
    Sep 8, 2014 at 16:03
1
$\begingroup$

igraph implements alternative algorithms for generating a graph with a given degree sequence. They can be accessed through IGraph/M. These alternative methods can be useful sometimes.

?IGDegreeSequenceGame

IGDegreeSequenceGame[degrees] generates an undirected random graph with the given degree sequence. Available Method options: {"VigerLatapy", "SimpleNoMultiple", "Simple"}. IGDegreeSequenceGame[indegrees, outdegrees] generates a directed random graph with the given in- and out-degree sequences.

Of the three available methods, "VigerLatapy" does not support directed graphs and "Simple" does not guarantee simple graphs (it can create parallel edges). Thus we can use "SimpleNoMultiple".

IGDegreeSequenceGame[{1, 3, 3, 1, 2}, {3, 1, 3, 2, 1}]

Mathematica graphics

{VertexInDegree[%], VertexOutDegree[%]}
(* {{1, 3, 3, 1, 2}, {3, 1, 3, 2, 1}} *)

Mathematica's DegreeGraphDistribution uses the configuration model, I believe. It guarantees uniform sampling, but it may take a very very long time.

igraph's "Simple" method unfortunately does not guarantee uniform sampling, but it can be much faster.

Another strategy one might try using igraph is randomly rewiring edges in a way that the degree sequence is kept. For this we first need to have at least one graph with the given degree sequence, then we can sample more from the same distribution by rewiring its edges.

?IGRewire

IGRewire[graph, n] attempts to rewire the edges of graph n times while preserving its degree sequence.

The problem with this method is that it is not clear how many rewiring steps are necessary to approximate a uniform distribution well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.