为所有节点创建具有相同入度和出度的矩阵

Question

我已经用图论术语说明了这个问题，但没有必要概念化。

我想做的是，使用 Python，生成一个由 0 和 1 组成的矩阵，其中每一行都有相同数量的 1，每一列都有相同数量的 1。当行数（发送节点）不等于列数（接收节点）时，行数将与列数不同——这是我允许的。

对我来说，在 numpy 中执行此操作很有意义，但可能还有其他软件包（如 networkx？）会有所帮助。

这是我希望使用所需输入和输出编写的函数：

n_pre = 4  # number of nodes available to send a connection
n_post = 4  # number of nodes available to receive a connection
p = 0.5  # proportion of all possible connections that exist

mat = generate_mat(n_pre, n_post, p)

print mat

输出将是，例如：

[[0, 1, 0, 1],
 [1, 0, 1, 0],
 [1, 1, 0, 0],
 [0, 0, 1, 1]]

注意，每一列和每一行都有两个。除了这个限制，它们的位置应该是随机的（并且随着这个函数的调用而变化）。

在图论术语中，这意味着每个节点的入度为 2，出度为 2（所有可能连接的 50%，由 p = 0.5 指定）。

Answer 1

首先做前期工作，得到方阵的大小和每行每列的人口pop。现在，用 pop 个对角线初始化一个矩阵。对于 n = 6 和 pop = 3，你有

[[1, 1, 1, 0, 0, 0]
 [0, 1, 1, 1, 0, 0]
 [0, 0, 1, 1, 1, 0]
 [0, 0, 0, 1, 1, 1]
 [1, 0, 0, 0, 1, 1]
 [1, 1, 0, 0, 0, 1]]

现在，将您的友好邻居 random shuffle 操作应用于列，然后是行（或以其他顺序）。这是你的矩阵。仅行或仅列的洗牌不会改变任一轴上的人口。

Answer 2

对于方阵，你描述的是一个随机的邻接矩阵k-regular directed graph，并且有已知的算法来生成这样的图。 igraph 实现一个：

# I think this is how you call it - it's an instance method for some reason.
igraph.Graph().K_Regular(n, k, directed=True)

networkx 具有随机 k-正则无向图的函数：

networkx.random_regular_graph(k, n)

对于非方阵，你所描述的是同构于随机biregular graph。我发现随机双正则图没有方便的现有实现，但该术语应该是搜索已知算法的良好起点。

为所有节点创建具有相同入度和出度的矩阵

Create matrix with same in and out degree for all nodes

python

algorithm

numpy

graph-theory

matrix