LightGraphs.jl中random_configuration_model运行耗时异常过长问题

问题复现 #

迭代生成配置模型图过程中，边序列存储在向量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

问题特征 #

• 耗时异常无规律出现在部分迭代步中，决定算法理论复杂度的变量N和c始终处于同一量级，无明显波动
• 即便设置check_graphical=true提前校验度序列的可图性，异常耗时问题仍然会出现
• 异常仅在负二项分布参数α<1时触发，该参数仅影响负二项分布的方差，不会改变分布均值（有限N下样本均值约为c）

问题诱因 #

该异常耗时由LightGraphs中random_configuration_model函数的默认实现逻辑，与α<1时的度序列统计特征共同导致：

• LightGraphs的配置模型默认采用拒绝采样逻辑生成简单图：先将所有节点的度对应为等量的“半链路”，随机对半链路配对形成连边，如果配对结果出现自环、重边，就直接丢弃本次结果重新执行全量配对，直到生成无自环无重边的简单图为止。
• 当α<1时，所用的负二项分布属于重尾分布，生成的度序列异质性极强：虽然平均度稳定在c附近，但会以不低的概率出现度值远高于平均的极端节点。这类节点在随机配对时出现自环、与其他节点形成重边的概率会大幅升高，直接导致单次配对生成合法简单图的概率骤降，部分迭代步需要重试数百上千次才能得到合法结果，因此表现为无规律的极长耗时。
• 开启check_graphical=true仅能校验度序列是否满足可图条件（即存在至少一个对应简单图），无法改变随机配对过程的低成功率，因此无法解决该耗时问题。

参考替代实现 #

可以使用iGraph库实现相同逻辑的度序列配置图生成，已有使用教程介绍了将iGraph生成的图对象转换为LightGraphs兼容对象的方法与通用使用说明，参考实现代码如下：

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)

内容的提问来源于stack exchange，提问作者Leonardo Ferreira