Let an adjacency matrix $A={A^\top}\in {\mathbb{R}^{n \times n}}$ (a binary matrix) of a simple undirected graph and its degree matrix $D$ be given.
When adding $Q$ edges into the graph, which is equivalent to adding a $0$-$1$ perturbation matrix $E={E^\top}\in {\mathbb{R}^{n \times n}}$ (the number of 1's in $E$ is $Q$ and the position of 1's is not fixed) into the adjacency matrix $A$, we can get a perturbed adjacency matrix:
$$
\widetilde A = A + E
$$
and its perturbed degree matrix $\widetilde D$. Now let
$$
M := \frac{1}{2}({D^{ - 1}}A + {({D^{ - 1}}A)^2})
$$ and let its SVD (Singular Value Decomposition)
$$
M = U\Sigma {V^T}
$$ be known. After adding the perturbation matrix we get
$$
\begin{align}
\widetilde M &= \frac{1}{2}({\widetilde D^{ - 1}}\widetilde A + {({\widetilde D^{ - 1}}\widetilde A)^2})\\
\widetilde M &= \widetilde U\widetilde \Sigma {\widetilde V^\top}
\end{align}
$$ the last equation being its SVD.
Since every column of $U$ is ${u_i}$ and ${\widetilde u_i}$ is to $\widetilde U$, the question is
- how can I get the perturbation bound of ${\widetilde u_i}$?
- Otherwise, do there exists probabilistic methods that I can use to deal with this issue?
