Sampler for bipartite graphs with given degrees

[gaborcsardi]

trafficstars

See http://dx.doi.org/10.1016/j.physa.2006.04.047

And the code is actually here: http://jlguillaume.free.fr/www/programs.php?lang=eng

---

Imported from Launchpad using lp2gh.

• date created: 2010-10-28T09:15:58Z
• owner: gabor.csardi
• the launchpad url was https://bugs.launchpad.net/bugs/667661

[gaborcsardi]

The code on that page is not too useful, actually, it is just sampling the bottom vertices with replacement, individually for each top vertex. So it potentially generates multiple edges.

[gaborcsardi]

But we can do a similar thing, only sampling without replacement.

[gaborcsardi]

Well, no, it is actually somewhat more difficult, but it can still be done, of course. One needs two partial prefix sum trees, one for bottom, one for top nodes. We order the vertices (mixed) according to their degrees. Then pull the first neighbor of the highest degree vertex, adjust degrees and trees, and repeat.

[gaborcsardi]

This is probably not uniform sampling, though......

[gaborcsardi]

This is useful: http://www.uvm.edu/~pdodds/files/papers/others/1997/kannan1997.pdf

[mar-iana]

Hello, I apologize for any confusion. It appears that the issue you mentioned is still unresolved. I haven't found the solution yet to perform a configuration model for bipartite networks , can it be? I also try using the "rewire" function along with "keeping_degseq," but it has resulted in generating links between nodes of the same type, which is supposed to not be allowed in bipartite networks. If anyone has experience or suggestions on how to successfully apply the configuration model for bipartite networks would be greatly appreciated. Thank you in advance for your help!

[szhorvat]

Sampling bipartite networks with given degrees is not available yet in igraph. It is planned to be implemented sometime this autumn, along with a bipartite version of rewire().

If anyone has experience or suggestions on how to successfully apply the configuration model for bipartite networks would be greatly appreciated.

You can implement the stub matching method yourself, as it's quite easy in high-level languages. See https://sites.santafe.edu/~aaronc/courses/5352/fall2013/csci5352_2013_L11.pdf

For further support questions, please use the forum. We would like to reserve the issue tracker for bug reports and feature requests as well as for coordinating development.