Generate random binary matrix

3 views (last 30 days)
Meng
Meng on 16 Oct 2013
Commented: Meng on 18 Oct 2013
Given the number of nodes M and number of links, I want to generate a random M by N matrix with 0 and 1 entries but with the constraints that the sum of each row is a random integer between 1 and L, and the sum of each column is a random integer between 1 and S. Here L and S are integers greater than 1.
Thanks for any hint and help.
David

Answers (2)

Jos (10584)
Jos (10584) on 16 Oct 2013
Should all possibilities of such a matrix be equally likely? Then it might be very quite tricky.
Here's a brute force approach, that might not always work for specific values of S, L, M and N:
M = 5 ; N = 6 ;
S = 3 ; L = 2 ;
% fix the number of 1's per row
X = zeros(M,N) ;
sumRow = ceil(S*rand(M,1)) ;
for k=1:M,
X(k,1:sumRow(k)) = 1 ;
end
ntries = 0 ;
while ntries < 1000 ;
ntries = ntries + 1 ;
% randomly swap columns, see RANDSWAP on the File Exchange
for k=1:M,
p = randperm(N) ;
X(k,:) = X(k,p) ;
end
if all(sum(X,1) <= L) && all(sum(X,1)>0)
break ;
end
end
if ntries < 1000
disp(X)
sumCol = sum(X,1)
sumRow = sum(X,2).'
else
disp('No matrix found within a reasonable time') ;
end
  3 Comments
Jan
Jan on 16 Oct 2013
@Meng: Please do not write "larger", but show us the typical and maximum size. The applied method depends critically on the magnitude of the problem. An efficient solution for a 8x8 matrix and S=L=4 must differ from M=N=1e6 and S=L=1e4.
Meng
Meng on 18 Oct 2013
@Simon: Typically, the matrix is very sparse. For example, M=150, N=60, L=8,S=15.

Sign in to comment.


Jan
Jan on 16 Oct 2013
You can try a "shooting method":
  1. Start with a matrix of zeros
  2. Determine a line and column, which differ the most from the criteria
  3. Set a 1 there
  4. Loop
A genetic algorithm might be fine also:
  1. Start with 100 random matrices
  2. Select the 10 with the smallest sum of deviations from the criteria
  3. For each of them create 10 children by setting 10% (and 9% later etc) of the elements randomly
  4. Perhaps some cross-overs of blocks between the best individuals
  5. Loop to 2.

Categories

Find more on Creating and Concatenating Matrices in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!