Ergodicity coefficients for higher-order stochastic processes. (English) Zbl 1483.60105
Summary: The use of higher-order stochastic processes such as nonlinear Markov chains or vertex-reinforced random walks is significantly growing in recent years as they are much better at modeling high dimensional data and nonlinear dynamics in numerous application settings. In many cases of practical interest, these processes are identified with a stochastic tensor, and their stationary distribution is a tensor \(Z\)-eigenvector. However, fundamental questions such as the convergence of the process towards a limiting distribution and the uniqueness of such a limit are still not well understood and are the subject of rich recent literature. Ergodicity coefficients for stochastic matrices provide a valuable and widely used tool to analyze the long-term behavior of standard, first-order, Markov processes. In this work, we extend an important class of ergodicity coefficients to the setting of stochastic tensors. We show that the proposed higher-order ergodicity coefficients provide new explicit formulas that (a) guarantee the uniqueness of Perron \(Z\)-eigenvectors of stochastic tensors, (b) provide bounds on the sensitivity of such eigenvectors with respect to changes in the tensor, and (c) ensure the convergence of different types of higher-order stochastic processes governed by cubical stochastic tensors. Moreover, we illustrate the advantages of the proposed ergodicity coefficients on several example application settings, including the analysis of PageRank vectors for triangle-based random walks and the convergence of lazy higher-order random walks.
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 60G50 | Sums of independent random variables; random walks |
| 65C30 | Numerical solutions to stochastic differential and integral equations |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65C40 | Numerical analysis or methods applied to Markov chains |
Keywords:
nonnegative tensors; stochastic tensors; higher-order Markov chain; ergodicity coefficient; \(Z\)-eigenvector; vertex-reinforced random walk; spacey random walk; multilinear PageRankReferences:
| [1] | A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky, Tensor decompositions for learning latent variable models, J. Mach. Learn. Res., 15 (2014), pp. 2773-2832. · Zbl 1319.62109 |
| [2] | R. Andersen, F. Chung, and K. Lang, Local graph partitioning using PageRank vectors, in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), IEEE, 2006, pp. 475-486, https://doi.org/10.1109/FOCS.2006.44. |
| [3] | F. Arrigo, D. J. Higham, and V. Noferini, Non-backtracking PageRank, J. Sci. Comput., 80 (2019), pp. 1419-1437. · Zbl 1425.65046 |
| [4] | F. Arrigo, D. J. Higham, and F. Tudisco, A framework for second-order eigenvector centralities and clustering coefficients, Proc. A, 476 (2020), 20190724. · Zbl 1472.65043 |
| [5] | F. Arrigo and F. Tudisco, Multi-dimensional, multilayer, nonlinear and dynamic HITS, in Proceedings of the 2019 SIAM International Conference on Data Mining, SIAM, 2019, pp. 369-377. |
| [6] | L. Backstrom and J. Leskovec, Supervised random walks: Predicting and recommending links in social networks, in Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, 2011, pp. 635-644. |
| [7] | M. Benaïm, Vertex-reinforced random walks and a conjecture of Pemantle, Ann. Probab., 25 (1997), pp. 361-392. · Zbl 0873.60044 |
| [8] | A. Benson, D. F. Gleich, and L.-H. Lim, The spacey random walk: A stochastic process for higher-order data, SIAM Rev., 59 (2017), pp. 321-345. · Zbl 1365.15033 |
| [9] | A. R. Benson, Three hypergraph eigenvector centralities, SIAM J. Math. Data Sci., 1 (2019), pp. 293-312. · Zbl 1499.05432 |
| [10] | A. R. Benson, D. F. Gleich, and J. Leskovec, Tensor spectral clustering for partitioning higher-order network structures, Proceedings of the 2015 SIAM International Conference on Data Mining, 2015, pp. 118-126. |
| [11] | A. Berchtold and A. Raftery, The mixture transition distribution model for high-order Markov chains and non-Gaussian time series, Statist. Sci., 17 (2002), pp. 328-356. · Zbl 1013.62088 |
| [12] | G. Birkhoff, Extensions of Jentzsch’s theorem, Trans. Amer. Math. Soc., 85 (1957), pp. 219-227. · Zbl 0079.13502 |
| [13] | F. Bouguet and B. Cloez, Fluctuations of the empirical measure of freezing Markov chains, Electron. J. Probab., 23 (2018), 2. · Zbl 1390.60264 |
| [14] | H. Bozorgmanesh and M. Hajarian, Convergence of a transition probability tensor of a higher-order Markov chain to the stationary probability vector, Numer. Linear Algebra Appl., 23 (2016), pp. 972-988. · Zbl 1413.15047 |
| [15] | K. Chang and T. Zhang, On the uniqueness and non-uniqueness of the positive Z-eigenvector for transition probability tensors, J. Math. Anal. Appl., 408 (2013), pp. 525-540. · Zbl 1306.15021 |
| [16] | K.-C. Chang, K. Pearson, and T. Zhang, Perron-Frobenius theorem for nonnegative tensors, Commun. Math. Sci., 6 (2008), pp. 507-520. · Zbl 1147.15006 |
| [17] | F. Chierichetti, R. Kumar, P. Raghavan, and T. Sarlos, Are web users really Markovian?, in Proceedings of the 21st International Conference on World Wide Web, ACM, 2012, pp. 609-618. |
| [18] | S. Cipolla, M. Redivo-Zaglia, and F. Tudisco, Extrapolation methods for fixed-point multilinear PageRank computations, Numer. Linear Algebra Appl., 27 (2020), e2280. · Zbl 1488.65106 |
| [19] | L.-B. Cui and Y. Song, On the uniqueness of the positive Z-eigenvector for nonnegative tensors, J. Comput. Appl. Math., 352 (2019), pp. 72-78. · Zbl 1408.15009 |
| [20] | L. De Lathauwer, B. De Moor, and J. Vandewalle, On the best rank-1 and rank-\((R_1,R_2,\ldots,R_N)\) approximation of higher-order tensors, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1324-1342. · Zbl 0958.15026 |
| [21] | R. L. Dobrushin, Central limit theorem for nonstationary Markov chains. I, II, Theory Probab. Appl., 1 (1956), pp. 65-80, 329-383. |
| [22] | S. P. Eveson and R. D. Nussbaum, An elementary proof of the Birkhoff-Hopf theorem, Math. Proc. Cambridge Philos. Soc., 117 (1995), pp. 31-55. · Zbl 0834.47028 |
| [23] | S. Friedland, S. Gaubert, and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl., 438 (2013), pp. 738-749. · Zbl 1261.15039 |
| [24] | A. Gautier and F. Tudisco, The contractivity of cone-preserving multilinear mappings, Nonlinearity, 32 (2019), pp. 4713-4728. · Zbl 07123903 |
| [25] | A. Gautier, F. Tudisco, and M. Hein, The Perron-Frobenius theorem for multihomogeneous mappings, SIAM J. Matrix Anal. Appl., 40 (2019), pp. 1179-1205. · Zbl 07122458 |
| [26] | A. Gautier, F. Tudisco, and M. Hein, A unifying Perron-Frobenius theorem for nonnegative tensors via multihomogeneous maps, SIAM J. Matrix Anal. Appl., 40 (2019), pp. 1206-1231. · Zbl 07122459 |
| [27] | D. F. Gleich, L.-H. Lim, and Y. Yu, Multilinear PageRank, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 1507-1541. · Zbl 1330.15029 |
| [28] | C. J. Hillar and L.-H. Lim, Most tensor problems are NP-hard, J. ACM, 60 (2013), 45. · Zbl 1281.68126 |
| [29] | S. Hu and L. Qi, Convergence of a second order Markov chain, Appl. Math. Comput., 241 (2014), pp. 183-192. · Zbl 1334.60143 |
| [30] | S. Hu, L. Qi, and G. Zhang, Computing the geometric measure of entanglement of multipartite pure states by means of non-negative tensors, Phys. Rev. A, 93 (2016), 012304. |
| [31] | I. C. F. Ipsen and T. M. Selee, Ergodicity coefficients defined by vector norms, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 153-200. · Zbl 1223.15043 |
| [32] | K. Knopp, Infinite Sequences and Series, Dover Publications, Inc., New York, 1956. · Zbl 0070.05807 |
| [33] | T. G. Kolda and J. R. Mayo, Shifted power method for computing tensor eigenpairs, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1095-1124. · Zbl 1247.65048 |
| [34] | V. N. Kolokoltsov, Nonlinear Markov Processes and Kinetic Equations, Cambridge University Press, Cambridge, UK, 2010. · Zbl 1222.60003 |
| [35] | F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang, Spectral redemption in clustering sparse networks, Proc. Natl. Acad. Sci. USA, 110 (2013), pp. 20935-20940. · Zbl 1359.62252 |
| [36] | C.-K. Li and S. Zhang, Stationary probability vectors of higher-order Markov chains, Linear Algebra Appl., 473 (2015), pp. 114-125. · Zbl 1391.60176 |
| [37] | W. Li, L.-B. Cui, and M. K. Ng, The perturbation bound for the Perron vector of a transition probability tensor, Numer. Linear Algebra Appl., 20 (2013), pp. 985-1000. · Zbl 1313.15036 |
| [38] | W. Li, D. Liu, M. K. Ng, and S.-W. Vong, The uniqueness of multilinear PageRank vectors, Numer. Linear Algebra Appl., 24 (2017), e2107. · Zbl 1488.65102 |
| [39] | W. Li and M. K. Ng, On the limiting probability distribution of a transition probability tensor, Linear Multilinear Algebra, 62 (2014), pp. 362-385. · Zbl 1301.60049 |
| [40] | Y. Liu, H. Tong, L. Xie, and Y. Tang, Supervised link prediction using random walks, in Communications in Computer and Information Science, Commun. Comput. Inf. Sci. 568, Springer-Verlag, Cham, 2015, pp. 107-118, https://doi.org/10.1007/978-981-10-0080-5_10. |
| [41] | N. Masuda, M. A. Porter, and R. Lambiotte, Random walks and diffusion on networks, Phys. Rep., 716/717 (2017), pp. 1-58. · Zbl 1377.05180 |
| [42] | Q. Mei, J. Guo, and D. Radev, Divrank: The interplay of prestige and diversity in information networks, in Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2010, pp. 1009-1018. |
| [43] | B. Meini and F. Poloni, Perron-based algorithms for the multilinear PageRank, Numer. Linear Algebra Appl., 25 (2018), e2177. · Zbl 1524.65199 |
| [44] | H. Nassar, A. R. Benson, and D. F. Gleich, Pairwise Link Prediction, preprint, arXiv:1907.04503, 2019. |
| [45] | M. K. Ng, X. Li, and Y. Ye, Multirank: Co-ranking for objects and relations in multi-relational data, in Proceedings of the 17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2011, pp. 1217-1225. |
| [46] | J. D. Noh and H. Rieger, Random walks on complex networks, Phys. Rev. Lett., 92 (2004), 118701, https://doi.org/10.1103/PhysRevLett.92.118701. |
| [47] | R. Pemantle, Vertex-reinforced random walk, Probab. Theory Related Fields, 92 (1992), pp. 117-136. · Zbl 0741.60029 |
| [48] | L. Qi and Z. Luo, Tensor Analysis: Spectral Theory and Special Tensors, SIAM, Philadelphia, PA, 2017. · Zbl 1370.15001 |
| [49] | L. Qi, Y. Wang, and E. X. Wu, D-eigenvalues of diffusion kurtosis tensors, J. Comput. Appl. Math., 221 (2008), pp. 150-157. · Zbl 1176.65046 |
| [50] | A. E. Raftery, A model for high-order Markov chains, J. R. Stat. Soc. Ser. B. Stat. Methodol., 47 (1985), pp. 528-539. · Zbl 0593.62091 |
| [51] | A. E. Raftery and S. Tavaré, Estimation and modelling repeated patterns in high order Markov chains with the mixture transition distribution model, J. R. Stat. Soc. Ser. C. Appl. Stat., 43 (1994), pp. 179-199. · Zbl 0825.62667 |
| [52] | S. Ragnarsson and C. F. Van Loan, Block tensor unfoldings, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 149-169. · Zbl 1246.15028 |
| [53] | R. A. Rossi and N. K. Ahmed, The network data repository with interactive graph analytics and visualization, in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI’15, AAAI Press, 2015, p. 4292-4293, http://networkrepository.com (accessed 2020-04-26). |
| [54] | M. Rosvall, A. V. Esquivel, A. Lancichinetti, J. D. West, and R. Lambiotte, Memory in network flows and its effects on spreading dynamics and community detection, Nature Commun., 5 (2014), 4630. |
| [55] | M. Saburov, Ergodicity of \(p\)-majorizing nonlinear Markov operators on the finite dimensional space, Linear Algebra Appl., 578 (2019), pp. 53-74. · Zbl 1476.47038 |
| [56] | E. Seneta, Non-negative matrices and Markov chains, Springer-Verlag, Cham, 1981. · Zbl 0471.60001 |
| [57] | E. Seneta, Perturbation of the stationary distribution measured by ergodicity coefficient, Adv. Appl. Probab., 20 (1988), pp. 228-230. · Zbl 0645.60070 |
| [58] | D. A. Spielman and S.-H. Teng, A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning, SIAM J. Comput., 42 (2013), pp. 1-26. · Zbl 1286.68244 |
| [59] | A. L. Traud, P. J. Mucha, and M. A. Porter, Social structure of Facebook networks, Phys. A, 391 (2012), pp. 4165-4180. |
| [60] | F. Tudisco, A note on certain ergodicity coefficients, Spec. Matrices, 3 (2015), pp. 175-185. · Zbl 1321.65057 |
| [61] | O. E. Williams, F. Lillo, and V. Latora, Effects of memory on spreading processes in non-Markovian temporal networks, New J. Phys., 21 (2019), 043028. |
| [62] | S.-J. Wu and M. T. Chu, Markov chains with memory, tensor formulation, and the dynamics of power iteration, Appl. Math. Comput., 303 (2017), pp. 226-239. · Zbl 1411.60129 |
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.
