Efficient Generation of Networks with Given Expected Degrees
Efficient Generation of Networks with Given Expected Degrees
复制标题
具有给定预期度数的网络的高效生成
DOI：
10.1007/978-3-642-21286-4_10
复制
发表时间：
2011
影响因子：
1
通讯作者：
A. Hagberg
中科院分区：
文献类型：
--
作者：
Joel C. Miller;A. Hagberg
我们提出了一个有效的算法来生成具有给定序列的期望度的随机图。现有的算法运行时间为O（N2），其中N是节点数。我们证明了我们的算法运行在O（N +M）的预期时间，其中M是预期的边缘数。如果期望度是从有限均值分布中选择的，则当N → ∞时，这是O（N）。
We present an efficient algorithm to generate random graphs with a given sequence of expected degrees. Existing algorithms run in O(N2) time where N is the number of nodes. We prove that our algorithm runs in O(N +M) expected time where M is the expected number of edges. If the expected degrees are chosen from a distribution with finite mean, this is O(N) as N → ∞.