Many applications require randomly sampling bipartite graphs with fixed degrees, or randomly sampling incidence matrices with fixed row and column sums. Although several algorithms to perform this sampling have been proposed, the "curveball" algorithm is the most efficient, running in O(n log n) time, and has been proven to sample uniformly at random. In this paper, we introduce the "fastball" algorithm, which adopts a similar approach but runs in O(n) time. We show that fastball allows the random sampling of large bipartite graphs with fixed degrees roughly five times faster than curveball.
翻译：许多应用程序都要求随机抽样使用固定度的双边图表,或随机抽样使用固定行数和列数总和的发生率矩阵。 虽然提出了进行这一抽样的几种算法,但“曲线”算法是最有效的,在O(nlog n)时间运行,并被证明可以统一随机抽样。在本文件中,我们引入了“快球”算法,该算法采用了类似方法,但在O(n)时间运行。我们显示快速球允许随机抽样使用固定度约为曲线速五倍的大型双边图形。
相关内容
微信扫码咨询专知VIP会员