6
$\begingroup$

I need to generate random connected simple graphs (no loops) with the constraint that exactly two vertices must only have a single edge. I can create many connected graphs (but very few will have the properties I want) like so:

gps = Select[RandomGraph[{30, 70}, 512], ConnectedGraphQ];

This is a bit inefficient because it's rejection sampling. I'm no expert in graph theory so if you know a more efficient way that would be helpful. Here's a diagram of the kind of graph I need:

example of the typical graph I want

I thought about using DegreeGraphDistribution but I don't care about specifying the interior vertices' exact degree as long as d>=2 and the 'input' and 'output' nodes have degree 1. Ideally, I'd like this to be as fast as possible, to generate an extremely large number of such graphs (tens of thousands if not more) quickly.

UPDATE: best I've got so far is an inefficient rejection sampling approach (RandomInteger could be replaced with a Binomial variate maybe) but this fails sometimes because DegreeGraphDistribution isn't always guaranteed to generate a proper graph for given degrees... so I just evaluate the line a few times until it works:

While[Quiet[Check[gps = 
  Select[Quiet@
    RandomGraph[
     DegreeGraphDistribution[
      Join[RandomInteger[{2, 5}, 50], {1, 1}]], 10000], 
   ConnectedGraphQ],
  RandomGraph::argt]] === RandomGraph::argt];
Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ I see at least two approaches. First, you can generate a suitable random graph, and then sample uniformly at random 2 vertices $u$ and $v$. Then introduce two new vertices $x$ and $y$, and add in edges $(x,u)$ and $(y,v)$. Or, based on rejection sampling, you can generate degree sequences (that contains exactly two ones), and apply the Havel-Hakimi algorithm. $\endgroup$
    – Juho
    May 25, 2015 at 16:34
  • 1
    $\begingroup$ When you say "random graph" do you mean "just give me some graph with these properties" or do you mean true uniform sampling from the set of all graphs satisfying your constraints? The latter is a much harder problem. Also, can you list your constraints concisely and clearly? $\endgroup$
    – Szabolcs
    May 25, 2015 at 19:23
  • $\begingroup$ @Szabolcs No I mean using the RandomGraph function to generate many different graphs with these properties on demand, not a single instance. So far the code I have works but is a little slow (not dreadful but doesn't scale well) and I'm searching for a more efficient approach $\endgroup$
    – Histograms
    May 25, 2015 at 19:30
  • $\begingroup$ What I was trying to ask if whether you need all graphs that satisfy the constraints to be sampled with equal probability. I'm assuming yes. $\endgroup$
    – Szabolcs
    May 25, 2015 at 19:35
  • $\begingroup$ Oh right, the graphs are not required to be sampled uniformly. I realize I'm being a bit vague. I only need a tonne of different graphs that have these properties and "look different enough" in a very hand-wavy way. I'm doing this for creating an unusual kind of learning algorithm a bit like a neural network. $\endgroup$
    – Histograms
    May 25, 2015 at 19:58

1 Answer 1

Reset to default
4
$\begingroup$

The below approach seems to work efficiently. First, generate a list q of vertex degrees that are each at least 2.0. You can make the graphs more complex by changing the RandomInteger[{2, 5}], below, to RandomInteger[{2, 6}] or whatever, so long as you don't make the degree greater than the number of nodes - 1 (which would force a self-loop). From the fundamental theorem of graph theory and your constraints, the sum of the degrees must be even. If not, then merely add a vertex whose degree is 3; that will make the sum of the vertex degrees even and thus yield an acceptable (base) graph.

Then simply add two more vertexes and a single edge for each to two nodes in the graph. (They can even be to the same node.)

Table[
 q = Table[RandomInteger[{2, 5}], {8}];
 If[OddQ[ Total@q], AppendTo[q, 3]];
 g = RandomGraph[DegreeGraphDistribution[q]];
 EdgeAdd[VertexAdd[
   g, {Length[q] + 1, Length[q] + 2}], {Length[q] + 1 <-> 2, 
   Length[q] + 2 <-> 3}],
 {10}]

Generating 10^5 examples takes less than 20 seconds on a Mac Pro.

The above code can be optimized slightly by putting on constraints that the degree not be greater than the number of nodes -1, that if the total of the degrees is not even you increment any entry by 1.0 (thus making the total even), and so forth.

I don't think this algorithm samples the space uniformly, and there might be duplicates in your list (which you can delete using SameQ), but this should work for many applications.

Here are some representations:

Grid[Partition[Table[q = Table[RandomInteger[{2, 9}], {12}];
   If[OddQ[Total@q], AppendTo[q, 3]];
   g = RandomGraph[DegreeGraphDistribution[q]];
   EdgeAdd[
    VertexAdd[
     g, {Length[q] + 1, Length[q] + 2}], {Length[q] + 1 <-> 2, 
     Length[q] + 2 <-> 3}], {10}], 5]]

enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ Brilliant, exactly what I was looking for. $\endgroup$
    – Histograms
    May 25, 2015 at 19:38
  • $\begingroup$ There is one minor problem, if you generate say, 20000 cases, a few will not be connected for some reason, although it seems easy enough to remove them. $\endgroup$
    – Histograms
    May 25, 2015 at 20:13
  • $\begingroup$ @Histograms Ah yes... I see. Some indeed might not be connected. Several ways to avoid that: 1) merely test each graph using ConnectedGraphQ, or 2) increase the range of vertex degrees so as to make such graphs very rare. There are more complex methods too, but I'm confident they will slow down your generation routines significantly. $\endgroup$
    – David G. Stork
    May 25, 2015 at 20:17

Your Answer

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

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