graph - 使用 iGraph 在 Julia 中生成随机配置模型图

Question

最近我开始在 Julia 中使用 iGraph 来生成随机配置模型，因为 LightGraphs 在这些对象的时间实现方面存在问题(链接到与此相关的上一个问题:random_configuration_model(N,E) takes to long on LightGraphs.jl)。为了生成这样的图，我生成一个向量 E(从 1 开始索引)，并从中生成一个 iGraph 对象 g2，如下所示

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

α=0.625;N=1000;c=0.01*N;p=α/(α+c)
E = zeros(Int64,N)
test=false

while test == false
    s=0
    for i in 1:N
        E[i] = rand(NegativeBinomial(α,p))
        s += E[i]
    end
    if iseven(s) == true
        test = true
    else
    end
end

g = ig.Graph.Realize_Degree_Sequence(E)

我的第一个问题与 python 是从 0 开始索引这一事实有关。通过比较E的分量与g的度数，似乎ig.Graph.Realize_Degree_Sequence(E)会自动转换索引基数，从基于 1 的对象 E 生成基于 0 的对象 g。这是正确的吗？

其次，我想强制随机配置图 g 变得简单，没有自环也没有多边。 iGraphs 文档 ( https://igraph.org/c/doc/igraph-Generators.html#igraph_realize_degree_sequence ) 说标志 allowed_edge_types:IGRAPH_SIMPLE_SW 可以完成这项工作，但我无法找到在 Julia 中使用它的语法。是否可以在 Julia 中使用这个标志？

Answer 1

小心 LightGraph 的 random_configruaton_model 。上次我看时，it was broken, and it did not sample uniformly ，但作者断然拒绝修复它。不知道从那以后有什么变化吗？

C/igraph 的 degree_sequence_game() 有一个正确实现的均匀采样方法，称为 IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE_UNIFORM ，但由于某种原因它尚未在 Python 中公开...我们将尽快考虑公开它。

那么你有两个选择:

• 使用 python-igraph 的 "simple"方法，并继续生成图表，直到得到一个简单的图表(使用 Graph.is_simple() 进行测试)。这使用 stub 匹配方法，并且将完全均匀地采样。对于大学位，由于多次拒绝，需要很长时间。注意这个拒绝方法到底是什么IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE_UNIFORM实现(尽管速度更快)。
• 使用 igraph 的 Graph.Realize_Degree_Sequence()创建一个具有给定度数序列的图，然后使用 Graph.rewire() 重写它具有足够多的重新布线步骤(至少是边缘计数的几倍)。该方法使用保度边缘交换机，并且可以在大量交换机的限制下均匀采样。

"no_multiple" python-igraph 中的方法将再次不均匀采样。

看看section 2.1 of this paper简要解释哪些技术可用于均匀采样。