  When analyzing complex networks, an important task is the identification of
those nodes which play a leading role for the overall communicability of the
network. In the context of modifying networks (or making them robust against
targeted attacks or outages), it is also relevant to know how sensitive the
network's communicability reacts to changes in certain nodes or edges.
Recently, the concept of total network sensitivity was introduced in [O. De la
Cruz Cabrera, J. Jin, S. Noschese, L. Reichel, Communication in complex
networks, Appl. Numer. Math., 172, pp. 186-205, 2022], which allows to measure
how sensitive the total communicability of a network is to the addition or
removal of certain edges. One shortcoming of this concept is that sensitivities
are extremely costly to compute when using a straight-forward approach (orders
of magnitude more expensive than the corresponding communicability measures).
In this work, we present computational procedures for estimating network
sensitivity with a cost that is essentially linear in the number of nodes for
many real-world complex networks. Additionally, we extend the sensitivity
concept such that it also covers sensitivity of subgraph centrality and the
Estrada index, and we discuss the case of node removal. We propose a priori
bounds for these sensitivities which capture well the qualitative behavior and
give insight into the general behavior of matrix function based network indices
under perturbations. These bounds are based on decay results for Fr\'echet
derivatives of matrix functions with structured, low-rank direction terms which
might be of independent interest also for other applications than network
analysis.
