×

zbMATH — the first resource for mathematics

On the exponential generating function for non-backtracking walks. (English) Zbl 1394.05119
Summary: We derive an explicit formula for the exponential generating function associated with non-backtracking walks around a graph. We study both undirected and directed graphs. Our results allow us to derive computable expressions for non-backtracking versions of network centrality measures based on the matrix exponential. We find that eliminating backtracking walks in this context does not significantly increase the computational expense. We show how the new measures may be interpreted in terms of standard exponential centrality computation on a certain multilayer network. Insights from this block matrix interpretation also allow us to characterize centrality measures arising from general matrix functions. Rigorous analysis on the star graph illustrates the effect of non-backtracking and shows that localization can be eliminated when we restrict to non-backtracking walks. We also investigate the localization issue on synthetic networks.

MSC:
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A15 Determinants, permanents, traces, other special matrix functions
65F50 Computational methods for sparse matrices
90B10 Deterministic network models in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Afanasjew, M.; Eiermann, M.; Ernst, O. G.; Güttel, S., Implementation of a restarted Krylov subspace method for the evaluation of matrix functions, Linear Algebra Appl., 429, 10, 2293-2314, (2008) · Zbl 1153.65042
[2] Al-Mohy, A. H.; Higham, N. J., Computing the action of the matrix exponential, with an application to exponential integrators, SIAM J. Sci. Comput., 33, 488-511, (2011) · Zbl 1234.65028
[3] Alon, N.; Benjamini, I.; Lubetzky, E.; Sodin, S., Non-backtracking random walks mix faster, Commun. Contemp. Math., 09, 585-603, (2007) · Zbl 1140.60301
[4] Angel, O.; Friedman, J.; Hoory, S., The non-backtracking spectrum of the universal cover of a graph, Trans. Amer. Math. Soc., 326, 4287-4318, (2015) · Zbl 1310.05136
[5] Arrigo, F.; Benzi, M.; Fenu, C., Computation of generalized matrix functions, SIAM J. Matrix Anal. Appl., 37, 3, 836-860, (2016) · Zbl 1342.65121
[6] Arrigo, F.; Grindrod, P.; Higham, D. J.; Noferini, V., Non-backtracking walk centrality for directed networks, J. Complex Netw., 6, 1, 54-78, (2018)
[7] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512, (1999) · Zbl 1226.05223
[8] Benzi, M.; Klymko, C., Total communicability as a centrality measure, J. Complex Netw., 1, 2, 124-149, (2013)
[9] Benzi, M.; Klymko, C., On the limiting behavior of parameter-dependent network centrality measures, SIAM J. Matrix Anal. Appl., 36, 686-706, (2015) · Zbl 1314.05113
[10] Bonacich, P., Factoring and weighting approaches to status scores and clique identification, J. Math. Sociol., 2, 113-120, (1972)
[11] Bonacich, P., Power and centrality: a family of measures, Amer. J. Sociol., 92, 1170-1182, (1987)
[12] Bowen, R.; Lanford, O. E., Zeta functions of restrictions of the shift transformation, (Chern, S.-S.; Smale, S., Global Analysis, University of California, Berkely, 1968, Proceedings of Symposia in Pure Mathematics, (1970), Americal Mathematical Society, University of California Berkely), 43-49
[13] Cvetkovć, D.; Rowlinson, P.; Simić, S., Eigenspaces of graphs, (1997), Cambridge University Press Cambridge
[14] Estrada, E., The structure of complex networks, (2011), Oxford University Press Oxford
[15] Estrada, E.; Hatano, N., Communicability in complex networks, Phys. Rev. E, 77, 3, (2008)
[16] Estrada, E.; Hatano, N.; Benzi, M., The physics of communicability in complex networks, Phys. Rep., 514, 89-119, (2011)
[17] Estrada, E.; Higham, D. J., Network properties revealed through matrix functions, SIAM Rev., 52, 696-714, (2010) · Zbl 1214.05077
[18] Gohberg, I.; Lancaster, P.; Rodman, L., Matrix polynomials, (2009), SIAM Philadelphia, PA
[19] Goltsev, A. V.; Dorogovtsev, S. N.; Oliveira, J. G.; Mendes, J. F.F., Localization and spreading of diseases in complex networks, Phys. Rev. Lett., 109, (2012)
[20] Grindrod, P.; Higham, D. J.; Noferini, V., The deformed graph Laplacian and its applications to network centrality analysis, SIAM J. Matrix Anal. Appl., 39, 1, 310-341, (2018) · Zbl 1381.05043
[21] Higham, N. J., Functions of matrices: theory and computation, (2008), Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1167.15001
[22] Higham, N. J.; Deadman, E., A catalogue of software for matrix functions, (Jan. 2016), Manchester Institute for Mathematical Sciences, The University of Manchester UK, updated March 2016
[23] Horton, M. D., Ihara zeta functions on digraphs, Linear Algebra Appl., 425, 130-142, (2007) · Zbl 1119.05067
[24] Horton, M. D.; Stark, H. M.; Terras, A. A., What are zeta functions of graphs and what are they good for?, (Bertolaiko, G.; Carlson, R.; Fulling, S. A.; Kuchment, P., Quantum graphs and their applications, Contemp. Math., vol. 415, (2006)), 173-190 · Zbl 1222.11109
[25] Katz, L., A new index derived from sociometric data analysis, Psychometrika, 18, 39-43, (1953) · Zbl 0053.27606
[26] Kawamoto, T., Localized eigenvectors of the non-backtracking matrix, J. Stat. Mech. Theory Exp., 2016, (2016)
[27] Kivelä, M.; Arenas, A.; Barthelemy, M.; Gleeson, J. P.; Moreno, Y.; Porter, M. A., Multilayer networks, J. Complex Netw., 2, 203-271, (2014)
[28] Krzakala, F.; Moore, C.; Mossel, E.; Neeman, J.; Sly, A.; Zdeborová, L.; Zhang, P., Spectral redemption: clustering sparse networks, Proc. Nat. Acad. Sci., 110, 20935-20940, (2013) · Zbl 1359.62252
[29] Martin, T.; Zhang, X.; Newman, M. E.J., Localization and centrality in networks, Phys. Rev. E, 90, (2014)
[30] Maugis, P.-A. G.; Olhede, S. C.; Wolfe, P. J., Topology reveals universal features for network comparison, (2017)
[31] Morone, F.; Makse, H. A., Influence maximization in complex networks through optimal percolation, Nature, 524, 65-68, (2015)
[32] Morone, F.; Min, B.; Bo, L.; Mari, R.; Makse, H. A., Collective influence algorithm to find influencers via optimal percolation in massively large social media, Sci. Rep., 6, (2016)
[33] Nakatsukasa, Y.; Noferini, V., On the stability of computing polynomial roots via confederate linearizations, Math. Comp., 85, 2391-2425, (2016) · Zbl 1347.65096
[34] Nakatsukasa, Y.; Noferini, V.; Townsend, A., Vector spaces of linearizations of matrix polynomials: a bivariate polynomial approach, SIAM J. Matrix Anal. Appl., 38, 1, 1-29, (2016) · Zbl 1355.65058
[35] Noferini, V.; Poloni, F., Duality of matrix pencils, Wong chains and linearizations, Linear Algebra Appl., 471, 730-767, (2015) · Zbl 1308.15009
[36] Pastor-Satorras, R.; Castellano, C., Distinct types of eigenvector localization in networks, Sci. Rep., 6, (2016)
[37] Saad, Y., Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 29, 1, 209-228, (1992) · Zbl 0749.65030
[38] Saade, A.; Krzakala, F.; Zdeborová, L., Spectral clustering of graphs with the Bethe Hessian, (Ghahramani, Z.; Welling, M.; Cortes, C.; Lawrence, N. D.; Weinberger, K. Q., Advances in Neural Information Processing Systems, vol. 27, (2014)), 406-414
[39] Smilansky, U., Quantum chaos on discrete graphs, J. Phys. A, 40, F621, (2007) · Zbl 1124.81024
[40] Sodin, S., Random matrices, non-backtracking walks, and the orthogonal polynomials, J. Math. Phys., 48, (2007)
[41] Stark, H.; Terras, A., Zeta functions of finite graphs and coverings, Adv. Math., 121, 1, 124-165, (1996) · Zbl 0874.11064
[42] Tarfulea, A.; Perlis, R., An ihara formula for partially directed graphs, Linear Algebra Appl., 431, 73-85, (2009) · Zbl 1225.05119
[43] Taylor, A.; Higham, D. J., CONTEST: a controllable test matrix toolbox for MATLAB, ACM Trans. Math. Software, 35, 4, 26:1-26:17, (2009)
[44] Terras, A., Harmonic analysis on symmetric spaces — Euclidean space, the sphere, and the Poincaré upper half-plane, (2013), Springer New York · Zbl 1279.43001
[45] Watanabe, Y.; Fukumizu, K., Graph zeta function in the Bethe free energy and loopy belief propagation, (Bengio, Y.; Schuurmans, D.; Lafferty, J.; Williams, C.; Culotta, A., Advances in Neural Information Processing Systems, vol. 22, (2009)), 2017-2025
[46] Wilf, H. S., Generatingfunctionology, (2006), A. K. Peters, Ltd. Natick, MA, USA · Zbl 1092.05001
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.