random_configuration_model(N，E)在LightGraphs.jl上需要长时间

Question

我面临着在LightGraphs上生成配置图的问题。此后，向量E包含边缘序列。我必须在循环中迭代地生成这样的图，下面的例子再现了这个问题。

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

在某些迭代步骤j中，由于决定复杂性的变量(N和c)保持相同的顺序，g = random_configuration_model(N,E)似乎需要很长时间才能运行。确保序列是图形化的check_graphical=true没有帮助，而且问题也会发生。它只发生在小值的α (<1)，但这个参数只影响负二项分布的方差，而不是它的平均值，即近似于有限N的c。有人知道什么可能会导致这个问题吗？

编辑:作为一个完整的问题，我在下面留下了如何用iGraph生成配置随机图(full：https://igraph.org/)。您可以在Bogumi iGraph Kamiński的这教程中找到如何将LightGraph对象g2转换为LightGraph对象(以及更多关于一般用法的内容)。

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

原因是random_configuration_model使用拒绝抽样方法生成图。

您已经可以在25个节点上的相当大的星上看到它：

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

当程度序列几乎是非图形时，拒绝抽样是有问题的(就像“命中”一个简单图的概率很低一样)。

如果您可以接受与均匀抽样的小偏差，则可以提供比拒绝抽样更快的方法，但是AFAICT不是在Graphs.jl中实现的。其中一种流行的方法是https://arxiv.org/abs/cs/0502085，它还附加了一个限制，即图形应该连接。这种方法在iGraph中是可用的。