time - 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，似乎g = random_configuration_model(N,E)需要意外(非常)长的时间来运行，因为决定复杂度(N 和 c)保持相同的顺序。使用 check_graphical=true 确保序列是图形的并没有帮助，而且问题也会发生。仅当 α (<1) 值较小时才会发生这种情况，但此参数仅影响负二项式分布的方差，而不影响其平均值，即大约 c对于有限的N。有谁知道可能导致此问题的原因吗？

编辑:为了完整性，我在下面留下了如何使用 iGraph 生成配置随机图(完整文档: https://igraph.org/ )。人们可以在 this 找到如何将 iGraph 对象 g2 转换为 LightGraph 对象(以及更多关于一般用法的信息)。 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

原因是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 中提供了此方法。