erdos_renyi is n^2 algorithm

[jpfairbanks]

You can instead compute the number of edges to draw as ne ~ binomial((n^2-n)/2 , p) and then pick i,j uniformly at random until you hit ne edges. This leads to an O(ne) algorithm for small p For large p you end up doing O(n^2) work anyway.

[sbromberger]

The two issues with this are

1. (similar to the random graph generation built into Graph by default) it's not guaranteed to terminate, especially with large p.

2. We must check has_edge() for each iteration.

[jpfairbanks]

The two issues with this are

1. (similar to the random graph generation built into Graph by default) it's not guaranteed to terminate, especially with large p.

Are you generating large p? You could generate with 1-p and then subtract from the complete graph.
2) We must check has_edge() for each iteration.

Doesn’t add_edge! check that anyway so that it can raise an error?
—
Reply to this email directly or view it on GitHub.

[sbromberger]

Subtraction is relatively expensive. I was looking at doing that for the generic random graph creation but there are a lot of nuances to it.

add_edge! checks has_edge, but unless you want to catch exceptions (expensive) you should do it beforehand.

[jpfairbanks]

At least for the undirected case its n choose 2 edge operations which is the original cost

h = Graph(nv(g))
for i in 1:nv(g)
    for j in i+1:nv(g)
        if !has_edge(g, i,j)
            add_edge!(h,i,j)
        end
    end
end
return h

Yeah we have to check before each insertion but we get and asymptotic gain.

[sbromberger]

@jpfairbanks Can you create a function fast_erdos_renyi in randgraphs.jl and we can do some benchmarking and termination checking? I'm not opposed to replacing the existing e_r function but this way we can play with it a bit.

[jpfairbanks]

Are you willing to depend on Distributions.jl? I used it in my sparse_erdos_renyi implementation #29 and forgot to add it to REQUIRE. If you don't want LightGraphs.jl to depend on it then we should make a GraphGenerators.jl package migrate all of the generators that need randomness to that package. The sparse_erdos_renyi implementation could be parameterized by a Distribution to give many different graph generators at once. Basically if you pick a discrete distribution vd over the vertex set and a discrete distribution ned for the number of edges, that same algorithm will generate a graphs whose expected degree distribution is vd and whose number of edges is distributed as ned ER graphs are when vd is uniform and ned is binomial.

[sbromberger]

I'm ok with it. I'm using StatsBase already for some sampling stuff for betweenness_centrality though. Perhaps we can consolidate?

[sbromberger]

As it turns out, Distributions.jl has a sample() function that appears to be identical to the one in StatsBase.jl - so I just switched the dependency. I'll add it to REQUIRE.

[sbromberger]

Closed via #31. Thank you!