Re-sample a sparse matrix - keeping row- and column-sums constant Lets say I have a square matrix $A_{n\times n}$. It is a sparse matrix and let's assume that it only holds 0's and 1's. I wish to generate another matrix $B_{n\times n}$ with the following properties:


*

*All the row-sums and column-sums (or equivalently, the norms) are kept constant, i.e equal between $A$ & $B$.

*None of the 1's are in the same location in $B$ as they were in $A$.

*The diagonal elements of $B$ are all zero (this is also true of $A$). 
So basically, I want to re-sample a matrix (or a set of matrices $B_{i}$) that keeps that above resemblance and difference with $A$.
Of course there are no guarantees that this actually have a solution, but given a high level of sparsity and favorable distribution of the 1's, It should be possible.
The matrix correspond to a social network with unidirectional connections between the $n$ users ($a_{ij}$ 'likes' $a_{kl}$), and I need to sample a new network over the $n$ users that keeps the distribution of 'likes' and 'is liked by' constant over the users. 
Anyone with an idea of how to systematically generate this? I guess I could brute force it, moving the connections around and test for validity. But there might be some theoretical framework to formalize the process a bit.   
 A: If you pick a random zero-one matrix $B$ satisfying the row and column constraints, then (assuming $A$ was sufficiently sparse), it should have a decent probability of just working.
Here's how we can go about this, generalizing the "configuration model" approach to generating random regular graphs. 


*

*Generate a bunch of "row nodes" and "column nodes" as follows: if the $i$-th row of $A$ has $j$ ones in it, create row nodes $R_{i1}, R_{i2}, \dots, R_{ij}$, and if the $i$-th column of $A$ has $j$ ones in it, create column nodes $C_{i1}, C_{i2}, \dots, C_{ij}$. 

*The number of row nodes should be equal to the number of column nodes. Randomly permute the set of column nodes and then pair up each row node with a column node.

*Create $B$ by the following rule: whenever a row node $R_{ik}$ is paired with a column node $C_{j\ell}$, set $B_{ij}=1$, and set all other entries to $0$.


This can go wrong in several ways. We might end up setting some diagonal entries of $B$ to $1$, which is bad. We might also set the same entry $B_{ij}$ to $1$ several times, which is also bad, because then the row sums and column sums won't be correct.
Suppose that no row or column of $A$ had more than $\Delta$ ones, and that the total number of ones in $A$ is $m$, with $\delta n \le m \le \Delta n$. There are at most $n\Delta^2$ pairs of row and column nodes that could create a $1$ down the diagonal of $B$ if paired, and each is paired with probability $\frac1m$ more or less independently. So the average number of these is $\frac{n\Delta^2}{m} \le \Delta^2/\delta$, and the distribution is close to Poisson; with probability around $e^{-\Delta^2/\delta}$, this doesn't occur.
Similarly, the probability that row $i$ and column $j$ are paired twice is at most ${\Delta^2 \choose 2}\cdot \frac{1}{m^2} < \frac{\Delta^4}{2\delta^2 n^2}$, and there are $n^2$ pairs $(i,j)$ to worry about. Again, these are almost independent, so the distribution of the number of such bad pairs is close to Poisson with mean at most $\frac{\Delta^4}{2\delta^2n^2} \cdot n^2 = \frac{\Delta^4}{2\delta^2}$; with probability around $e^{-\Delta^4/2\delta^2}$, there are no bad pairs.
So with this method, we'll have to make around $e^{x + x^2/2}$ trials (where $x = \frac{\Delta^2}{\delta}$) before we obtain a matrix $B$ that satisfies all the properties you want. If $x$ is not too large, then this is not a problem. The resulting matrix $B$ has the bonus property of being uniformly chosen from all possible matrices that satisfy these constraints.
