我正在尝试了解Python或R中是否存在与图论相关的模块功能,可以从度分布(或一旦设置顶点数量即表示为序列)开始,并生成满足规定度序列的(随机)图形。
例如,我们可能会得到以下分布:p =(0.179、0.49、0.34)
,它们是度值1,2和3
的概率。因此,我们可以将顶点数设置为n = 500
,将p
映射到度序列deseq
列表:用1
填充0.179*n
次,以此类推。
任何对先前讨论过此类问题或库建议的指针都将非常有帮助。
我正在尝试了解Python或R中是否存在与图论相关的模块功能,可以从度分布(或一旦设置顶点数量即表示为序列)开始,并生成满足规定度序列的(随机)图形。
例如,我们可能会得到以下分布:p =(0.179、0.49、0.34)
,它们是度值1,2和3
的概率。因此,我们可以将顶点数设置为n = 500
,将p
映射到度序列deseq
列表:用1
填充0.179*n
次,以此类推。
任何对先前讨论过此类问题或库建议的指针都将非常有帮助。
在学会如何使用R和Python中的igraph生成所需类型的图形后,以下是我回答自己问题的尝试。
为了举例说明,假设有以下度数序列:总节点数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 中的 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()
和获得的直方图:
对于Python,networkx 包也提供了您所需要的内容。
特别是,关于从度序列生成随机图的功能(例如使用 @Alex_6 评论中的想法的 configuration_model
)可能会有所帮助。