生成一个给定的度分布的图
参考文献：《Efficient and Simple Generation of Random Simple Connected Graphs with Prescribed Degree Sequence》2006
这篇文章讲的是如何快速生成一个满足指定度分布的图，并不包含具体完整的算法，只能做引用文献使用，另外，文章引用部分给定了代码网址，只可惜现在无法访问了。
谷歌时，尽可能用专业一点的英文进行搜索，会有惊喜！
比如，这个我使用的搜索关键词为：
github generates a random graph with prescribed degree sequence
，然后就找到了相关的知识，在
igraph
和
networkx
的包中，应该是都直接有指定的接口。
初步选定
networkx
中的Degree Sequence中的接口：
random_degree_sequence_graph(sequence, seed=None, tries=10)
Networkx-5.8-Degree Sequence
生成具有给定度序列或预期度序列的图
给定函数：
configuration_model(deg_sequence[, . . . ])
Return a random graph with the given degree sequence.
directed_configuration_model(. . . [, . . . ])
Return a directed_random graph with the given degree sequences.
expected_degree_graph(w[, seed, selfloops])
Return a random graph with given expected degrees.
havel_hakimi_graph(deg_sequence[, create_using])
Return a simple graph with given degree sequence constructed using the Havel-Hakimi algorithm.
directed_havel_hakimi_graph(in_deg_sequence,. . . )
Return a directed graph with the given degree sequences.
degree_sequence_tree(deg_sequence[, . . . ])
Make a tree for the given degree sequence.
random_degree_sequence_graph(sequence[, . . . ])
Return a simple random graph with the given degree sequence.
使用最后一个函数，该模型来自于文章：
《A Sequential Algorithm for Generating Random Graphs》 2009，引用应使用这篇文章。
random_degree_sequence_graph(sequence[, . . . ])
标准形式：
random_degree_sequence_graph(sequence, seed=None, tries=10)
返回：一个给定度序列的简单随机图
如果最大度
d
m
d_{m}
d
m
在这个序列中是
O
(
m
1
4
)
O(m^{\frac{1}{4}})
O
(
m
4
1
)
，那么这个算法将产生几乎均匀的随机图在
O
(
m
d
m
)
O(md_{m})
O
(
m
d
m
)
时间内，这里
m
m
m
是边的数量。
参数
：
sequence (list of integers) – 度的序列，使用一个list给出
seed (hashable object, optional) – 用于生成图的随机种子，这一个默认为
None
tries (int, optional) – 创建一个图最大的尝试次数，因为该模型不一定保证能创建出指定度序列的图，有时，指定度序列本身不存在
返回值
：
Return G，返回指定度序列的图，nodes被标记为从0开始，索引对应给定序列中的位置。
返回值类型：networkx中的对象 Graph
抛出异常
：
NetworkXUnfeasible – 如果给定度分布不满足成为一个图
NetworkXError – 在给定达到给定尝试次数之后仍然不能形成一个图
注意
：
这个生成算法并不能保证产生一个图
例子
：
>>> sequence = [1, 2, 2, 3]
>>> G = nx.random_degree_sequence_graph(sequence)
>>> sorted(d for n, d in G.degree())
[1, 2, 2, 3]
生成指定度分布图
生成序列
生成一个指定度按幂律分布，系数为2.5的图
生成序列使用如下函数：
random_powerlaw_tree_sequence(n, gamma=3, seed=None, tries=100)
该函数返回一个幂律分布的度序列
参数
：
n (int,) – The number of nodes.
gamma (float) – Exponent of the power law.
seed (int, optional) – Seed for random number generator (default=None).
tries (int) – Number of attempts to adjust the sequence to make it a tree.
抛出异常
：
NetworkXError – If no valid sequence is found within the maximum number of attempts.
注意：
A trial power law degree sequence is chosen and then elements are swapped with new elements from a power law distribution until the sequence makes a tree (by checking, for example, that the number of edges is one smaller than the number of nodes).
事实证明，这个函数对于小数据还可以，大数据量就生成不了了。
自行生成序列
黎曼zeta函数对应取值，即分母：
| 1.5 | 1.6 | 1.7 | 1.8 | 1.9 | 2.0 | 2.1 | 2.2 | 2.3 |
|---|---|---|---|---|---|---|---|---|
| 2.612 | 2.285 | 2.054 | 1.882 | 1.749 | 1.645 | 1.560 | 1.491 | 1.432 |
|
2.4 |
2.5 |
2.6 |
2.7 |
2.8 |
2.9 |
3.0 |
3.1 |
3.2 |
| 1.383 | 1.341 | 1.305 | 1.274 | 1.247 | 1.223 | 1.202 | 1.183 | 1.167 |
|
3.3 |
3.4 |
3.5 |
3.6 |
3.7 |
3.8 |
3.9 |
4.0 |
|
| 1.152 | 1.138 | 1.127 | 1.116 | 1.106 | 1.097 | 1.089 | 1.082 |
多计算几个值：
| 1.01 | 1.03 | 1.05 | 1.07 | 1.09 | 1.1 | 1.2 | 1.3 | 1.4 |
|---|---|---|---|---|---|---|---|---|
| 15.464 | 13.359 | 11.647 | 10.245 | 9.090 | 8.589 | 5.393 | 3.905 | 3.101 |
本想通过概率计算出每个节点对应的度大小，然后取样后形成生成序列，最终调用接口生成图。
每个节点占比来源于公式：
P
(
k
)
=
k
−
λ
∑
k
=
1
+
∞
k
−
λ
P(k)=\frac{k^{-\lambda}}{\sum_{k=1}^{+\infty}k^{-\lambda}}
P
(
k
)
=
∑
k
=
1
+
∞
k
−
λ
k
−
λ
实验证明，networkx速度超级慢，1000个节点都是几分钟，更别说一个小目标100000了
解决方案
使用SNAP提供的库解决，相关内容见博客：