为所有节点创建具有相同进出度的矩阵 [英] Create matrix with same in and out degree for all nodes

问题描述

我已经用图论的术语提出了这个问题，但是概念化不是必需的.

I've stated this question in graph theory terms, but that conceptualization isn't necessary.

我要使用Python进行的操作是产生一个零和一的矩阵，其中每一行具有相同的个数，而每一列具有相同的个数.当行数(发送节点)不等于列数(接收节点)时，行数将与列数不同-这是我允许的.

What I'm trying to do, using Python, is produce a matrix of zeros and ones, where every row has the same number of ones and every column has the same number of ones. The number for rows will not be the same as the number for columns when the number of rows (sending nodes) does not equal the number of columns (receiving nodes) -- which is something I'm allowing.

在 numpy 中执行此操作对我来说很有意义，但是可能会有其他软件包(例如 networkx ?)会有所帮助.

It makes sense to me to do this in numpy, but there may be other packages (like networkx?) that would help.

这是我想要用所需的输入和输出编写的功能:

Here's the function I'm looking to write with the desired inputs and outputs:

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]]

请注意，每一列和每一行都有两个.除此约束外，这些函数的位置还应该是随机的(并且此函数的调用之间会有所不同).

Notice, every column and every row has two ones in it. Aside from this constraint, the positions of the ones should be random (and vary from call to call of this function).

用图论的术语来说，这意味着每个节点的入度为2，出度为2(所有可能的连接的50％，如 p = 0.5 所指定)./p>

In graph theory terms, this means every node has an in-degree of 2 and an out-degree of 2 (50% of all possible connections, as specified with p = 0.5).

推荐答案

对于方阵，您所描述的是随机 k正则有向图，并且已知的算法可以生成此类图. igraph 实现了一个:

For a square matrix, what you describe is the adjacency matrix of a random k-regular directed graph, and there are known algorithms to generate such graphs. igraph implements one:

# 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 has a function for random k-regular undirected graphs:

networkx.random_regular_graph(k, n)

对于非正方形矩阵，您所描述的内容与随机 双正则图.我发现对于随机双正则图没有方便的现有实现方式，但是该术语应该是搜索已知算法的良好起点.

For a non-square matrix, what you describe is isomorphic to a random biregular graph. I have found no convenient existing implementation for random biregular graphs, but the term should be a good starting point for searching for known algorithms.

这篇关于为所有节点创建具有相同进出度的矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！