Generating random configuration model graphs in Julia using iGraph

user_19400443 0
Viewed 103

Recently I started to use iGraph in Julia to generate random configuration models, since LightGraphs has a problem with time realization of these objects (link to a previous question related to this: random_configuration_model(N,E) takes to long on LightGraphs.jl). To generate such graphs, I generate a vector E (1-based indexed) and from it I generate an iGraph object g2 as follows

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)

My first question is related to the fact that python is 0-based indexed. By comparison of the components of E to the degrees of g, it seems that ig.Graph.Realize_Degree_Sequence(E) automatically convert the index bases, generating a 0 based object g from a 1-based object E. Is this correct?

Secondly, I would like to enforce the random configuration graph g to be simple, with no self loops nor multi-edges. iGraphs documentation (https://igraph.org/c/doc/igraph-Generators.html#igraph_realize_degree_sequence) says that the flag allowed_edge_types:IGRAPH_SIMPLE_SW does the job, but I am not able to find the syntax to use it in Julia. Is it possible at all to use this flag in Julia?

julia igraph graph
2 Answers

Be careful with LightGraph's random_configruaton_model. Last time I looked, it was broken, and it did not sample uniformly, yet the authors outright refused to fix it. I don't know if anything changed since then.

C/igraph's degree_sequence_game() has a correctly implemented method that samples uniformly, called IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE_UNIFORM, but for some reason it is not yet exposed in Python ... we'll look into exposing it soon.

Then you have two options:

  • Use python-igraph's "simple" method, and keep generating graphs until you get a simple one (test it with Graph.is_simple()). This uses the stub-matching method, and will sample exactly uniformly. For large degrees, it will take a long time due to many rejections. Note that this rejection method exactly what the IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE_UNIFORM implements (albeit bit faster).
  • Use igraph's Graph.Realize_Degree_Sequence() to create one graph with the given degree sequence, then rewrite it using Graph.rewire() with a sufficiently large number of rewiring steps (at least several times the edge count). This method uses degree-preserving edge switches and can be shown to sample uniformly in the limit of a large number of switches.

The "no_multiple" method in python-igraph will again not sample uniformly.

Take a look at section 2.1 of this paper for a gentle explanation of what techniques are available for uniform sampling.

user_6951320

You are reading C docs of igraph. You need to read Python documentation https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Degree_Sequence. So:

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

I used "no_multiple" algorithm, as "vl" algorithm assumes connected graph and some of degrees of nodes in your graph can be 0.

user_12695670
Related