Generate a graph with n veritces, m edges uniformly at random algorithm

Question

Easy question, haven't found an easy answer. I want a graph with N vertices, M edges, uniformly at random. In a reasonable time complexity (I'd say quasilinear at worst). Does such algorithm exist, and if yes, what is it?

EDIT: Clarification: The graph is undirected, has no multi-edges or loop edges.

Should be straightforward. Just generate `N` vertices. Then `M` edges. Select random vertices as source and destination. Since you don't have additional requirements (like automata languages) this is uniformly distributed. — Zabuzard, May 29 '18 at 14:15
What do you mean by "uniformly at random"? If you mean a uniform random labeled graph, then @Zabuza has the right idea. If you mean a uniform random unlabeled graph (i.e., isomorphism class), then I don't know of an approach with a good worst-case running time. — David Eisenstat, May 29 '18 at 14:18

Zabuzard · Accepted Answer · 2018-05-29T14:30:42.067

Should be straightforward. Just generate N vertices. Then M edges. Select random vertices as source and destination. Since you don't have additional requirements (like automata languages) this is uniformly distributed.

V <- {1, ..., N}
E <- {}
for 1 to M do
    edge <- (random(V), random(V))
    E.push(edge)
return (V, E)

EDIT: Clarification: The graph is undirected, has no multi-edges or loops.

Keep generating random edges until you have a valid edge:

V <- {1, ..., N}
E <- {}
for 1 to M do
    repeat
        source <- random(V)
        edge <- (source, random(V \ {source}))
    until E does not contain edge
    E.push(edge)
return (V, E)

For the destination use random(V \ source) to exclude loops. The E does not contain edge should not care for the direction. I.e. it should consider

(a, b) = (b, a)

For efficiency of the contains you should use some hashed structure when implementing.

The problem is the repeat loop. Depending on how fast random works and how close M is to the amount of possible edges, it may take a while. You can speed this up using techniques like the Floyd-Rivest algorithm (also see Algorithm to select a single, random combination of values?).

If M is rather small, compared to the maximal amount, it should run fast (linear in N and M) since you don't get a lot of edge collisions.

Again, sorry for inaccuracy, but as I stated in the edit, I don't want multi-edges. — V0ldek, May 29 '18 at 14:21
Use Floyd's sampling algorithm to reduce repetitive sampling when m is large: https://stackoverflow.com/a/2394292/2144669 — David Eisenstat, May 29 '18 at 14:23
That sampling algorithm is just the trick! If it really works in O(x) then it solves all my problems, thanks! — V0ldek, May 29 '18 at 14:30

score 1 · Answer 2 · answered May 29 '18 at 15:30

To generate a random graph efficiently, you can use Erdős–Rényi model. It is a classical approach in graph theory. The Java code (using graphstream library) to generate a random graph is something like:

Graph g = new SingleGraph("Erdos-Renyi model");
// adding the first nodes
g.addNode("0");
g.addNode("1");
// creates the first edge
g.addEdge("0_1", "0", "1");
Integer i = 2;
while(i < numNodes) {
    Node source = g.addNode(i.toString());
    Node dest = g.getNode(random.nextInt(i)+"");
    g.addEdge(source.getId() + "_" + dest.getId(), source.getId(), dest.getId());
    i++;
 }

There are also other models to generate graphs such as the Barabási–Albert model. This model generates a graph where the more connected a node is, the more likely it is to receive new links (describing the rich get richer phenomenon). The Java code to generate a random graph using Barabási-Albert model is:

Graph g = new SingleGraph("Barabasi–Albert model");    
g.addNode("0");
g.addNode("1");
g.addEdge("0_1", "0", "1");
int sumDegree = 2;
Integer i = 2;
while(i < numNodes) {
    Node source = g.getNode(i.toString());
    if(source == null) {
          source = g.addNode(i.toString());
    }
    Node dest = g.getNode(random.nextInt(i)+"");
    double probability = dest.getDegree() * 1.0/sumDegree;
    double r = nextDouble();
    if(probability > r) {
       g.addEdge(source.getId() + "_" + dest.getId(), source.getId(), dest.getId());
        sumDegree = sumDegree + 2;
         i++;
       }
  }

Another famous approach is to generate a random graph with small-world properties by using the Watts–Strogatz model. In this case, most nodes are not neighbors of one another. However, the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a small number of hops.

As you see, there are several possibilities to generate random graphs. Depending on the network characteristics required, a specific model should be used.

Thanks for information. Also Sedgewick and Wayne in their book "Algortihms" discuss some approaches. Code: https://algs4.cs.princeton.edu/41graph/GraphGenerator.java.html — MBo, May 31 '18 at 03:09
It's a fantastic book. Certainly, a good reference for those who wish to learn more about algorithms. In addition, their code examples are well presented and documented. — Thiago Procaci, May 31 '18 at 20:53

Generate a graph with n veritces, m edges uniformly at random algorithm

2 Answers2