Generate a graph with n vertices, m edges that's uniformly random

Question

What algorithm produces a graph with N vertices and M edges that's uniformly random in a reasonable time complexity (worst-case quasi-linear)?

The graph is undirected, with neither multi-edges nor loop edges.

Answer 1

1. Generate N vertices.
2. Then M edges.
3. Select random vertices as source and destination.

Since there aren't 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)

---

For undirected graphs without multi-edges or loops, keep generating random edges until there's 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 backslash, \, is set theory notation for set exclusion, so choose V such that it is not in the source set). The E does not contain edge should not care for the direction. That is, 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.

---

Example implementation:

import java.io.PrintStream;
import java.util.*;

import static java.lang.String.format;

public class UniformGraph {
  /**
   * If creating an edge between two random vertices takes more than this
   * many tries, skip the edge. This ensures creating the graph will terminate.
   */
  private static final int MAX_ITERATIONS = 10;

  /**
   * Represents a line segment between point A and point B. Note that points
   * may require conversion to a coordinate system. For example, a Cartesian
   * plane with coordinates (X, Y) and a maximum X value Mx, a vertex offset
   * can be calculated using X + (Y * Mx).
   *
   * @param a   The starting line segment point.
   * @param b   The ending line segment point.
   * @param <T> The data type representing points.
   */
  private record Tuple<T extends Comparable<T>>( T a, T b )
    implements Comparable<Tuple<T>> {
    public String toString() {
      return format( "%s -> %s", a(), b() );
    }

    @Override
    public int compareTo( final Tuple<T> o ) {
      return a().compareTo( o.a() );
    }
  }

  public UniformGraph() {}

  /**
   * @param n Number of vertices in the graph.
   * @param m Number of edges in the graph.
   */
  public Set<Tuple<Integer>> generate( final int n, final int m ) {
    assert n > 1;
    assert m > 1;

    final var mRandom = new Random();
    final var edges = new TreeSet<Tuple<Integer>>();

    for( int i = 0; i < m; i++ ) {
      var iter = 0;
      boolean conflict;
      Tuple<Integer> edge;

      do {
        final var vertex1 = mRandom.nextInt( n );
        final var vertex2 = mRandom.nextInt( n );

        edge = new Tuple<>( vertex1, vertex2 );

        conflict = edges.contains( edge ) || vertex1 == vertex2;
      }
      while( conflict && ++iter < MAX_ITERATIONS );

      edges.add( edge );
    }

    return edges;
  }

  public void print( final Set<Tuple<Integer>> edges, final PrintStream out ) {
    for( final var edge : edges ) {
      out.println( edge );
    }
  }

  public static void main( final String[] args ) {
    final var graph = new UniformGraph();
    final var edges = graph.generate( 20, 9 );

    graph.print( edges, System.out );
  }
}

Answer 2

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.