relative perturbation edge changes are tied to node degree

[[concept]]

Let $\tilde{S} = S + D S + S D$ be a relative perturbation on $S$ . Locally, we have

\begin{aligned} {\tilde{S}}_{i j} & = S_{i j} + (D S)_{i j} + (S D)_{i j} \\ = S_{i j} + \sum_{k \in N (j)} D_{i k} S_{k j} + \sum_{k \in N (i)} S_{i k} D_{k i} \\ = S_{i j} + (\propto deg (j)) + (\propto deg (i)) \end{aligned}

This tells us that the edge changes in the perturbed graph is tied to the degrees of the nodes.

File
2025-03-10 graphs lecture 13