We develop efficient and effective strategies for the update of Katz centralities after node and edge removal in simple graphs. We provide explicit formulas for the ``loss of walks" a network suffers when nodes/edges are removed, and use these to inform our algorithms. The theory builds on the newly introduced concept of $\cF$-avoiding first-passage walks. Further, bounds on the change of total network communicability are also derived. Extensive numerical experiments on synthetic and real-world networks complement our theoretical results.