CODEWITHSUNDEEP
algorithmrandomgraph
Fihop
Fihop

Reputation: 3177

generate a random graph with uniform distribution of edges

I'm trying to find an efficient algorithm to generate a simple connected graph with given the number of nodes. Something like:

Input:
    N - size of generated graph
Output:
    simple connected graph G(v,e) with N vertices and S edges, The number of edges should be uniform distribution.

Upvotes: 5

Views: 2950

Answers (3)

Leeor
Leeor

Reputation: 19706

A very common random graph generation algorithm (used in many academic works) is based on RMat method, or a generalization in the form of Kronecker graphs. It's a simple, iterative process, that uses very few parameters and is easily scalable.

There's a really good explanation here (including why it's better than other methods) - http://www.graphanalysis.org/SIAM-PP08/Leskovic.pdf

There are versions of both implemented in many graph benchmark suites, for e.g.

Upvotes: 0

artur grzesiak
artur grzesiak

Reputation: 20348

It may be a bit surprising but if you choose (randomly) log(n) edges (where n - maximum number of edges) then you can be almost sure that your graph is connected (a reference). If number of edges is much lower than log(n) you can be almost sure that the graph is disconnected.

How to generate the graph:

GenerateGraph(N,S):
    if (log(N)/N) > S) return null // or you can take another action
    V <- {0,...,N-1}
    E <- {}
    possible_edges <- {{v,u}: v,u in V} // all possible edges
    while (size(E) < S):
        e <- get_random_edge(possible_edges)
        E.add(e)
        possible_edges.remove(e)
    G=(V,E)
    if (G is connected)
        return G
    else
        return GenerateGraph(N,S)

Let me know if you need any more guidance. (Btw. right now I am dealing with exactly the same problem! Let me know if you need to generate some more sophisticated graphs:-))

Upvotes: 1

ElKamina
ElKamina

Reputation: 7807

You might want to create a minimal spanning tree first to ensure connectivity. Later, randomly generate two nodes (which are not yet connected) and connect them. Repeat until you have S edges.

For minimal spanning tree, the easiest thing to do is start with a random node as tree. For every remaining node (ordered randomly), connect it to any node in the tree. The way you select the node within the tree (to connect to) defines the distribution of edges/node.

Upvotes: 1

Related Questions