python - Generating graphs for given degree sequence in Python or R

Question

I am trying to learn if in Python or R, there exist within the graph-theory related modules features that would enable one to start from a degree distribution (or expressed as a sequence once we set the number of vertices), and generate (random) graphs that satisfy the prescribed degree sequence.

As an example, we might be given the following distribution: p=(0.179,0.49,0.34) which are the probabilities of degree values 1,2 and 3 respectively. So we can set the number of vertices, n=500, map p to a degree sequence deseq list: filled with 0.179*n times of 1, and so on for the rest.

Any pointers towards previously discussed cases for such problems or library suggestions would be very helpful.

标签： pythonrgraph-theory

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

和得到的直方图：