创建一个在 r (i.graph) 中有限制的关联矩阵

Question

我想为二分图 (N=M=200) 创建一个 (N*M)-关联矩阵。但是，必须考虑以下限制：

每列 i ( 1 , ... , 200 ) 的列总和为 g = 10
每一行的行总和为 h = 10
没有多边（关联矩阵中的值只取值[0:1]

到目前为止我有

M <- 200; # number of rows
N <- 200; # number of colums
g <- 10
I <- matrix(sample(0:1, M*N, repl=T, prob= c(1-g/N,g/N)), M, N);

有人有解决办法吗？

Answer 1

这里有一种方法可以满足您的需求。首先是算法思想，然后是它在 R.

中的实现

两步算法思路

你想要一个由 0 和 1 组成的矩阵，每行加起来是 10，每列加起来是 10。

第 1 步： 首先，创建一个简单的解决方案，如下所示：前 10 行的前 10 个元素为 1，然后是 190 个零。第二组十行的第 11 到第 20 个元素为 1，依此类推。换句话说，一个可行的解决方案是有一个全0的200x200矩阵，10x10 1的密集矩阵对角线嵌入，20次。

步骤 2： 随机排列整行和整列。在这个shuffle中，rowSum和columnSums被维护。

R 中的实现

我用一个更小的16x16矩阵来演示。在这种情况下，假设我们希望每一行和每一列加起来等于 4。（这个 colsum 必须是较大方矩阵维度的整数倍。）

n <- 4 #size of the smaller square
i <- c(1,1,1,1) #dense matrix of 1's
z <- c(0,0,0,0) #dense matrix of 0's

#create a feasible solution to start with:
m <- matrix(c(rep(c(i,z,z,z),n),
         rep(c(z,i,z,z),n),
         rep(c(z,z,i,z),n),
         rep(c(z,z,z,i),n)), 16,16)
         
#shuffle (Run the two lines following as many times as you like)
m <- m[sample(16), ] #shuffle rows
m <- m[ ,sample(16)] #shuffle columns

#verify that the sum conditions are not violated
colSums(m); rowSums(m)

#solution
print(m)

希望这能帮助您继续使用二分 igraph。

创建一个在 r (i.graph) 中有限制的关联矩阵

create an incidence matrix with restrictions in r (i.graph)

algorithm

r

graph

igraph

bipartite

两步算法思路

R 中的实现