在 Python 或 R 中为给定度数序列生成图

Question

我正在尝试了解在 Python 或 R 中是否存在与图论相关的模块功能，这些功能可以使人们从度分布开始（或者一旦我们设置了顶点数就表示为序列），并生成（随机) 满足规定度数序列的图。例如，我们可能会得到以下分布：p=(0.179,0.49,0.34)分别是度值1,2和的概率3。所以我们可以设置顶点的个数，n=500,映射p到一个度数序列deseq表：填充的0.179*n次数1,等等。任何指向先前讨论过的此类问题或库建议的案例都会非常有帮助。

Answer 1

在学习了如何在 R 和 Python 中使用 igraph 来生成所需类型的图之后，这是我自己的问题的尝试。

在 R 中：

出于本示例的目的，我们假设以下度数序列：总节点n=20, 5,10和分别5具有度数1,2,和的节点3。c()我们使用和创建度数序列，rep().然后我们将使用sample_degseq()fromigraph生成与上述度数序列对应的图形。然后我们将绘制其度数直方图以进行完整性检查。

首先使用以下命令在 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()

和得到的直方图：

Answer 2

我不知道您已经对该主题进行了多少研究，但是在 R 中有一个非常知名的包，在 Python 中有一个名为igraph的模块。它可能有你想要的。

Answer 3

对于 Python，networkx包还提供了您正在寻找的内容。

特别是，来自度数序列的随机图的功能（例如configuration_model，来自@Alex_6 评论的想法）可能会有所帮助。