Creating an Erdos-Renyi Graph

Dear Friends,

How one should create an Erdos-Renyi random graph with graph_tool? Equivalently, a “G_n_p" graph?

I think, one could create a graph with -n- vertices and n*p edges and then use the random_rewire function with model=‘erdos’.

Q1. Can I create the input graph of the random_rewire deterministically and rely on the random_rewire to actually do the shuffling?
Q2. “Turning on” the edge_sweep option and the niter is it crucial for the graph’s randomness?

And a small suggestion: given the popularity of this type of model, it might worth an example at the documentation, to “attract” more people.

All the best,
Helen

PS.
Small side-question: what is the fastest way to create a graph object with n vertices and m edges (any edges other than parallel and self-loops are allowed).

attachment.html (1.23 KB)

Dear Friends,

How one should create an Erdos-Renyi random graph with graph_tool? Equivalently, a “G_n_p" graph?

I think, one could create a graph with -n- vertices and n*p edges and
then use the random_rewire function with model=‘erdos’.

This would work. This is exactly what you would get if you did:

     g = random_graph(n, lambda: poisson((n-1) * p), directed=False, model="erdos")

Note that if you remove "model='erdos'" from the above you will get an
almost indistinguishable graph, i.e. a sample from the configuration
model with a Poisson degree distribution.

(Note that your graph will have on average n(n-1)p/2 edges, not n * p)

Q1. Can I create the input graph of the random_rewire
/deterministically/ and rely on the random_rewire to actually do the
shuffling?

Yes.

Q2. “Turning on” the edge_sweep option and the niter is it crucial for
the graph’s randomness?

The only important thing is that niter is sufficiently large. The
edge_sweep option only makes things faster, since it attempts to rewire
each edge in a random sequence, whereas if it is disabled, each edge to
be sampled is chosen randomly, and it may take a longer time for a
given edge to be chosen.

And a small suggestion: given the popularity of this type of model, it
might worth an *example *at the documentation, to “attract” more
people.

I agree. I'll make sure to include simpler examples in this part of the
documentation in the future. If you want to help, you could open a
ticket about this in the website, so I can keep track of it.

Small side-question: what is the* fastest* way to create a graph
object with n vertices and m edges (any edges other than parallel and
self-loops are allowed).

Should it be random? If not, you can do:

   ak = floor(2 * m / n)
   dm = 2 * m - ak * n
   g = random_graph(N, lambda i: ak + 1 if i < dm else ak, directed=False, random=False)

This is a bit cumbersome, but should be fast. I think it would be a
good idea to include this simple case in the library in some form...

Best,
Tiago