7

我正在尝试生成一个具有小世界属性的随机图（表现出幂律分布）。我刚开始使用 networkx 包，发现它提供了多种随机图生成。有人可以告诉我是否可以生成一个图，其中给定节点的度数遵循伽马分布（在 R 中或使用 python 的 networkx 包）？

4

4 回答 4

7

如果你想使用这样的配置模型，应该在 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)

您可能需要根据 gamma 分布中的参数调整序列 z 的平均值。z也不需要是图形的（你会得到一个多重图），但它确实需要一个偶数，所以你可能不得不尝试一些随机序列（或加1）......

Configuration_model 的 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()
于 2010-12-01T21:32:11.280 回答
2

我不久前在基础 Python 中做过这个...... IIRC，我使用了以下方法。根据记忆，所以这可能并不完全准确，但希望它是值得的：

  1. 选择图中的节点数 N 和密度（可能边上的现有边） D。这意味着边数 E。
  2. 对于每个节点，通过首先选择一个随机正数 x 并找到 P(x) 来分配其度数，其中 P 是您的 pdf。节点的度数为 (P(x)*E/2) -1。
  3. 随机选择一个节点，并将其连接到另一个随机节点。如果任一节点已实现其分配的程度，则将其从进一步选择中删除。重复 E 次。

请注意，这通常不会创建连通图。

于 2010-12-01T20:58:29.073 回答
1

我知道这已经很晚了，但是您可以使用mathematica 做同样的事情，尽管更简单一些。

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

这将生成 4 个随机图，每个节点都具有规定的度数。

于 2013-10-06T04:35:17.333 回答
1

包括上面提到的，networkx提供了 4 种接收 degree_distribution 作为输入的算法：

完整列表（包括有向图算法的某些版本）在这里。

我还找到了几篇论文：

于 2017-07-25T17:24:32.157 回答