用Python或R生成给定度序列的图

Question

我正在尝试了解Python或R中是否存在与图论相关的模块功能，可以从度分布（或一旦设置顶点数量即表示为序列）开始，并生成满足规定度序列的（随机）图形。

例如，我们可能会得到以下分布：p =（0.179、0.49、0.34），它们是度值1,2和3的概率。因此，我们可以将顶点数设置为n = 500，将p映射到度序列deseq列表：用1填充0.179*n次，以此类推。

任何对先前讨论过此类问题或库建议的指针都将非常有帮助。

- user929304

---

非常有趣，但我认为创建一个特定的模块来实现这一点太过精确了。但是你可以从你的分布中创建一个度数列表，然后使用配置模型从这个序列生成一个图形：https://en.wikipedia.org/wiki/Configuration_model - Alex_6

Answer 1

在学会如何使用R和Python中的igraph生成所需类型的图形后，以下是我回答自己问题的尝试。

In R:

为了举例说明，假设有以下度数序列：总节点数n=20，其中5,10个节点的度数分别为1,2,以及3，我们可以使用c()和rep()创建这个度数序列。然后，我们将使用igraph中的sample_degseq()生成与上述度数序列相对应的图形。接下来，我们绘制其度数直方图以进行检查。

首先，在R控制台中安装并调用igraph模块：

install.packages("igraph")
library(igraph)

现在我们可以按照描述进行：

degreels <- c(rep(1,5),rep(2,10),rep(3,5))
graph <- sample_degseq(degreels, method="simple")
degreehist <- hist(degree(graph))
is.connected(graph)

使用 Python：

现在让我们使用 Python 中的 igraph 模块来完成完全相同的事情:

要安装请看这里。

import igraph as ig
import matplotlib.pyplot as plt

degcounts = [5,10,5]
degreels = []
for i in range(len(degcounts)):
    degreels += degcounts[i]*[i+1]

graph = ig.GraphBase.Degree_Sequence(degreels,method="simple")
plt.hist(graph.degree())
plt.show()

和获得的直方图：

- user929304

---

我不知道这是用来干什么的，但图论很有趣。 - MrCorote

Answer 2

我不知道你已经在这个主题上研究了多少，但是在R语言中有一个相当著名的包，在Python中有一个模块叫做igraph。它可能有你所寻找的内容。

- MrCorote

---

@BenBolker 我可以这样做，但我回答自己的问题可以吗？ - user929304

是的，实际上鼓励您回答自己的问题：https://stackoverflow.com/help/self-answer - Ben Bolker

@BenBolker 瞧！:) - user929304

Answer 3

对于Python，networkx 包也提供了您所需要的内容。

特别是，关于从度序列生成随机图的功能（例如使用 @Alex_6 评论中的想法的 configuration_model）可能会有所帮助。

- lm1909