random_configuration_model(N,E) takes to long on LightGraphs.jl

Question

I'm facing problems with the generation of configurational graphs on LightGraphs. Hereafter, the vector E contains the sequence of edges. I have to generate this kind of graph iteratively inside a loop and the example below reproduces the problem.

using LightGraphs, Distributions
N=2000;c=0.01*N
α=0.625
p = α/(c+α)
E = zeros(Int64,N)

for j in 1:100
    s=0
    for i in 1:N
        E[i] = rand(NegativeBinomial(α,p))
        s += E[i]
    end
    if iseven(s) == false
        k = rand(DiscreteUniform(1,N))
        E[k] += 1
    end
    @show s
    g = random_configuration_model(N,E)
    @show j
end

At some iteration step j, it seems that g = random_configuration_model(N,E) takes unexpected (very) long time to run, since the variables that determine the complexity (N and c) remain of the same order. Making sure that the sequence is graphical with check_graphical=true doesn't help and the problem also happens. It happens only for small values of α (<1), but this parameter only affects the variance of the negative binomial distribution, and not its mean value, that is approximately c for finite N. Does anyone know something that may be causing this problem?

Edit: as a matter of completeness, I leave below how I generated the configuration random graph with iGraph (full doc: https://igraph.org/). One can find how to transform the iGraph object g2 to a LightGraph object (and more on general usage) at this tutorial by Bogumił Kamiński.

using LightGraphs, PyCall, Distributions
ig = pyimport("igraph")

s=0;N=1000;c=N*0.01;α=0.625;p=α/(c+α)
E=zeros(Int64,N)
for i in 1:N
    E[i] = rand(NegativeBinomial(α,p))
    s += E[i]
end

if iseven(s) == false
    k = rand(DiscreteUniform(1,N))
    E[k] += 1
end

g2 = ig.Graph.Realize_Degree_Sequence(E)

Answer 1

The reason is that random_configuration_model uses a rejection sampling approach to generate graphs.

You can already see it on quite star on 25 nodes:

julia> @time random_configuration_model(25, [24; fill(1, 24)])
 14.668509 seconds (134.34 M allocations: 16.465 GiB, 10.71% gc time)
{25, 24} undirected simple Int64 graph

julia> @time random_configuration_model(25, [24; fill(1, 24)])
  2.242426 seconds (20.41 M allocations: 2.501 GiB, 10.54% gc time)
{25, 24} undirected simple Int64 graph

julia> @time random_configuration_model(25, [24; fill(1, 24)])
 14.490126 seconds (130.53 M allocations: 15.999 GiB, 10.77% gc time)
{25, 24} undirected simple Int64 graph

Rejection sampling is problematic when degree sequence is almost non graphic (as then the probability to "hit" a simple graph is low).

Faster approaches than rejection sampling are available if you can accept a small deviation from uniform sampling but AFAICT are not implemented in Graphs.jl. One such method that is popular is https://arxiv.org/abs/cs/0502085 which additionally puts a restriction that the graph should be connected. This method is available in iGraph.