search

JuliaGraphs / Graphs.jl

An optimized graphs package for the Julia programming language
http://juliagraphs.org/Graphs.jl/
Other
455 stars 88 forks source link

consider adding approximate algorithm for random_configuration_model #149

Open bkamins opened 2 years ago

bkamins commented 2 years ago

Follow up to https://stackoverflow.com/questions/72732571/random-configuration-modeln-e-takes-to-long-on-lightgraphs-jl.

Currently random_configuration_model uses rejection sampling which is very slow for tight configurations. Probably allowing for approximate sampling with some edge rewiring strategy could be allowed (iGraph implements this).

etiennedeg commented 2 years ago

I already noticed that the algorithm was not the true random_configuration_model as it does not allows the creation of multigraphs. If I remember correctly, even with the rejection sampling used, I think that the current generation is not exactly uniform (to be checked), so maybe it makes sense to do that...

bkamins commented 2 years ago

does not allows the creation of multigraphs

I assumed it was on purpose as SimpleGraph does not support multigraphs

current generation is not exactly uniform

Ah - indeed - I have just checked. It does some "naive" collision resolution breaking uniformity. So indeed we are neither uniform nor "fast near uniform" now.

bkamins commented 2 years ago

I am not sure why bug label was added here automatically. I would classify it as feature request.