fastball: a fast algorithm to randomly sample bipartite graphs with fixed degree sequences
fastball: a fast algorithm to randomly sample bipartite graphs with fixed degree sequences
复制标题
fastball：一种对具有固定度数序列的二分图进行随机采样的快速算法
DOI：
10.1093/comnet/cnac049
复制
发表时间：
2022
影响因子：
2.1
通讯作者：
Neal, Zachary P.
中科院分区：
文献类型：
--
作者：
Godard, Karl;Neal, Zachary P.
许多应用需要随机抽样具有固定度的二部图或随机抽样具有固定行和列和的关联矩阵。虽然存在几种采样算法，但“曲球”算法是最有效的，其渐近时间复杂度为，并且已被证明可以随机均匀采样。在这篇文章中，我们介绍了“快速球”算法，它采用了类似的方法，但有一个渐进的时间复杂度。我们表明，C实现的快速球随机采样大二分图固定度比曲线球快，并说明了这种更快的算法的价值在固定度序列模型的背景下，骨干提取。
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 ‘curveball’ algorithm is the most efficient with an asymptotic time complexity ofand has been proven to sample uniformly at random. In this article, we introduce the ‘fastball’ algorithm, which adopts a similar approach but has an asymptotic time complexity of. We show that a Cimplementation 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.