تقرير
On Kemeny's constant and stochastic complement
| العنوان: | On Kemeny's constant and stochastic complement |
|---|---|
| المؤلفون: | Bini, Dario Andrea, Durastante, Fabio, Kim, Sooyeong, Meini, Beatrice |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Numerical Analysis, 60J22, 65C40, 65F15 |
| الوصف: | Given a stochastic matrix $P$ partitioned in four blocks $P_{ij}$, $i,j=1,2$, Kemeny's constant $\kappa(P)$ is expressed in terms of Kemeny's constants of the stochastic complements $P_1=P_{11}+P_{12}(I-P_{22})^{-1}P_{21}$, and $P_2=P_{22}+P_{21}(I-P_{11})^{-1}P_{12}$. Specific cases concerning periodic Markov chains and Kronecker products of stochastic matrices are investigated. Bounds to Kemeny's constant of perturbed matrices are given. Relying on these theoretical results, a divide-and-conquer algorithm for the efficient computation of Kemeny's constant of graphs is designed. Numerical experiments performed on real-world problems show the high efficiency and reliability of this algorithm. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2312.13201 |
| رقم الأكسشن: | edsarx.2312.13201 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |