relative perturbations

$$E(S,\tilde{S})=\{D:P^{T}SP=S+DS+SD,P\in \mathcal{P}\}$$

given $\tilde{S}$, the error is $E$ with the smallest norm ie

ie $||\tilde{E}||=d(S,\tilde{S})$

where $d(\cdot )$ is the operator distance modulo permutations.

• dilation takes into account edge weights, but cannot model edge additions and deletions
• additive perturbations can model edge additions and deletions, but do not take into account edge weights
• relative perturbations take into account both edge weights and additions/deletions