{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T05:43:39Z","timestamp":1778910219325,"version":"3.51.4"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2022,12,9]],"date-time":"2022-12-09T00:00:00Z","timestamp":1670544000000},"content-version":"vor","delay-in-days":43,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,10,27]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Many applications require randomly sampling bipartite graphs with fixed degrees or randomly sampling incidence matrices with fixed row and column sums. Although several sampling algorithms exist, the \u2018curveball\u2019 algorithm is the most efficient with an asymptotic time complexity of $O(n~log~n)$ and has been proven to sample uniformly at random. In this article, we introduce the \u2018fastball\u2019 algorithm, which adopts a similar approach but has an asymptotic time complexity of $O(n)$. We show that a C$\\texttt{++}$ implementation of fastball randomly samples large bipartite graphs with fixed degrees faster than curveball, and illustrate the value of this faster algorithm in the context of the fixed degree sequence model for backbone extraction.<\/jats:p>","DOI":"10.1093\/comnet\/cnac049","type":"journal-article","created":{"date-parts":[[2022,12,9]],"date-time":"2022-12-09T10:32:59Z","timestamp":1670581979000},"source":"Crossref","is-referenced-by-count":12,"title":["fastball: a fast algorithm to randomly sample bipartite graphs with fixed degree sequences"],"prefix":"10.1093","volume":"10","author":[{"given":"Karl","family":"Godard","sequence":"first","affiliation":[{"name":"University of Michigan Electrical Engineering and Computer Science, , Ann Arbor, Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zachary P","family":"Neal","sequence":"additional","affiliation":[{"name":"Michigan State University Psychology Department, , East Lansing, Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,12,9]]},"reference":[{"key":"2023120904391760600_B1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41598-020-76300-1","article-title":"The ambiguity of nestedness under soft and hard constraints","volume":"10","author":"Bruno,","year":"2020","journal-title":"Sci. Rep."},{"key":"2023120904391760600_B2","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1038\/s42254-018-0002-6","article-title":"The statistical physics of real-world networks","volume":"1","author":"Cimini,","year":"2019","journal-title":"Nat. Rev. Phys."},{"key":"2023120904391760600_B3","doi-asserted-by":"crossref","first-page":"2606","DOI":"10.1890\/0012-9658(2000)081[2606:NMAOSC]2.0.CO;2","article-title":"Null model analysis of species co-occurrence patterns","volume":"81","author":"Gotelli,","year":"2000","journal-title":"Ecology"},{"key":"2023120904391760600_B4","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/j.socnet.2014.06.001","article-title":"The backbone of bipartite projections: inferring relationships from co-authorship, co-sponsorship, co-attendance and other co-behaviors","volume":"39","author":"Neal,","year":"2014","journal-title":"Soc. Netw."},{"key":"2023120904391760600_B5","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/j.physa.2007.08.015","article-title":"Ensemble inequivalence in random graphs","volume":"386","author":"Barr\u00e9,","year":"2007","journal-title":"Physica A"},{"key":"2023120904391760600_B6","doi-asserted-by":"crossref","first-page":"268701","DOI":"10.1103\/PhysRevLett.115.268701","article-title":"Breaking of ensemble equivalence in networks","volume":"115","author":"Squartini,","year":"2015","journal-title":"Phys. Rev. Lett."},{"key":"2023120904391760600_B7","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1007\/s10955-015-1212-2","article-title":"Equivalence and nonequivalence of ensembles: thermodynamic, macrostate, and measure levels","volume":"159","author":"Touchette,","year":"2015","journal-title":"J. Stat. Phys."},{"key":"2023120904391760600_B8","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1016\/j.aim.2009.12.001","article-title":"On the number of matrices and a random matrix with prescribed row and column sums and 0\u20131 entries","volume":"224","author":"Barvinok,","year":"2010","journal-title":"Adv. Math."},{"key":"2023120904391760600_B9","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1007\/s11336-008-9062-3","article-title":"An efficient MCMC algorithm to sample binary matrices with fixed marginals","volume":"73","author":"Verhelst,","year":"2008","journal-title":"Psychometrika"},{"key":"2023120904391760600_B10","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/rsa.20403","article-title":"Characterizing optimal sampling of binary contingency tables via the configuration model","volume":"42","author":"Blanchet,","year":"2013","journal-title":"Random Struct. Algorithms"},{"key":"2023120904391760600_B11","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.2140\/pjm.1957.7.1073","article-title":"A theorem on flows in networks","volume":"7","author":"Gale,","year":"1957","journal-title":"Pac. J. Math."},{"key":"2023120904391760600_B12","doi-asserted-by":"crossref","first-page":"371","DOI":"10.4153\/CJM-1957-044-3","article-title":"Combinatorial properties of matrices of zeros and ones","volume":"9","author":"Ryser,","year":"1957","journal-title":"Can. J. Math."},{"key":"2023120904391760600_B13","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1093\/comnet\/cnx014","article-title":"Generating bipartite networks with a prescribed joint degree distribution","volume":"5","author":"Boroojeni,","year":"2017","journal-title":"J. Complex Netw."},{"key":"2023120904391760600_B14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.18637\/jss.v024.i08","article-title":"Networksis: a package to simulate bipartite graphs with fixed marginals through sequential importance sampling","volume":"24","author":"Admiraal,","year":"2008","journal-title":"J. Stat. Softw."},{"key":"2023120904391760600_B15","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1214\/009053605000000822","article-title":"Sequential importance sampling for multiway tables","volume":"34","author":"Chen,","year":"2006","journal-title":"Ann. Stat."},{"key":"2023120904391760600_B16","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1002\/rsa.20155","article-title":"Sampling binary contingency tables with a greedy start","volume":"30","author":"Bez\u00e1kov\u00e1,","year":"2007","journal-title":"Random Struct. Algorithms"},{"key":"2023120904391760600_B17","article-title":"Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence","author":"Carstens,","year":"2018","journal-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2018)"},{"key":"2023120904391760600_B18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/ncomms5114","article-title":"A fast and unbiased procedure to randomize ecological binary matrices with fixed row and column totals","volume":"5","author":"Strona,","year":"2014","journal-title":"Nat. Commun."},{"key":"2023120904391760600_B19","doi-asserted-by":"crossref","first-page":"042812","DOI":"10.1103\/PhysRevE.91.042812","article-title":"Proof of uniform sampling of binary matrices with fixed row sums and column sums for the fast curveball algorithm","volume":"91","author":"Carstens,","year":"2015","journal-title":"Phys. Rev. E"},{"key":"2023120904391760600_B20","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1016\/j.mex.2018.06.018","article-title":"A unifying framework for fast randomization of ecological networks with fixed (node) degrees","volume":"5","author":"Carstens,","year":"2018","journal-title":"MethodsX"},{"key":"2023120904391760600_B21","first-page":"11:1","article-title":"Parallel and I\/O-efficient randomisation of massive networks using global curveball trades","volume-title":"26th Annual European Symposium on Algorithms (ESA 2018)","author":"Carstens,","year":"2018"},{"key":"2023120904391760600_B22","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher,","year":"2017"},{"key":"2023120904391760600_B23","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.socnet.2007.04.006","article-title":"Basic notions for the analysis of large two-mode networks","volume":"30","author":"Latapy,","year":"2008","journal-title":"Soc. Netw."},{"key":"2023120904391760600_B24","doi-asserted-by":"crossref","first-page":"23929","DOI":"10.1038\/s41598-021-03238-3","article-title":"Comparing alternatives to the fixed degree sequence model for extracting the backbone of bipartite projections","volume":"11","author":"Neal,","year":"2021","journal-title":"Sci. Rep."},{"key":"2023120904391760600_B25","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s13278-011-0021-0","article-title":"A systematic approach to the one-mode projection of bipartite graphs","volume":"1","author":"Zweig,","year":"2011","journal-title":"Soc. Netw. Anal. Mining"},{"key":"2023120904391760600_B26","doi-asserted-by":"crossref","first-page":"e0269137","DOI":"10.1371\/journal.pone.0269137","article-title":"backbone: an R package to extract network backbones","volume":"17","author":"Neal,","year":"2022","journal-title":"PLoS One"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/6\/cnac049\/47758701\/cnac049.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/6\/cnac049\/47758701\/cnac049.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T04:39:39Z","timestamp":1702096779000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnac049\/6885105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,27]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,10,27]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnac049","relation":{},"ISSN":["2051-1329"],"issn-type":[{"value":"2051-1329","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,12,1]]},"published":{"date-parts":[[2022,10,27]]},"article-number":"cnac049"}}