Question: 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.

```

Answer: 
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](http://economics.mit.edu/files/4622)). 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:-))
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. 

* BFS benchmark with a subdir with rMat generator - <http://www.cs.cmu.edu/~pbbs/benchmarks/breadthFirstSearch.tar>
* Kronecker graph generator (both c and matlab codes included) - <http://www.graph500.org/sites/default/files/files/graph500-2.1.4.tar.bz2>