I'm trying to find out what happens to the transitive closure of a weighted graph when I remove some of its edges at random.
More concretely, if a weighted graph has an adjacency matrix $A$ such that $A_{ij} \geq 0$ and $\|A\|_{\infty} = \max_i \sum_{j=1}^n |A_{ij}| < \lambda < 1$. Suppose I change the graph by removing some edges, obtaining a new matrix $B \leq A$ such that $\|A - B\|_{\infty} = \max_i \sum_{j=1}^n |A_{ij} - B_{ij}| < \epsilon.$
I'm trying to derive a bound on the difference between the transitive closures of $A$ and $B$, in particular, what happens to $\| (I-A)^{-1} - (I-B)^{-1}\|_{\infty} \leq \sum_{k=1}^{\infty} \|A^k - B^k\|_{\infty}.$
If one could somehow bound $\|A^k - B^k\|_{\infty}$ by $c \|(A-B)^k\|_{\infty}$ for some constant real number $c$ then one would get an immediate bound $\| (I-A)^{-1} - (I-B)^{-1}\|_{\infty} \leq \frac{ c \epsilon}{1-\epsilon}$, but I'm not sure this is the right way to go.
Let $f(X) = (I-X)^{-1} = I + X + X^2 + ...$.
The function $f$ is a differentiable matrix function with derivative $f'(X) = 1 + 2X + 3X^2 + ... = (I-X)^{-2}$. For any $X$ with $\|X\|_{\infty} < \lambda$, we have that
$$\|f'(X)\|_{\infty} = \| (I-X)^{-2}\|_{\infty} \leq \sum_{k=0}^{\infty} (k+1)\|X^k\|_{\infty} \leq \sum_{k=0}^{\infty} (k+1) \lambda^{k} = \frac{1}{(1-\lambda)^2}$$
Since $f$ is differentiable, $f$ is Lipschitz continuous (Is a differentiable matrix function Lipschitz Continuous?), and we have $$\|f(A)-f(B)\|_{\infty} \leq \frac{1}{(1-\lambda)^2} \|A-B\|_{\infty}$$