Message Boards Message Boards

0
|
11255 Views
|
8 Replies
|
3 Total Likes
View groups...
Share
Share this post:

[?] Generate a random connected graph?

Posted 4 years ago

As title said, how to generate a random connected graph?

I test the function RandomGraph, but it can't make sure to be connected. How to realized it on Mathematica?

POSTED BY: Licheng Zhang
8 Replies

Thanks for the response!

The method you used in Sage can be implemented like this with IGraph/M:

IGTryUntil[ConnectedGraphQ]@RandomGraph[{20, 20}]

This keeps re-trying until RandomGraph[{20, 20}] produces a connected result. Of course, the IGTryUntil is very simple, and you don't need IGraph/M for this. You can implement it as

While@Not@ConnectedGraphQ[g = RandomGraph[{20,20}]]
g

However, in practical use, I find it to be a great convenience.

The problem with this method (rejection sampling) is that for some parameters, it is unlikely that the produced graph will be connected. A graph on $n$ vertices needs at least $n-1$ edges to be connected. If we exceed this edge count by only a little, most generated graphs won't be connected, and the algorithm will have to keep re-trying practically forever.

IGTryUntil[ConnectedGraphQ]@RandomGraph[{40, 40}] is already noticeably slow and once we go to 100, it won't ever finish.


I looked at Maple's RandomGraph function. What it does is that it generates a random tree, i.e. a random connected graph with $n$ vertices and $n-1$ edges, then it adds more edges randomly to reach the desired edge count. This is a commonly suggested method on various online blogs. Despite what you might read on these blogs, it does not sample uniformly (i.e. it's wrong).

POSTED BY: Szabolcs Horvát
Posted 4 years ago

I have a premature opinion idea : First I can generate a random graph, then we choose one vertex randomly from each connected component of the graph, and connect them as a path.

POSTED BY: Licheng Zhang
Posted 4 years ago

Sir, first thank you very much for your patient reply! I'm sorry to reply you so late.

Speak accurately, SageMath has no ready-made function to generate a random connected graph: That's what I did before in Sage notebook is something similar to what you're dealing with.

import networkx as nx                   # import networx package 
testgraph = RandomGNP(10, .5).networkx_graph(); 
while nx.is_connected(testgraph) == False:
     testgraph= RandomGNP(10, .5).networkx_graph()
print nx.is_connected(testgraph)

enter image description here Ps: In Maple, I noticed that ready-made function RandomGraph(10 , connected) can directly generate random connected graph.

POSTED BY: Licheng Zhang
Posted 4 years ago

Sir, first thank you very much for your patient ! I'm sorry to reply you so late.

Speak accurately, SageMath has no ready-made function to generate a random connected graph: That's what I did before in Sage notebook is something similar to what you're dealing with.

import networkx as nx                   # import networx package 
testgraph = RandomGNP(10, .5).networkx_graph(); 
while nx.is_connected(testgraph) == False:
     testgraph= RandomGNP(10, .5).networkx_graph()
print nx.is_connected(testgraph)

Ps: In Maple, I noticed that ready-made function RandomGraph(10 , connected) can directly generate random connected graph. I have

POSTED BY: Licheng Zhang

To do this mathematically accurately, the question needs to be better specified.

What do we mean when we say "generate a random X"?

A more precise phrasing of the problem is "choose an X uniformly at random from the set of all Xs", with uniform being critical (i.e. each X is chosen with the same probability). For some applications, non-uniform sampling is also useful, but we would at least want to know what distribution we are sampling from.

Most suggestions you will find online about how to do this will neither sample uniformly, nor will they make it easy (or at all possible!) to figure out the actual distribution you are sampling from. This is also true for Nicola's suggestion above.


So let's make the question precise:

Do you want to sample uniformly from the set of all connected simple graphs on $n$ vertices? Notice the two constraints: "connected" and "having $n$ vertices". This task happens to be easy because most graphs on $n$ vertices are connected. Thus we can use rejection sampling.

While[
 Not@ConnectedGraphQ[
   g = RandomGraph[BernoulliGraphDistribution[10, 1/2]]
  ]
 ]
g

BernoulliGraphDistribution[10, 1/2] represents a uniform distribution over the set of all simple graphs on 10 vertices. We keep drawing graphs from this distribution until we find a connected one. With very high probability, the first one will already be connected.


Another version of the problem:

Sample uniformly from the set of connected simple graphs on $n$ vertices with $m$ edges. Now we have an extra constraint on the number of edges, and this makes the problem much harder. I am not aware of any simple and general solutions to this.

We can pick a graph at random with $n$ vertices and $m$ edges using RandomGraph[{n,m}], but some of these will not be connected. If m is low, most of these will not be connected, thus rejection sampling is not feasible.

I asked a question about this on MathOverflow a while ago: https://mathoverflow.net/q/297317/8776

If you google for solutions, a typical suggestion is to first construct a random tree (there are several simple methods for uniform sampling of trees), which ensures connectedness. Then add more edges randomly. This method is incorrect. It does not sample uniformly, nor do the various blog posts suggestion this algorithm derive the actual distribution is samples from.


@Licheng Zhang, you mention using Sage for this problem. Can you specify which exact problem (see two possible versions above) and which Sage function you are using? I am interested in this topic too.

POSTED BY: Szabolcs Horvát
First @ ConnectedGraphComponents @ graph
Posted 4 years ago

Sorry reply to you so late, I use sage to do this easily. But I do not know the ways to realize in Mathematica.

POSTED BY: Licheng Zhang
Posted 4 years ago

From the RandomGraph documentation, under Possible Issues:

enter image description here

But then one could argue that the graph is not random anymore.

POSTED BY: Hans Milton
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract