- Access by Xinjiang University
Proof of uniform sampling of binary matrices with fixed row sums and column sums for the fast Curveball algorithm
Phys. Rev. E 91, 042812 – Published 29 April, 2015Erratum Phys. Rev. E 94, 039902 (2016)
DOI: https://doi.org/10.1103/PhysRevE.91.042812
Abstract
Randomization of binary matrices has become one of the most important quantitative tools in modern computational biology. The equivalent problem of generating random directed networks with fixed degree sequences has also attracted a lot of attention. However, it is very challenging to generate truly unbiased random matrices with fixed row and column sums. Strona et al. [Nat. Commun. 5, 4114 (2014)] introduce the innovative Curveball algorithm and give numerical support for the proposition that it generates truly random matrices. In this paper, we present a rigorous proof of convergence to the uniform distribution. Furthermore, we show the Curveball algorithm must include certain failed trades to ensure uniform sampling.
Erratum
Article Text
References (23)
- A. Zaman and D. Simberloff, Random binary matrices in biogeographical ecology–Instituting a good neighbor policy, Environ, Ecol. Stat. 9, 405 (2002).
- L. Stone and A. Roberts, The checkerboard score and species distributions, Oecologia 85, 74 (1990).
- I. Miklós and J. Podani, Randomization of presence-absence matrices: Comments and new algorithms, Ecology 85, 86 (2004).
- S. Maslov and K. Sneppen, Specificity and stability in topology of protein networks, Science 296, 910 (2002).
- R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Network motifs: Simple building blocks of complex networks, Science 298, 824 (2002).
- T. A. B. Snijders, Enumeration and simulation methods for 0–1 matrices with given marginals, Psychometrika 56, 397 (1991).
- M. Molloy and B. Reed, A critical point for random graphs with a given degree sequence, Random Struct. Algorithms 6, 161 (1995).
- M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64, 026118 (2001).
- Y. Artzy-Randrup and L. Stone, Generating uniformly distributed random networks, Phys. Rev. E 72, 056708 (2005).
- C. J. Carstens, A uniform random graph model for directed acyclic networks and its effect on motif-finding, J. Complex Networks 2, 419 (2014).
- O. D. King, Comment on “Subgraphs in random networks”, Phys. Rev. E 70, 058101 (2004).
- Also known as rewiring methods, switching methods, and trade methods.
- A. R. Rao, R. Jana, and S. Bandyopadhyay, A Markov chain Monte Carlo method for generating random (0,1)-matrices with given marginals, Sankhyä: The Indian Journal of Statistics, Ser. A 58, 225 (1996).
- R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, and U. Alon, On the uniform generation of random graphs with prescribed degree sequences, arXiv:cond-mat/0312028.
- H. Klein-Hennig and A. K. Hartmann, Bias in generation of random graphs, Phys. Rev. E 85, 026101 (2012).
- From now on we refer to the “switch and hold” method from Ref. [9] as “the switching method”.
- G. Strona, D. Nappo, F. Boccacci, S. Fattorini, and J. San-Miguel-Ayanz, A fast and unbiased procedure to randomize ecological binary matrices with fixed row and column totals, Nat. Commun. 5, 4114 (2014).
- M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, Cambridge, New York, 2005).
- Depending on the dimensions of the matrix it may be faster to make a list of the columns, and depending on the number of zeros and ones in the matrix it may be faster to make lists of the zeros.
- This explicit description of step (d) is based on the implementation of the Curveball algorithm as can be downloaded from http://www.nature.com/ncomms/2014/140611/ncomms5114/extref/ncomms5114-s6.txt.
- H. J. Ryser, Combinatorial Mathematics, Carus Mathematical Monographs Vol. 14 (The Mathematical Association of America, Buffalo, NY, 1963).
- These formulas for the transition probabilities are not in correspondence with those presented in Ref. [17] for the small example of matrices with row sums and column sums equal to (1,2,1). However, these formulas correspond to the algorithm as found in the Supplementary Material code of Ref. [17]. The probabilities presented in Ref. [17] correspond to the good-shuffle Curveball algorithm discussed in Sec. 3a.
- An implementation of the good-shuffle Curveball algorithm can be found at http://github.com/queenBNE/Curveball.