Given an undirected graph $G$ which has $n$ nodes and $m$ edges, and its adjacency matrix is $A$, which is a $n \times n$ $0$-$1$ matrix, $r(A)$ is the rank of $A$, when I add randomly $x$ edges into the graph $G$, we can get a perturbed matrix $\widetilde A$:
$\widetilde A = A + E$
where $E$ is the perturb matrix which is also a $0$-$1$ matrix and it has $2x$ "$1$" entries. The location of these "$1$" entries is not fixed. Note that $\widetilde A$ is still a symmetric matrix.
The question is how can I get the rank of $\widetilde A$, that is, $r(\widetilde A)$.