×

zbMATH — the first resource for mathematics

The deformed graph Laplacian and its applications to network centrality analysis. (English) Zbl 1381.05043

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
15A18 Eigenvalues, singular values, and eigenvectors
15A54 Matrices over function rings in one or more variables
15B48 Positive matrices and their generalizations; cones of matrices
15B99 Special matrices
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
Software:
CONTEST; testmatrix
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Alon, I. Benjamini, E. Lubetzky, and S. Sodin, Non-backtracking random walks mix faster, Commun. Contemp. Math., 9 (2007), pp. 585–603. · Zbl 1140.60301
[2] A. Arratia and C. Marijuán, On graph combinatorics to improve eigenvector-based measures of centrality in directed networks, Linear Algebra Appl., 504 (2016), pp. 325–353. · Zbl 1338.15068
[3] A. L. Barabási and R. Albert, Emergence of scaling in random networks, Science, 286 (1999), pp. 509–512. · Zbl 1226.05223
[4] M. Benzi and C. Klymko, On the limiting behavior of parameter-dependent network centrality measures, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 686–706, . · Zbl 1314.05113
[5] D. Bindel and A. Hood, Localization theorems for nonlinear eigenvalue problems, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1728–1749, . · Zbl 1297.15021
[6] D. A. Bini, V. Noferini, and M. Sharify, Locating the eigenvalues of matrix polynomials, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1708–1727, . · Zbl 1291.15048
[7] P. Boldi and S. Vigna, Axioms for centrality, Internet Math., 10 (2014), pp. 222–262.
[8] B. Bollobas, Modern Graph Theory, Springer-Verlag, New York, 1998. · Zbl 0902.05016
[9] P. Bonacich, Factoring and weighting approaches to status scores and clique identification, J. Math. Sociol., 2 (1972), pp. 113–120.
[10] P. Bonacich, Power and centrality: A family of measures, American Journal of Sociology, 92 (1987), pp. 1170–1182.
[11] S. P. Borgatti, Centrality and network flow, Social Networks, 27 (2005), pp. 55–71.
[12] S. P. Borgatti and M. G. Everett, A graph theoretic perspective on centrality, Social Networks, 28 (2006), pp. 466–484.
[13] R. Bowen and O. E. Lanford, Zeta functions of restrictions of the shift transformation, in Global Analysis: Proceedings of the Symposium in Pure Mathematics of the American Mathematical Society, University of California, Berkeley, 1968, S.-S. Chern and S. Smale, eds., American Mathematical Society, Providence, RI, 1970, pp. 43–49.
[14] D. Cvetkovć, P. Rowlinson, and S. Simić, Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.
[15] D. Cvetković, P. Rowlinson, and S. K. Simić, Signless Laplacians of finite graphs, Linear Algebra Appl., 423 (2007), pp. 155–171. · Zbl 1113.05061
[16] H. Delange, The converse of Abel’s theorem on power series, Ann. of Math., 50 (1949), pp. 94–109. · Zbl 0032.06002
[17] E. Estrada, Protein bipartivity and essentiality in the yeast protein-protein interaction network, Journal of Proteome Research, 5 (2006), pp. 2177–2184.
[18] E. Estrada, Virtual identification of essential proteins within the protein interaction network of yeast, Proteomics, 6 (2006), pp. 35–40.
[19] E. Estrada, The Structure of Complex Networks, Oxford University Press, Oxford, 2011.
[20] E. Estrada and D. J. Higham, Network properties revealed through matrix functions, SIAM Rev., 52 (2010), pp. 696–714, . · Zbl 1214.05077
[21] E. Estrada and G. Silver, Accounting for the role of long walks on networks via a new matrix function, J. Math. Anal. Appl., 449 (2017), pp. 1581–1600. · Zbl 1355.05233
[22] L. C. Freeman, Centrality in social networks: Conceptual clarification, Social Networks, 1 (1978), pp. 215–239.
[23] G. Frobenius, Theorie der linearen Formen mit ganzen Coefficienten, J. Reine Angew. Math. (Crelle), 86 (1878), pp. 146–208. · JFM 10.0079.02
[24] I. Gohberg, P. Lancaster, and L. Rodman, Matrix Polynomials, Classics Appl. Math. 58, SIAM, Philadelphia, 2009.
[25] P. Grindrod and T. E. Lee, Comparison of social structures within cities of very different sizes, R. Soc. Open Sci., 3 (2016), 150526.
[26] M. D. Horton, H. M. Stark, and A. A. Terras, What are zeta functions of graphs and what are they good for?, in Quantum Graphs and Their Applications, Contemp. Math. 415, G. Berkolaiko, R. Carlson, S. A. Fulling, and P. Kuchment, eds., 2006, pp. 173–190. · Zbl 1222.11109
[27] T. Kato, Perturbation Theory for Linear Operators, Springer-Verlag, New York, 1966. · Zbl 0148.12601
[28] L. Katz, A new index derived from sociometric data analysis, Psychometrika, 18 (1953), pp. 39–43. · Zbl 0053.27606
[29] M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse, Identification of influential spreaders in complex networks, Nature Physics, 6 (2010), 888.
[30] M. Kotlyar, C. Pastrello, N. Sheahan, and I. Jurisica, Integrated interactions database: Tissue-specific view of the human and model organism interactomes, Nucleic Acids Research, 44 (2016), pp. 536–541.
[31] A. N. Langville and C. D. Meyer, Deeper inside PageRank, Internet Math., 1 (2004), pp. 335–380. · Zbl 1098.68010
[32] D. S. Mackey, N. Mackey, C. Mehl, and V. Merhmann, Vector spaces of linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 971–1004, . · Zbl 1132.65027
[33] T. Martin, X. Zhang, and M. E. J. Newman, Localization and centrality in networks, Phys. Rev. E, 90 (2014), 052808.
[34] V. Mehrmann, V. Noferini, F. Tisseur, and H. Xu, On the sign characteristics of Hermitian matrix polynomials, Linear Algebra Appl., 511 (2016), pp. 328–364. · Zbl 1352.15027
[35] R. Merris, Laplacian matrices of graphs: A survey, Linear Algebra Appl., 197–198 (1994), pp. 143–176. · Zbl 0802.05053
[36] F. Morbidi, The deformed consensus protocol, Automatica, 49 (2013), pp. 3049–3055. · Zbl 1358.93013
[37] Y. Nakatsukasa, V. Noferini, and A. Townsend, Vector spaces of linearizations of matrix polynomials: A bivariate polynomial approach, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1–29, . · Zbl 1355.65058
[38] V. Noferini and F. Poloni, Duality of matrix pencils, Wong chains and linearizations, Linear Algebra Appl., 471 (2015), pp. 730–767. · Zbl 1308.15009
[39] V. Noferini, M. Sharify, and F. Tisseur, Tropical roots as approximations to eigenvalues of matrix polynomials, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 138–157, . · Zbl 1315.65038
[40] R. J. Plemmons, M-matrix characterizations. \textupI—nonsingular M-matrices, Linear Algebra Appl., 18 (1977), pp. 175–188. · Zbl 0359.15005
[41] F. Radicchi and C. Castellano, Leveraging percolation theory to single out influential spreaders in networks, Phys. Rev. E, 93 (2016), 062314.
[42] D. Schoch, T. W. Valente, and U. Brandes, Correlations among centrality indices and a class of uniquely ranked graphs, Social Networks, 50 (2017), pp. 46–54.
[43] H. Stark and A. Terras, Zeta functions of finite graphs and coverings, Adv. Math., 121 (1996), pp. 124–165. · Zbl 0874.11064
[44] A. Tarfulea and R. Perlis, An Ihara formula for partially directed graphs, Linear Algebra Appl., 431 (2009), pp. 73–85. · Zbl 1225.05119
[45] A. Taylor and D. J. Higham, CONTEST: A controllable test matrix toolbox for MATLAB, ACM Trans. Math. Softw., 35 (2009), 26.
[46] P. Uetz, L. Giot, G. Cagney, T. A. Mansfield, R. S. Judson, J. R. Knight, E. Lockshon, V. Narayan, M. Srinivasan, P. Pochart, A. Qureshi-Emili, Y. Li, B. Godwin, D. Conover, T. Kalbfleish, G. Vijayadamodar, M. Yang, M. Johnston, S. Fields, and J. M. Rothberg, A comprehensive analysis of protein-protein interactions in saccharomyces cerevisiae, Nature, 403 (2000), pp. 623–627.
[47] S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications, Cambridge University Press, Cambridge, 1994. · Zbl 0926.91066
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.