<p>The reason is that <code>random_configuration_model</code> uses a rejection sampling approach to generate graphs.</p>
<p>You can already see it on quite star on 25 nodes:</p>
<pre><code>julia&gt; @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&gt; @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&gt; @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
</code></pre>
<p>Rejection sampling is problematic when degree sequence is almost non graphic (as then the probability to &quot;hit&quot; a simple graph is low).</p>
<p>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 <a href="https://arxiv.org/abs/cs/0502085" rel="nofollow noreferrer">https://arxiv.org/abs/cs/0502085</a> which additionally puts a restriction that the graph should be connected. This method is available in iGraph.</p>
random_configuration_model(N,E) takes to long on LightGraphs.jl
<p>I'm facing problems with the generation of configurational graphs on LightGraphs. Hereafter, the vector  <code>E</code> contains the sequence of edges. I have to generate this kind of graph iteratively inside a loop and the example below reproduces the problem.</p>
<pre><code>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
</code></pre>
<p>At some iteration step <code>j</code>, it seems that <code>g = random_configuration_model(N,E)</code> takes unexpected (very) long time to run, since the variables that determine the complexity (<code>N</code> and <code>c</code>) 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 <code>α</code> (&lt;1), but this parameter only affects the variance of the negative binomial distribution, and not its mean value, that is approximately <code>c</code> for finite <code>N</code>. Does anyone know something that may be causing this problem?</p>
<p>Edit: as a matter of completeness, I leave below how I generated the configuration random graph with iGraph (full doc: <a href="https://igraph.org/" rel="nofollow noreferrer">https://igraph.org/</a>). One can find how to transform the iGraph object <code>g2</code> to a LightGraph object (and more on general usage) at <a href="https://bkamins.github.io/julialang/2021/04/09/igraph.html" rel="nofollow noreferrer">this</a> tutorial by Bogumił Kamiński.</p>
<pre><code>using LightGraphs, PyCall, Distributions
ig = pyimport(&quot;igraph&quot;)

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)
</code></pre>