{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:40:25Z","timestamp":1760236825492,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,12,24]],"date-time":"2021-12-24T00:00:00Z","timestamp":1640304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61632002,61872166,61662066"],"award-info":[{"award-number":["61632002,61872166,61662066"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>For random walks on a complex network, the configuration of a network that provides optimal or suboptimal navigation efficiency is meaningful research. It has been proven that a complete graph has the exact minimal mean hitting time, which grows linearly with the network order. In this paper, we present a class of sparse networks G(t) in view of a graphic operation, which have a similar dynamic process with the complete graph; however, their topological properties are different. We capture that G(t) has a remarkable scale-free nature that exists in most real networks and give the recursive relations of several related matrices for the studied network. According to the connections between random walks and electrical networks, three types of graph invariants are calculated, including regular Kirchhoff index, M-Kirchhoff index and A-Kirchhoff index. We derive the closed-form solutions for the mean hitting time of G(t), and our results show that the dominant scaling of which exhibits the same behavior as that of a complete graph. The result could be considered when designing networks with high navigation efficiency.<\/jats:p>","DOI":"10.3390\/e24010034","type":"journal-article","created":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T01:00:54Z","timestamp":1640566854000},"page":"34","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Mean Hitting Time for Random Walks on a Class of Sparse Networks"],"prefix":"10.3390","volume":"24","author":[{"given":"Jing","family":"Su","sequence":"first","affiliation":[{"name":"School of Electronics Engineering and Computer Science, Peking University, NO. 5 Yiheyuan Road, Haidian District, Beijing 100871, China"},{"name":"Key Laboratory of High Confidence Software Technologies, Peking University, Beijing 100871, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4232-1147","authenticated-orcid":false,"given":"Xiaomin","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Electronics Engineering and Computer Science, Peking University, NO. 5 Yiheyuan Road, Haidian District, Beijing 100871, China"},{"name":"Key Laboratory of High Confidence Software Technologies, Peking University, Beijing 100871, China"}]},{"given":"Bing","family":"Yao","sequence":"additional","affiliation":[{"name":"College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Newman, M.E.J. (2010). Networks: An Introduction, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780199206650.003.0001"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"648","DOI":"10.3934\/mine.2019.3.648","article-title":"Equilibria and control of metabolic networks with enhancers and inhibitors","volume":"1","author":"An","year":"2019","journal-title":"Math. Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"6734248","DOI":"10.1155\/2021\/6734248","article-title":"Structure, Dynamics, and Applications of Complex Networks in Software Engineering","volume":"2021","author":"Pan","year":"2021","journal-title":"Math. Probl. Eng."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"aac6284","DOI":"10.1126\/science.aac6284","article-title":"The predator-prey power law: Biomass scaling across terrestrial and aquatic biomes","volume":"349","author":"Hatton","year":"2015","journal-title":"Science"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1988","DOI":"10.1016\/j.laa.2010.07.016","article-title":"Fastest expected time to mixing for a Markov chain on a directed graph","volume":"433","author":"Kirkland","year":"2010","journal-title":"Linear Algebra Its Appl."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1080\/00029890.2002.11919905","article-title":"Kemeny\u2019s constant and the random surfer","volume":"109","author":"Levene","year":"2002","journal-title":"Am. Math. Mon."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"043129","DOI":"10.1063\/1.4768665","article-title":"Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks","volume":"22","author":"Zhang","year":"2012","journal-title":"Chaos"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2073140","DOI":"10.1155\/2020\/2073140","article-title":"Salient object detection based on weighted hypergraph and random walk","volume":"2020","author":"Wei","year":"2020","journal-title":"Math. Probl. Eng."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Chelali, M., Kurtz, C., Puissant, A., and Vincent, N. (2020). From pixels to random walk based segments for image time series deep classification. International Conference on Pattern Recognition and Artificial Intelligence, Springer.","DOI":"10.1007\/978-3-030-59830-3_30"},{"key":"ref_10","first-page":"6","article-title":"High-throughput segmentation of tiled biological structures using random salk distance transforms","volume":"6","author":"Baum","year":"2019","journal-title":"Integr. Comp. Biol."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1134\/S0016266319020084","article-title":"Open quantum random walks and quantum markov chains","volume":"53","author":"Dhahri","year":"2019","journal-title":"Funct. Anal. Its Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1108\/IR-05-2018-0096","article-title":"Matching for navigation map building for automated guided robot based on laser navigation without a reflector","volume":"46","author":"Zhang","year":"2019","journal-title":"Ind. Robot"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1350097","DOI":"10.1142\/S0129183113500976","article-title":"Mean first-passage time on a family of small-world treelike networks","volume":"25","author":"Li","year":"2014","journal-title":"Int. J. Mod. Phys. C"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"28733","DOI":"10.1038\/srep28733","article-title":"The entire mean weighted first-passage time on a family of weighted treelike networks","volume":"6","author":"Dai","year":"2016","journal-title":"Sci. Rep."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"075102","DOI":"10.1088\/1751-8113\/44\/7\/075102","article-title":"Effect of trap position on the efficiency of trapping in treelike scale-free networks","volume":"44","author":"Zhang","year":"2011","journal-title":"J. Phys. A Math. Theor."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1544","DOI":"10.1038\/s41598-018-19959-x","article-title":"Two types of weight-dependent walks with a trap in weighted scale-free treelike networks","volume":"8","author":"Dai","year":"2018","journal-title":"Sci. Rep."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"043120","DOI":"10.1063\/1.5123594","article-title":"Constructions and properties of a class of random scale-free networks","volume":"30","author":"Wang","year":"2020","journal-title":"Chaos"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"6898","DOI":"10.1109\/TIT.2019.2925610","article-title":"Low-Mean Hitting Time for Random Walks on Heterogeneous Networks","volume":"65","author":"Sheng","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"178701","DOI":"10.1103\/PhysRevLett.107.178701","article-title":"All scale-free network are sparse","volume":"107","author":"Gross","year":"2011","journal-title":"Phys. Rev. Lett."},{"key":"ref_20","unstructured":"Foster, R.M. (1949). The average impedance of an electrical network. Contrib. Appl. Mech. (Reissner Anniv. Vol.), 333\u2013340."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1691","DOI":"10.1016\/j.dam.2010.05.020","article-title":"Random walks and the effective resistance sum rules","volume":"158","author":"Chen","year":"2010","journal-title":"Discret. Appl. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF01164627","article-title":"Resistance distance","volume":"1","author":"Klein","year":"1993","journal-title":"J. Math. Chem."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1016\/j.dam.2006.09.008","article-title":"Resistance distance and the normalized Laplacian spectrum","volume":"155","author":"Chen","year":"2007","journal-title":"Discret. Appl. Math."},{"key":"ref_24","first-page":"982","article-title":"The quasi-Wiener and the Kirchhoff indices coincide","volume":"36","author":"Gutman","year":"1996","journal-title":"J. Chem. Inf. Model."},{"key":"ref_25","unstructured":"Kemeny, J.G., and Snell, J.L. (1976). Finite Markov Chains, Springer."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1038\/nature06201","article-title":"First-passage times in complex scale-invariant media","volume":"450","author":"Condamin","year":"2007","journal-title":"Nature"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0024-3795(94)90084-1","article-title":"Reverse order laws for the generalized inverses of multiple matrix products","volume":"211","author":"Tian","year":"1944","journal-title":"Linear Algebra Its Appl."},{"key":"ref_28","first-page":"87","article-title":"Resistance distance in graphs","volume":"68","author":"Bapat","year":"1999","journal-title":"Mathmatics Stud."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/34\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:53:07Z","timestamp":1760169187000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,24]]},"references-count":28,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["e24010034"],"URL":"https:\/\/doi.org\/10.3390\/e24010034","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,12,24]]}}}