Return to Question

Given 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$ .

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$.

Let $M := \frac{1}{2}({D^{ - 1}}A + {({D^{ - 1}}A)^2})$ and its SVD is:

$M = U\Sigma {V^T}$ is known;

After being perturbed, we get :

$\widetilde M = \frac{1}{2}({\widetilde D^{ - 1}}\widetilde A + {({\widetilde D^{ - 1}}\widetilde A)^2})$ and its SVD:

$\widetilde M = \widetilde U\widetilde \Sigma {\widetilde V^\top}$

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}$.

Or are there any probabilistic methods that I can use to deal with this issue?

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?

Given an adjacency matrix $A={A^\top}\in {\mathbb{R}^{n \times n}}$ of a simple undirected graph and its degree matrix $D$ .

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$.

Let $M := \frac{1}{2}({D^{ - 1}}A + {({D^{ - 1}}A)^2})$ and its SVD is:

$M = U\Sigma {V^T}$ is known;

After being perturbed, we get :

$\widetilde M = \frac{1}{2}({\widetilde D^{ - 1}}\widetilde A + {({\widetilde D^{ - 1}}\widetilde A)^2})$ and its SVD:

$\widetilde M = \widetilde U\widetilde \Sigma {\widetilde V^\top}$

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}$.

Or are there any probabilistic methods that I can use to deal with this issue?

Given 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$ .

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$.

Let $M := \frac{1}{2}({D^{ - 1}}A + {({D^{ - 1}}A)^2})$ and its SVD is:

$M = U\Sigma {V^T}$ is known;

After being perturbed, we get :

$\widetilde M = \frac{1}{2}({\widetilde D^{ - 1}}\widetilde A + {({\widetilde D^{ - 1}}\widetilde A)^2})$ and its SVD:

$\widetilde M = \widetilde U\widetilde \Sigma {\widetilde V^\top}$

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}$.

Or are there any probabilistic methods that I can use to deal with this issue?