使用IGRAPH在Julia中生成随机配置模型图

Question

最近，我开始使用朱莉娅（Julia）中的igraph来生成随机配置模型，因为LightGraphs在实现这些对象的时间内有问题（链接到与此对象有关的先前问题： rando_configuration_model（n，e）需要很长的时间/a>）。要生成此类图，我生成了一个vector 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的度，从1个基本对象e生成基于0的对象g。这是正确的吗？

其次，我想强制执行随机配置图g是简单的，没有自我循环或多重编号。 igraphs文档（ https://igraph.org/c/doc/igraph-generators.html#igraph_realize_degree_sequence ）表示，flag washe_edge_edge_dege_types：igraph_simple_sw我无法完成工作找到在朱莉娅中使用它的语法。是否有可能在朱莉娅（Julia）中使用此标志？

Answer 1

请小心LightGraph的ROTAMY_CONFIGRUATON_MODEL。上次我看时，它被损坏了，它没有均匀地进行样品，，然而，作者彻底拒绝修复它。从那时起，我不知道是否有任何变化。

c/igraph的 >具有正确实现的方法，该方法均匀地进行了样品，称为igraph_degseq_simple_no_no_multiple_uniform，但由于某种原因，它尚未在Python中暴露出来...我们会尽快将其暴露。

然后，您有两个选项：

• 使用Python-graph的“ Simple”方法，并继续生成图形，直到获得简单的图形（用graph.is_simple（））。这使用了存根匹配方法，并将完全均匀地采样。对于很大的程度，由于许多拒绝，将需要很长时间。请注意，此拒绝方法恰好是igraph_degseq_simple_no_no_multiple_uniform insterments insterments（尽管位更快）。
• 使用igraph的graph.realize_degree_seperence（）用给定的度序列创建一个图，然后使用graph.rewire（）重写，并使用足够多的重新布线步骤（在边缘数量至少几倍）。该方法使用保留学位的边缘开关，可以显示在大量开关的极限下均匀地采样。

“ no_multiple” python-rigraph中的方法将再次 均匀示例。

看看“ nofollow noreferrer”>第2.1节的本文解释哪些技术可用于均匀抽样。

Answer 2

您正在阅读c igraph的文档。您需要阅读python文档 https://igraph.org/python/api/latest/igraph._igraph.graph.graphbase.html#degree_sequence 。因此：

julia> ige = [collect(e .+ 1) for e in ig.Graph.Degree_Sequence(collect(Any, E), method="no_multiple").get_edgelist()];

julia> extrema(reduce(vcat, ige)) # OK check
(1, 1000)

julia> sg = SimpleGraph(1000)
{1000, 0} undirected simple Int64 graph

julia> for (a, b) in ige
           add_edge!(sg, a, b)
       end

julia> sg # OK check
{1000, 5192} undirected simple Int64 graph

julia> length(ige) # OK check
5192

julia> sort(degree(sg)) == sort(E) # OK check
true

我使用“ no_multiple”算法，用作“ vl”算法假定连接的图形，图形中的某些节点可以为0。