Unbiased degree-preserving randomization of directed binary networks

TY - JOUR

T1 - Unbiased degree-preserving randomization of directed binary networks

AU - Roberts, E. S.

AU - Coolen, A. C. C.

PY - 2012/4/5

Y1 - 2012/4/5

N2 - Randomizing networks using a naive "accept-all" edge-swap algorithm is generally biased. Building on recent results for nondirected graphs, we construct an ergodic detailed balance Markov chain with nontrivial acceptance probabilities for directed graphs, which converges to a strictly uniform measure and is based on edge swaps that conserve all in and out degrees. The acceptance probabilities can also be generalized to define Markov chains that target any alternative desired measure on the space of directed graphs in order to generate graphs with more sophisticated topological features. This is demonstrated by defining a process tailored to the production of directed graphs with specified degree-degree correlation functions. The theory is implemented numerically and tested on synthetic and biological network examples.

AB - Randomizing networks using a naive "accept-all" edge-swap algorithm is generally biased. Building on recent results for nondirected graphs, we construct an ergodic detailed balance Markov chain with nontrivial acceptance probabilities for directed graphs, which converges to a strictly uniform measure and is based on edge swaps that conserve all in and out degrees. The acceptance probabilities can also be generalized to define Markov chains that target any alternative desired measure on the space of directed graphs in order to generate graphs with more sophisticated topological features. This is demonstrated by defining a process tailored to the production of directed graphs with specified degree-degree correlation functions. The theory is implemented numerically and tested on synthetic and biological network examples.

M3 - Article

VL - 85

JO - PHYSICAL REVIEW E

JF - PHYSICAL REVIEW E

IS - 4

M1 - 046103

ER -