×
Benzi, Michele; Boito, Paola

Quadrature rule-based bounds for functions of adjacency matrices. (English) Zbl 1191.65046

Linear Algebra Appl. 433, No. 3, 637-652 (2010).
Summary: Bounds for entries of matrix functions based on Gauss-type quadrature rules are applied to adjacency matrices associated with graphs. This technique allows to develop inexpensive and accurate upper and lower bounds for certain quantities (Estrada index, subgraph centrality, communicability) that describe properties of networks.

Cited in 40 Documents

MSC:

65F50 Computational methods for sparse matrices
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
15A16 Matrix exponential and similar functions of matrices
41A55 Approximate quadratures
15A45 Miscellaneous inequalities involving matrices

Keywords:

graphs; networks; estrada index; subgraph centrality; communicability; sparse matrices; quadrature rules; Lanczos algorithm; decay bounds; matrix exponential; resolvent; numerical examples; adjacency matrices

Software:

testmatrix; CONTEST; MATLAB expm; mftoolbox; MMQ Toolbox
Cite Review PDF
Full Text: DOI

References:

[1] Bai, Z.; Golub, G. H., Bounds for the trace of the inverse and the determinant of symmetric positive definite matrices, Ann. Numer. Math., 4, 29-38 (1997) · Zbl 0883.15013
[2] Benzi, M.; Golub, G. H., Bounds for the entries of matrix functions with applications to preconditioning, BIT, 39, 417-438 (1999) · Zbl 0934.65054
[3] Benzi, M.; Razouk, N., Decay rates and \(O(n)\) algorithms for approximating functions of sparse matrices, Electron. Trans. Numer. Anal., 28, 16-39 (2007) · Zbl 1171.65034
[4] Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences (1979), Academic Press: Academic Press New York, NY · Zbl 0484.15016
[5] Crofts, J. J.; Higham, D. J., A weighted communicability measure applied to complex brain networks, J. Roy. Soc. Interface, 33, 411-414 (2009)
[6] de la Peña, J. A.; Gutman, I.; Rada, J., Estimating the Estrada index, Linear Algebra Appl., 427, 70-76 (2007) · Zbl 1184.05082
[7] Duff, I. S.; Erisman, A. M.; Reid, J. K., Direct Methods for Sparse Matrices. Direct Methods for Sparse Matrices, Monographs on Numerical Analysis (1989), Oxford Science Publications, The Clarendon Press, Oxford University Press · Zbl 0666.65024
[8] Estrada, E., Characterization of 3D molecular structure, Chem. Phys. Lett., 319, 713-718 (2000)
[9] Estrada, E.; Hatano, N., Statistical-mechanical approach to subgraph centrality in complex networks, Chem. Phys. Lett., 439, 247-251 (2007)
[10] Estrada, E.; Hatano, N., Communicability in complex networks, Phys. Rev. E, 77, 036111 (2008)
[11] Estrada, E.; Hatano, N., Communicability graph and community structures in complex networks, Appl. Math. Comput., 214, 500-511 (2009) · Zbl 1284.05253
[12] Estrada, E.; Hatano, N., Returnability in complex directed networks (digraphs), Linear Algebra Appl., 430, 1886-1896 (2009) · Zbl 1225.05108
[13] E. Estrada, D.J. Higham, Network Properties Revealed Through Matrix Functions, University of Strathclyde Mathematics Research Report 17, 2008.; E. Estrada, D.J. Higham, Network Properties Revealed Through Matrix Functions, University of Strathclyde Mathematics Research Report 17, 2008.
[14] Estrada, E.; Higham, D. J.; Hatano, N., Communicability and multipartite structures in complex networks at negative absolute temperatures, Phys. Rev. E, 78, 026102 (2008)
[15] Estrada, E.; Higham, D. J.; Hatano, N., Communicability bewteenness in complex networks, Physica A, 388, 764-774 (2009)
[16] Estrada, E.; Rodríguez-Velázquez, J. A., Subgraph centrality in complex networks, Phys. Rev. E, 71, 056103 (2005)
[17] G.H. Golub, G. Meurant, Matrices, moments and quadrature, in: Numerical Analysis, 1993, D.F. Griffiths, G.A. Watson (Eds.), Pitman Research Notes in Mathematics, vol. 303, Essex, England, 1994, pp. 105-156.; G.H. Golub, G. Meurant, Matrices, moments and quadrature, in: Numerical Analysis, 1993, D.F. Griffiths, G.A. Watson (Eds.), Pitman Research Notes in Mathematics, vol. 303, Essex, England, 1994, pp. 105-156. · Zbl 0795.65019
[18] Golub, G. H.; Meurant, G., Matrices. Matrices, Moments and Quadrature with Applications (2010), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0888.65050
[19] Higham, N., Functions of Matrices. Theory and Computation (2008), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 1167.15001
[20] Higham, N., The scaling and squaring method for the matrix exponential revisited, SIAM Rev., 51, 747-764 (2009) · Zbl 1178.65040
[21] Meurant, G., Estimates of the trace of the inverse of a symmetric matrix using the modified Chebyshev algorithm, Numer. Algorithms, 51, 309-318 (2009) · Zbl 1166.65335
[22] G. Meurant, MMQ toolbox for Matlab, <http://pagesperso-orange.fr/gerard.meurant/>; G. Meurant, MMQ toolbox for Matlab, <http://pagesperso-orange.fr/gerard.meurant/>
[23] N. Razouk, Localization Phenomena in Matrix Functions: Theory and Algorithms, Ph.D. Thesis, Emory University, Atlanta, GA, 2008.; N. Razouk, Localization Phenomena in Matrix Functions: Theory and Algorithms, Ph.D. Thesis, Emory University, Atlanta, GA, 2008.
[24] A. Taylor, D.J. Higham, CONTEST: Toolbox files and documentation, <http://www.mathstat.strath.ac.uk/research/groups/numerical_analysis/contest/toolbox>; A. Taylor, D.J. Higham, CONTEST: Toolbox files and documentation, <http://www.mathstat.strath.ac.uk/research/groups/numerical_analysis/contest/toolbox>
[25] Taylor, A.; Higham, D. J., CONTEST: a controllable test matrix toolbox for MATLAB, ACM Trans. Math. Software, 35, 26:1-26:17 (2009)
[26] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139
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.