在两个值之间随机分配矩阵元素，同时保持行和列之和固定(MATLAB) [英] Randomize matrix elements between two values while keeping row and column sums fixed (MATLAB)

问题描述

我有一个技术问题，但是我觉得使用MATLAB强大的工具集应该可以实现.

I have a bit of a technical issue, but I feel like it should be possible with MATLAB's powerful toolset.

我所拥有的是一个0和w的n×n随机矩阵，比如说是用

What I have is a random n by n matrix of 0's and w's, say generated with

A=w*(rand(n,n)<p);

w的典型值为3000，但这并不太重要.

A typical value of w would be 3000, but that should not matter too much.

现在，这个矩阵有两个重要的量，向量

Now, this matrix has two important quantities, the vectors

c = sum(A,1); 
r = sum(A,2)';

这是两个行向量，第一个表示每列的总和，第二个表示每行的总和.

These are two row vectors, the first denotes the sum of each column and the second the sum of each row.

接下来我要对w的每个值进行随机化，例如在0.5和2之间进行随机化.

What I want to do next is randomize each value of w, for example between 0.5 and 2. This I would do as

rand_M = (0.5-2).*rand(n,n) + 0.5
A_rand = rand_M.*A;

但是，我不想只选择这些随机数:我希望它们是这样的:对于每一列和每一行，总和仍等于c和r的元素.所以说一下，我们定义一下

However, I don't want to just pick these random numbers: I want them to be such that for every column and row, the sums are still equal to the elements of c and r. So to clean up the notation a bit, say we define

A_rand_c = sum(A_rand,1);
A_rand_r = sum(A_rand,2)';

我希望所有j = 1:n, A_rand_c(j) = c(j)和A_rand_r(j) = r(j)都需要.

I want that for all j = 1:n, A_rand_c(j) = c(j) and A_rand_r(j) = r(j).

我正在寻找一种以我认为的算法方式重绘rand_M元素的方法，以便最终满足这些要求.

What I'm looking for is a way to redraw the elements of rand_M in a sort of algorithmic fashion I suppose, so that these demands are finally satisfied.

现在，当然，除非我有无限的时间，否则这可能不会真正发生.因此，我接受这些数量落入特定范围内:A_rand_c(j)必须是[(1-e)*c(j),(1+e)*c(j)]的元素，并且是[(1-e)*r(j),(1+e)*r(j)]的A_rand_r(j)的元素.我事先定义了这个e，例如0.001之类的.

Now of course, unless I have infinite amounts of time this might not really happen. I therefore accept these quantities to fall into a specific range: A_rand_c(j) has to be an element of [(1-e)*c(j),(1+e)*c(j)] and A_rand_r(j) of [(1-e)*r(j),(1+e)*r(j)]. This e I define beforehand, say like 0.001 or something.

在找到解决方法的过程中，有人可以帮助我吗?我尝试了一种方法，我只是随机地重新输入数字，但这确实无法解决任何问题.它也不必疯狂高效，我只需要它在有限的时间内对规模为n = 50的网络起作用.

Would anyone be able to help me in the process of finding a way to do this? I've tried an approach where I just randomly repick the numbers, but this really isn't getting me anywhere. It does not have to be crazy efficient either, I just need it to work in finite time for networks of size, say, n = 50.

很明显，最终输出是满足这些约束的矩阵A_rand.

To be clear, the final output is the matrix A_rand that satisfies these constraints.

好吧，因此经过一番思考，我认为它可以通过while语句来实现，它遍历了矩阵的每个元素.困难的部分是有四种可能性:如果您在特定元素A_rand(i,j)中，则A_rand_c(j)和A_rand_r(i)可能都太小，太大或相反.前两种情况很好，因为您可以重新绘制随机数，直到它小于当前值并改善情况.但是其他两种情况都是有问题的，因为您将改善一种情况，但不会改善另一种情况.我猜想它必须看看哪个标准不那么令人满意，以便尝试解决更糟糕的标准.但这不是一件容易的事..

Alright, so after thinking a bit I suppose it might be doable with some while statement, that goes through every element of the matrix. The difficult part is that there are four possibilities: if you are in a specific element A_rand(i,j), it could be that A_rand_c(j) and A_rand_r(i) are both too small, both too large, or opposite. The first two cases are good, because then you can just redraw the random number until it is smaller than the current value and improve the situation. But the other two cases are problematic, as you will improve one situation but not the other. I guess it would have to look at which criteria is less satisfied, so that it tries to fix the one that is worse. But this is not trivial I would say..

推荐答案

您可以利用以下事实:在A中具有单个非零条目的行/列会自动为您提供.如果A(2,5) = w并且它是其列中唯一的非零条目，则A_rand(2,5) = w也是如此.还有什么呢?

You can take advantage of the fact that rows/columns with a single non-zero entry in A automatically give you results for that same entry in A_rand. If A(2,5) = w and it is the only non-zero entry in its column, then A_rand(2,5) = w as well. What else could it be?

您可以在查找这些单项行/列和为值无关紧要的条目分配随机数之间进行选择.

You can alternate between finding these single-entry rows/cols, and assigning random numbers to entries where the value doesn't matter.

这是流程的框架:

• A_rand=zeros(size(A))是您要填充的矩阵
• entries_left = A>0是一个二进制矩阵，显示了您仍然需要填写A_rand中的哪些条目
• col_totals=sum(A,1)是您仍需要在A_rand
的每一列中添加的数量
• row_totals=sum(A,2)是您仍需要在A_rand
的每一行中添加的数量

• A_rand=zeros(size(A)) is the matrix you are going to fill
• entries_left = A>0 is a binary matrix showing which entries in A_rand you still need to fill
• col_totals=sum(A,1) is the amount you still need to add in every column of A_rand
• row_totals=sum(A,2) is the amount you still need to add in every row of A_rand

while sum( entries_left(:) ) > 0

% STEP 1:
% function to fill entries in A_rand if entries_left has rows/cols with one nonzero entry
% you will need to keep looping over this function until nothing changes
% update() A_rand, entries_left, row_totals, col_totals every time you loop

% STEP 2:
% let (i,j) be the indeces of the next non-zero entry in entries_left
% assign a random number to A_rand(i,j) <= col_totals(j) and <= row_totals(i)
% update() A_rand, entries_left, row_totals, col_totals

end

update()
    A_rand(i,j) = random_value;
    entries_left(i,j) = 0;
    col_totals(j) = col_totals(j) - random_value;
    row_totals(i) = row_totals(i) - random_value;
end

为random_value选择范围可能有些棘手.我能想到的最好的办法是从一个以N*w*p为中心的相对窄的分布中提取它，其中p是A中某个条目为非零的概率(这是行/列总数的平均值).

Picking the range for random_value might be a little tricky. The best I can think of is to draw it from a relatively narrow distribution centered around N*w*p where p is the probability of an entry in A being nonzero (this would be the average value of row/column totals).

这不能很好地扩展到大型矩阵，因为它将随着n^2复杂度的增长而增长.我对其进行了200 x 200矩阵测试，并在大约20秒内完成了工作.

This doesn't scale well to large matrices as it will grow with n^2 complexity. I tested it for a 200 by 200 matrix and it worked in about 20 seconds.

这篇关于在两个值之间随机分配矩阵元素，同时保持行和列之和固定(MATLAB)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！