生成具有特定度数分布的图？

Question

我正在尝试生成一个具有小世界特性的随机图（也就是符合幂律分布的图）。我刚开始使用networkx这个库，发现它提供了多种随机图的生成方法。有人能告诉我，是否可以生成一个图，使得某个特定节点的连接数（也就是度）遵循伽马分布吗？这个可以用R语言或者Python的networkx库来实现吗？

Answer 1

我知道这个回答来得有点晚，不过你可以用mathematica做同样的事情，方法会简单一些。

RandomGraph[DegreeGraphDistribution[{3, 3, 3, 3, 3, 3, 3, 3}], 4]

这个代码会生成4个随机图，每个节点都有指定的连接数。

Answer 2

我之前在基础的Python中做过这个...如果我没记错的话，我用了以下方法。记忆可能不完全准确，但希望对你有帮助：

1. 首先决定图中节点的数量N，以及密度D（现有边数与可能边数的比值）。这就决定了边的数量E。
2. 对于每个节点，先随机选择一个正数x，然后找到P(x)，其中P是你的概率密度函数（pdf）。这个节点的度数就是(P(x)*E/2) - 1。
3. 随机选择一个节点，并将它连接到另一个随机节点。如果任一节点已经达到了它的度数，就把它从后续选择中去掉。重复这个过程E次。

注意，这样做一般不会生成一个连通的图。

Answer 3

如果你想使用配置模型，类似下面的代码在NetworkX中应该可以工作：

import random 
import networkx as nx
z=[int(random.gammavariate(alpha=9.0,beta=2.0)) for i in range(100)]
G=nx.configuration_model(z)

你可能需要根据伽马分布中的参数来调整序列z的平均值。此外，z不一定要是图形的（这样会得到一个多重图），但它的总和必须是偶数，所以你可能需要尝试几个随机序列（或者加1）...

NetworkX的文档中关于配置模型的说明提供了另一个例子、参考资料，以及如何去掉平行边和自环：

Notes
-----
As described by Newman [1]_.

A non-graphical degree sequence (not realizable by some simple
graph) is allowed since this function returns graphs with self
loops and parallel edges.  An exception is raised if the degree
sequence does not have an even sum.

This configuration model construction process can lead to
duplicate edges and loops.  You can remove the self-loops and
parallel edges (see below) which will likely result in a graph
that doesn't have the exact degree sequence specified.  This
"finite-size effect" decreases as the size of the graph increases.

References
----------
.. [1] M.E.J. Newman, "The structure and function
       of complex networks", SIAM REVIEW 45-2, pp 167-256, 2003.

Examples
--------
>>> from networkx.utils import powerlaw_sequence
>>> z=nx.create_degree_sequence(100,powerlaw_sequence)
>>> G=nx.configuration_model(z)

To remove parallel edges:

>>> G=nx.Graph(G)

To remove self loops:

>>> G.remove_edges_from(G.selfloop_edges())

这里有一个类似于http://networkx.lanl.gov/examples/drawing/degree_histogram.html的例子，它展示了一个包含最大连通组件图形布局的绘图：

#!/usr/bin/env python
import random
import matplotlib.pyplot as plt
import networkx as nx

def seq(n):
    return [random.gammavariate(alpha=2.0,beta=1.0) for i in range(100)]    
z=nx.create_degree_sequence(100,seq)
nx.is_valid_degree_sequence(z)
G=nx.configuration_model(z)  # configuration model

degree_sequence=sorted(nx.degree(G).values(),reverse=True) # degree sequence
print "Degree sequence", degree_sequence
dmax=max(degree_sequence)

plt.hist(degree_sequence,bins=dmax)
plt.title("Degree histogram")
plt.ylabel("count")
plt.xlabel("degree")

# draw graph in inset 
plt.axes([0.45,0.45,0.45,0.45])
Gcc=nx.connected_component_subgraphs(G)[0]
pos=nx.spring_layout(Gcc)
plt.axis('off')
nx.draw_networkx_nodes(Gcc,pos,node_size=20)
nx.draw_networkx_edges(Gcc,pos,alpha=0.4)

plt.savefig("degree_histogram.png")
plt.show()