×

Kemeny’s constant and global mean first passage time of random walks on octagonal cell network. (English) Zbl 1527.05161

Summary: This paper investigates the random walks of octagonal cell network. By using the Laplacian spectrum method, we obtain the mean first passage time \((\tau) \) and Kemeny’s constant \( (\Omega ) \) between nodes. On one hand, the mean first passage time \((\tau)\) is explicitly studied in terms of the eigenvalues of a Laplacian matrix. On the other hand, Kemeny’s constant \((\Omega) \) is introduced to measure node strength and to determine the scaling of the random walks. We provide an explicit expression of Kemeny’s constant and mean first passage time for octagonal cell network, by their Laplacian eigenvalues and the correlation among roots of characteristic polynomial. Based on the achieved results, comparative studies are also performed for \( \tau\) and \( \Omega\). This work also deliver an inclusive approach for exploring random walks of networks, particularly biased random walks, which likewise support to better understand and tackle some practical problems such as search and routing on networks.
{© 2023 John Wiley & Sons, Ltd.}

MSC:

05C81 Random walks on graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
60G40 Stopping times; optimal stopping problems; gambling theory
Full Text: DOI

References:

[1] RednerS. A Guide to First‐passage Processes. Cambridge University Press; 2001. doi:10.1017/CBO9780511606014 · Zbl 0980.60006
[2] IkedaN. Network formation determined by the diffusion process of random walkers. J Phys A: Math Theor. 2008;41:235005. doi:10.1088/1751‐8113/41/23/235005 · Zbl 1144.82029
[3] PolizziNF, TherienMJ, BeratanDN. Mean first‐passage times in biology. Isr J Chem. 2016;56:816. doi:10.1002/ijch.201600040
[4] MetzlerR, OshaninG, RednerS. First‐passage Phenomena and Their Applications. World Scientific; 2014. doi:10.1142/9104 · Zbl 1291.00067
[5] KellsA, KoskinV, RostaE, AnnibaleA. Correlation functions, mean first passage times, and the Kemeny constant. J Chem Phys. 2020;152:104108. doi:10.1063/1.5143504
[6] WhiteS, SmythP. Algorithms for estimating relative importance in networks. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2003:266‐275. doi:10.1145/956750.956782
[7] BassolasA, NicosiaV. First‐passage times to quantify and compare structural correlations and heterogeneity in complex systems. Commun Phys. 2021;4:76. doi:10.1038/s42005‐021‐00580‐w
[8] KemenyG, SnellJL. Finite Markov Chains. Princeton, NJ: Van Nostrand; 1960. · Zbl 0089.13704
[9] BiniD, HunterJ, LatoucheG, MeiniB, TaylorP. Why is Kemeny’s constant a constant?J Appl Prob. 2018;55:1025‐1036. · Zbl 1405.60112
[10] BerkhoutJ, HeidergottBF. Analysis of Markov influence graphs. Oper Res. 2019;67:892‐904. · Zbl 1456.62169
[11] ZamanS, KomA, KhabyahAA, AhmadA. The Kemeny’s constant and spanning trees of hexagonal ring network. Comput Mater Continua. 2022;73(3):6347‐6365. doi:10.32604/cmc.2022.031958
[12] ZhangZ, ShengY, HuZ, ChenG. Optimal and suboptimal networks for efficient navigation measured by mean‐first passage time of random walks. Chaos: Interdisciplin J Nonlin Sci. 2012;22:43129. · Zbl 1319.05120
[13] BapatRB. Graphs and Matrices. New York: Springer; 2010.
[14] ZamanS. Cacti with maximal general sum‐connectivity index. J Appl Math Comput. 2021;65:147‐160. · Zbl 1475.05112
[15] ZamanS, AliA. On connected graphs having the maximum connective eccentricity index. J Appl Math Comput. 2021;67(1):131‐142. doi:10.1007/s12190‐020‐01489‐3 · Zbl 1487.05070
[16] PanYG, LiJP, LiSC, LuoWJ. On the normalized Laplacians with some classical parameters involving graph transformations. Linear and Multilinear Algebra. 2020;68(8):1534‐1556. doi:10.1080/03081087.2018.1548556 · Zbl 1448.05132
[17] PengYJ, LiSC. On the Kirchhoff index and the number of spanning trees of linear phenylenes. MATCH Commun Math Comput Chem. 2017;77(3):765‐780. · Zbl 1466.92280
[18] HuangJ, LiSC, LiXC. The normalized Laplacian, degree‐Kirchhoff index and spanning trees of the linear polyomino chains. Appl Math Comput. 2016;289:324‐334. · Zbl 1410.05128
[19] LiSC, SunWT, WangSJ. Multiplicative degree‐Kirchhoff index and number of spanning trees of a zigzag polyhex nanotube
[( TUH{C}_6\left[2n,2\right] \]\). Int J Quantum Chem. 2019;119(17):e25969.
[20] HeCL, LiSC, LuoWJ, SunLQ. Calculating the normalized Laplacian spectrum and the number of spanning trees of linear pentagonal chains. J Comput Appl Math. 2018;344:381‐393. · Zbl 1392.05075
[21] CaoY, LiSC, XuB. Explicit determination of three invariants associated with random walks on n‐prism networks. Lin Multilinear Algebra. 2020;70(10):1‐17. doi:10.1080/03081087.2020.1777249
[22] ZamanS. Spectral analysis of three invariants associated to random walks on rounded networks with 2n‐pentagons. Int J Comp Math. 2022;99(3):465‐485. doi:10.1080/00207160.2021.1919303 · Zbl 1499.05408
[23] LiQ, ZamanS, SunW, AlamJ. Study on the normalized Laplacian of a penta‐graphene with applications. Int J Quantum Chem. 2020;120(9):e26154.
[24] ChandraAK, RaghavanP, RuzzoWL, SmolenskyR, TiwariP. The electrical resistance of a graph captures its commute and cover times. Comput Complex. 1996;6:312‐340. · Zbl 0905.60049
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.