I need to generate a random binary matrix $(n, n)$ whose rows sums and columns sums are $4$.
I don't manage to find a quite efficient algorithm to do this. Have you an idea please ?
NB : The distribution should be uniform.
I'm not an expert in graph theory and I tried a direct method. First, I generate a matrix with the correct number of ones in the rows; then, I fix the columns.
rr (ss) are vectors with the indexes of the columns with missing (excess) ones. r and s are random draw from rr and ss. there must be at least one way to randomly swap a one with a zero in columns r and s. The if statements are due to the behavior of sample in R: sample(3,1) samples 1 element from 1:3, and does not provides 3. Hence, I check for its length.
10 matrices where n=200 and k=100 are generated in about 10 seconds on my AirBook and every matrix requires on average 110 fixes (out of 100*100=10000 entries).
I'm not yet familiar with the editor, polish my text if you wish. Hope this helps.
Expanding on Joriki's answer, you can use the algorithm inhttp://www.columbia.edu/~mo2291/Publications/DirectedRandomGraphs_29Jan13.pdf on page 7 or 8 to create a directed graph with outdegree 4 and I degree 4 at each vertex, with possible self-loops and multiple edges. Then you can exclude those with multiple edges. The directed adjacency matrix (a one in the i,j position means there is an edge from vertex i to j) gives you what you need.
The algorithm basically boils down to adding four random permutation matrices and changing the matrices if you get a 2 or higher in any entry. This is more efficient the larger $n$ is.
|show 3 more comments|