Short and clear paper to understand important problems encountered when generating a random graph on a typical example: matching methods are often biased (when possible), switching methods are safer but not controlled in terms of mixing time.
__Summary__
This article focuses on the uniform generation of simple graphs (no self-loops, no multiple edges) with a prescribed degree distribution. The graphs considered here are directed, but the generalization to the undirected case is straightforward.
Uniform generation means that all graphs have the same probability to be generated.
3 methods are compared:
- matching (= configuration model)
- switching (= basic edge switching method)
- go-with-the-winners (new, derived from matching)
_switching method_
- draw two random arcs
- switch their ends
- iterate
advantage: if we iterate a sufficient number of times, the graph obtained is uniformly random
drawback: we don't know theoretically what is this sufficient number of times...
_matching method_
- each node is given in-stubs and out-stubs corresponding to its in- and out-degree
- in-stubs and out-stubs are paired randomly
- (strong version) if a multi-edge is created the graph is discarded, and restart
advantage: the graph obtained is uniformly random
drawback: very high probability to restart with heavy-tailed dd
weak version (the one used in practice): the graph is not discarded, but the edge is reconnected elsewhere. drawback: the generation is biased
_go with the winners_
- starting from a population of graphs (with the right dd)
- same principle as the matching algorithm
- a graph is discarded if there is a loop or a multi-edge created during the process
- but to compensate the drop in number in the population, surviving graphs are cloned and they are given a weight to compensate for their over-representation in the final sample
_Experimental results_
On a set of toy-graphs for which all elements are known, they show that there is a sampling bias with the matching method
When sampling real classic networks (yeast etc), the bias with the matching algorithm is not detected.
In terms of computation speed matching > switching >> gwtw.
Short and clear paper to understand important problems encountered when generating a random graph on a typical example: matching methods are often biased (when possible), switching methods are safer but not controlled in terms of mixing time.
__Summary__
This article focuses on the uniform generation of simple graphs (no self-loops, no multiple edges) with a prescribed degree distribution. The graphs considered here are directed, but the generalization to the undirected case is straightforward.
Uniform generation means that all graphs have the same probability to be generated.
3 methods are compared:
- matching (= configuration model)
- switching (= basic edge switching method)
- go-with-the-winners (new, derived from matching)
_switching method_
- draw two random arcs
- switch their ends
- iterate
advantage: if we iterate a sufficient number of times, the graph obtained is uniformly random
drawback: we don't know theoretically what is this sufficient number of times...
_matching method_
- each node is given in-stubs and out-stubs corresponding to its in- and out-degree
- in-stubs and out-stubs are paired randomly
- (strong version) if a multi-edge is created the graph is discarded, and restart
advantage: the graph obtained is uniformly random
drawback: very high probability to restart with heavy-tailed dd
weak version (the one used in practice): the graph is not discarded, but the edge is reconnected elsewhere. drawback: the generation is biased
_go with the winners_
- starting from a population of graphs (with the right dd)
- same principle as the matching algorithm
- a graph is discarded if there is a loop or a multi-edge created during the process
- but to compensate the drop in number in the population, surviving graphs are cloned and they are given a weight to compensate for their over-representation in the final sample
_Experimental results_
On a set of toy-graphs for which all elements are known, they show that there is a sampling bias with the matching method
When sampling real classic networks (yeast etc), the bias with the matching algorithm is not detected.
In terms of computation speed matching > switching >> gwtw.
Comments: