Sensitivity of Matrix Function Based Network Communicability Measures: Computational Methods and A Priori Bounds
From MaRDI portal
Publication:6094748
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Matrix exponential and similar functions of matrices (15A16) Numerical computation of matrix exponential and similar matrix functions (65F60) Communication theory (94A05)
Abstract: 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.
Recommendations
Cites work
- A block Krylov method to compute the action of the Fréchet derivative of a matrix function on a vector with applications to condition number estimation
- A Krylov subspace method for the approximation of bivariate matrix functions
- A new status index derived from sociometric analysis
- Analysis of directed networks via the matrix exponential
- Bounds for the decay of the entries in inverses and Cauchy-Stieltjes functions of certain sparse, normal matrices.
- Centrality measures for node-weighted networks via line graphs and the matrix exponential
- Communicability graph and community structures in complex networks
- Communication in complex networks
- Complex networks. Structure, robustness and function.
- Complex networks: structure and dynamics
- Computing low‐rank approximations of the Fréchet derivative of a matrix function using Krylov subspace methods
- Convergence of a subgradient method for computing the bound norm of matrices
- Decay bounds and \(O(n)\) algorithms for approximating functions of sparse matrices
- Decay bounds for Bernstein functions of Hermitian matrices with applications to the fractional graph Laplacian
- Decay bounds for functions of Hermitian matrices with banded or Kronecker structure
- Decay properties for functions of matrices over \(C^\ast\)-algebras
- Decay Rates for Inverses of Band Matrices
- Edge modification criteria for enhancing the communicability of digraphs
- Error Estimates and Evaluation of Matrix Functions via the Faber Transform
- Estimating the largest elements of a matrix
- Functions of Matrices
- Functions of rational Krylov space matrices and their decay properties
- scientific article; zbMATH DE number 5977361 (Why is no real title available?)
- Localization in matrix computations: theory and applications
- Low-rank updates of matrix functions
- Low-Rank Updates of Matrix Functions II: Rational Krylov Methods
- Mittag-Leffler functions and their applications in network science
- Navigability of interconnected networks under random failures
- Network properties revealed through matrix functions
- Networks
- NIST handbook of mathematical functions
- Non-Toeplitz decay bounds for inverses of Hermitian positive definite tridiagonal matrices
- On Krylov Subspace Approximations to the Matrix Exponential Operator
- On the computation of incomplete gamma functions in the complex domain
- On the limiting behavior of parameter-dependent network centrality measures
- On the stability of network indices defined by means of matrix functions
- Ranking hubs and authorities using matrix functions
- Refined decay bounds on the entries of spectral projectors associated with sparse Hermitian matrices
- The power method for l\(^p\) norms
- The principle of minimized iterations in the solution of the matrix eigenvalue problem
- Updating and downdating techniques for optimizing network communicability
Cited in
(13)- Variability analysis of complex networks measures based on stochastic distances
- Communication in complex networks
- Perron communicability and sensitivity of multilayer networks
- Edge modification criteria for enhancing the communicability of digraphs
- Updating and downdating techniques for optimizing network communicability
- On the stability of network indices defined by means of matrix functions
- Communication in multiplex transportation networks
- Updating Katz centrality by counting walks
- Network efficiency under nonconservative diffusion
- Edge importance in complex networks
- A novel Krylov subspace method for approximating Fréchet derivatives of large-scale matrix functions
- Edge-based Katz centralities for spatio-temporal multiplex networks
- Network connectivity analysis via shortest paths
This page was built for publication: Sensitivity of Matrix Function Based Network Communicability Measures: Computational Methods and A Priori Bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094748)
