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

Question

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

pythonalgorithmrgraphnetworkx

7

我想生成一个具有小世界特性（呈幂律分布）的随机图。我刚开始使用networkx包，并发现它提供了各种随机图生成方法。请问是否可以生成一个给定节点度数遵循伽马分布的图形（无论是在R中还是使用Python的networkx包）？

- Legend

5个回答

2

我之前用基本的Python完成了这个...如果我没记错，我使用了以下方法。我是凭记忆写的，所以可能不完全准确，但希望对你有所帮助：

选择图中节点数N和密度（现有边数/可能边数），从而得出边数E。
为每个节点分配度数，首先选择一个随机正数x，并找到P(x)，其中P是您的概率密度函数。节点的度数是(P(x)*E/2)-1。
随机选择一个节点，并将其连接到另一个随机节点。如果任一节点已经达到其分配的度数，则从进一步选择中消除它。重复E次。

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

- JonC

谢谢你。这种方法与随机图创建类似（但不完全相同），但我担心的是，对于给定的度序列，我们不能保证构建一个简单的图形。但无论如何，感谢您的时间。 - Legend

似乎类似于这种方法的东西已经在networkx中实现了：random_degree_sequence_graph。 - toto_tico

1

包括上述内容，networkx 提供了4种算法，可以将 degree_distribution 作为输入参数：

configuration_model：由@eric解释
expected_degree_graph：基于每个节点的期望度数，使用概率方法。它不会给出精确的度数，而是一个近似值。
havel_hakimi_graph：这个尝试首先连接具有最高度数的节点
random_degree_sequence_graph：就我所见，这与@JonC建议的类似；它有一个trials参数，因为没有保证找到一个合适的配置。

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

我还找到了几篇论文：

- toto_tico

1

我知道这已经很晚了，但是您可以使用Mathematica完成同样的事情，尽管可能会更加直接。

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

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

- Workhorse

0

对于更一般和详细的实现，建议研究Britton等人在《生成具有预定度分布的简单随机图》中描述的算法。这可能比你所需的更详细，有些不切实际，但它提供了其他答案的潜在替代方案。

- gfaster

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aric · Accepted Answer

如果你想使用类似以下这样的配置模型，可以在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）...

NetworkX文档中提到了configuration_model的配置说明，给出了另一个示例、一个参考和如何去除平行边和自环的方法。

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()