×

Communication in complex networks. (English) Zbl 1485.90019

Summary: One of the properties of interest in the analysis of networks is global communicability, i.e., how easy or difficult it is, generally, to reach nodes from other nodes by following edges. Different global communicability measures provide quantitative assessments of this property, emphasizing different aspects of the problem.
This paper investigates the sensitivity of global measures of communicability to local changes. In particular, for directed, weighted networks, we study how different global measures of communicability change when the weight of a single edge is changed; or, in the unweighted case, when an edge is added or removed. The measures we study include the total network communicability, based on the matrix exponential of the adjacency matrix, and the Perron network communicability, defined in terms of the Perron root of the adjacency matrix and the associated left and right eigenvectors.
Finding what local changes lead to the largest changes in global communicability has many potential applications, including assessing the resilience of a system to failure or attack, guidance for incremental system improvements, and studying the sensitivity of global communicability measures to errors in the network connection data.

MSC:

90B18 Communication networks in operations research

Software:

mftoolbox
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Air500 Data
[2] Arrigo, F.; Benzi, M., Edge modification criteria for enhancing the communicability of digraphs, SIAM J. Matrix Anal. Appl., 37, 443-468 (2016) · Zbl 1336.05120
[3] Baglama, J.; Calvetti, D.; Reichel, L., IRBL: an implicitly restarted block Lanczos method for large-scale Hermitian eigenproblems, SIAM J. Sci. Comput., 24, 1650-1677 (2003) · Zbl 1044.65027
[4] Barrat, A.; Barthelemy, M.; Vespignani, A., Weighted evolving networks: coupling topology and weight dynamics, Phys. Rev. Lett., 92, Article 228701 pp. (2004)
[5] Beckermann, B.; Reichel, L., Error estimation and evaluation of matrix functions via the Faber transform, SIAM J. Numer. Anal., 47, 3849-3883 (2009) · Zbl 1204.65041
[6] Benzi, M.; Klymko, C., Total communicability as a centrality measure, J. Complex Netw., 1, 124-149 (2013)
[7] Biggs, N., Algebraic Graph Theory (1993), Cambridge University Press: Cambridge University Press Cambridge
[8] De la Cruz Cabrera, O.; Matar, M.; Reichel, L., Analysis of directed networks via the matrix exponential, J. Comput. Appl. Math., 355, 182-192 (2019) · Zbl 1417.90041
[9] De la Cruz Cabrera, O.; Matar, M.; Reichel, L., Centrality measures for node-weighted networks via line graphs and the matrix exponential, Numer. Algorithms, 88, 583-614 (2021) · Zbl 1487.05249
[10] Estrada, E., The Structure of Complex Networks: Theory and Applications (2011), Oxford University Press: Oxford University Press Oxford
[11] Estrada, E., Informational cost and networks navigability, Appl. Math. Comput., 397, Article 125914 pp. (2021) · Zbl 1508.05150
[12] Estrada, E.; Hatano, N., Communicability in complex networks, Phys. Rev. E, 77, Article 036111 pp. (2008)
[13] Estrada, E.; Hatano, N.; Benzi, M., The physics of communicability in complex networks, Phys. Rep., 514, 89-119 (2012)
[14] Estrada, E.; Higham, D. J.; Hatano, N., Communicability betweenness in complex networks, Physica A, 388, 764-774 (2009)
[15] Estrada, E.; Rodriguez-Velazquez, J. A., Subgraph centrality in complex networks, Phys. Rev. E, 71, Article 056103 pp. (2005)
[16] Higham, N. J., Functions of Matrices: Theory and Computation (2008), SIAM: SIAM Philadelphia · Zbl 1167.15001
[17] Horn, R. A.; Johnson, C. R., Matrix Analysis (1985), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0576.15001
[18] Kandolf, P.; Koskela, A.; Relton, S. D.; Schweitzer, M., Computing low-rank approximations of the Frèchet derivative of a matrix function using Krylov subspace methods, Numer. Linear Algebra Appl., Article e2401 pp. (2021) · Zbl 07478627
[19] Milanese, A.; Sun, J.; Nishikawa, T., Approximating spectral impact of structural perturbations in large networks, Phys. Rev. E, 81, Article 046112 pp. (2010)
[20] Newman, M. E.J., Analysis of weighted networks, Phys. Rev. E, 70, Article 056131 pp. (2004)
[21] Newman, M. E.J., Networks: An Introduction (2010), Oxford University Press: Oxford University Press Oxford · Zbl 1195.94003
[22] Ortega, J.; Rheinboldt, W., Iterative Solution of Nonlinear Equations in Several Variables (2000), SIAM: SIAM Philadelphia · Zbl 0949.65053
[23] Parlett, B. N.; Taylor, D. R.; Liu, Z. A., A look-ahead Lanczos algorithm for unsymmetric matrices, Math. Comput., 44, 105-124 (1985) · Zbl 0564.65022
[24] Ruhe, A., The two-sided Arnoldi algorithm for nonsymmetric eigenvalue problems, (Kågström, B.; Ruhe, A., Matrix Pencils (1983), Springer: Springer Berlin), 104-120 · Zbl 0502.65022
[25] Saad, Y., Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 29, 209-228 (1992) · Zbl 0749.65030
[26] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM: SIAM Philadelphia · Zbl 1002.65042
[27] USAir97 data and usroads-48 Data
[28] Wilkinson, J. H., Sensitivity of eigenvalues II, Util. Math., 30, 243-286 (1986) · Zbl 0611.65019
[29] Zwaan, I. N.; Hochstenbach, M. E., Krylov-Schur-type restarts for the two-sided Arnoldi method, SIAM J. Matrix Anal. Appl., 38, 297-321 (2017) · Zbl 1365.65100
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.