{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:51:11Z","timestamp":1764784271347,"version":"3.37.3"},"reference-count":54,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T00:00:00Z","timestamp":1587081600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872093","61803248"],"award-info":[{"award-number":["61872093","61803248"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Key R & D Program of China","award":["2018YFB1305104"],"award-info":[{"award-number":["2018YFB1305104"]}]},{"name":"Shanghai Municipal Science and Technology Major","award":["2018SHZDZX01"],"award-info":[{"award-number":["2018SHZDZX01"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,8,20]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Sierpi\u0144ski graphs and hierarchical graphs are two much studied self-similar networks, both of which are iteratively constructed and have the same number of vertices and edges at any iteration, but display entirely different topological properties. Both graphs have a large variety of applications: Sierpi\u0144ski graphs have a close connection with WK-recursive networks that are employed extensively in the design and implementation of local area networks and parallel processing architectures, while hierarchical graphs can be used to model complex networks. In this paper, we study hitting times for several absorbing random walks in Sierpi\u0144ski graphs and hierarchical graphs. For all considered random walks, we determine exact solutions to hitting times for both graphs. The obtained explicit expressions indicate that the hitting times in both graphs behave quite differently. We show that the structural difference of the graphs is responsible for the disparate behaviors of their hitting times.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz080","type":"journal-article","created":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T04:38:20Z","timestamp":1564115900000},"page":"1385-1396","source":"Crossref","is-referenced-by-count":11,"title":["Hitting Times for Random Walks on Sierpi\u0144ski Graphs and Hierarchical Graphs"],"prefix":"10.1093","volume":"63","author":[{"given":"Yi","family":"Qi","sequence":"first","affiliation":[{"name":"Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 200433, China"},{"name":"Fudan-Zhongan Joint Laboratory of Blockchain and Information Security, Shanghai Engineering Research Institute of Blockchain, Shanghai 200433, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuze","family":"Dong","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 200433, China"},{"name":"Fudan-Zhongan Joint Laboratory of Blockchain and Information Security, Shanghai Engineering Research Institute of Blockchain, Shanghai 200433, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhongzhi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 200433, China"},{"name":"Fudan-Zhongan Joint Laboratory of Blockchain and Information Security, Shanghai Engineering Research Institute of Blockchain, Shanghai 200433, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhang","family":"Zhang","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 200433, China"},{"name":"Fudan-Zhongan Joint Laboratory of Blockchain and Information Security, Shanghai Engineering Research Institute of Blockchain, Shanghai 200433, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"2020091506341547700_ref1","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1023\/A:1022444205860","article-title":"Graphs $S\\left (n,k\\right )$ and a variant of the Tower of Hanoi problem","volume":"47","author":"Klav\u017ear","year":"1997","journal-title":"Czech. Math. J."},{"key":"2020091506341547700_ref2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-0237-6","volume-title":"The Tower of Hanoi\u2014Myths and Maths","author":"Hinz","year":"2013"},{"key":"2020091506341547700_ref3","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pbio.0020424","article-title":"Algorithmic self-assembly of DNA Sierpi\u0144ski triangles","volume":"2","author":"Rothemund","year":"2004","journal-title":"PLoS Biol."},{"key":"2020091506341547700_ref4","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1038\/nchem.2211","article-title":"Assembling molecular Sierpi\u0144ski triangle fractals","volume":"7","author":"Shang","year":"2015","journal-title":"Nat. Chem."},{"key":"2020091506341547700_ref5","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0301-0104(02)00550-5","article-title":"Strange kinetics of polymeric networks modelled by finite fractals","volume":"284","author":"Jurjiu","year":"2002","journal-title":"Chem. Phys."},{"key":"2020091506341547700_ref6","doi-asserted-by":"crossref","first-page":"1782","DOI":"10.1126\/science.1125894","article-title":"Nanoassembly of a fractal polymer: a molecular \u201cSierpi\u0144ski hexagonal gasket\u201d","volume":"312","author":"Newkome","year":"2006","journal-title":"Science"},{"key":"2020091506341547700_ref7","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1016\/j.dam.2016.09.024","article-title":"A survey and classification of Sierpi\u0144ski-type graphs","volume":"217","author":"Hinz","year":"2017","journal-title":"Discrete Appl. Math."},{"key":"2020091506341547700_ref8","doi-asserted-by":"crossref","first-page":"1822","DOI":"10.1016\/j.dam.2012.03.022","article-title":"The hamiltonicity and path $t$-coloring of Sierpi\u0144ski-like graphs","volume":"160","author":"Xue","year":"2012","journal-title":"Discrete Appl. Math."},{"key":"2020091506341547700_ref9","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1007\/s00224-010-9286-3","article-title":"The hub number of Sierpi\u0144ski-like graphs","volume":"49","author":"Lin","year":"2011","journal-title":"Theory Comput. Syst."},{"key":"2020091506341547700_ref10","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s00224-015-9621-9","article-title":"The outer-connected domination number of Sierpi\u0144ski-like graphs","volume":"58","author":"Chang","year":"2016","journal-title":"Theory Comput. Syst."},{"key":"2020091506341547700_ref11","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/j.tcs.2015.10.032","article-title":"The number and degree distribution of spanning trees in the Tower of Hanoi graph","volume":"609","author":"Zhang","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"2020091506341547700_ref12","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.jda.2015.01.008","article-title":"Structural properties of subdivided-line graphs","volume":"31","author":"Hasunuma","year":"2015","journal-title":"J. Discrete Algorithms"},{"key":"2020091506341547700_ref13","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0167-739X(88)90007-6","article-title":"A recursively scalable network VLSI implementation","volume":"4","author":"Della Vecchia","year":"1988","journal-title":"Future Gener. Comput. Syst."},{"key":"2020091506341547700_ref14","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1016\/j.tcs.2014.10.034","article-title":"Hamiltonicity of the basic WK-recursive pyramid with and without faulty nodes","volume":"562","author":"Wang","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"2020091506341547700_ref15","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1016\/j.sysarc.2008.04.005","article-title":"Some topological and combinatorial properties of WK-recursive mesh and WK-pyramid interconnection networks","volume":"54","author":"Farahabady","year":"2008","journal-title":"J. Syst. Archit."},{"key":"2020091506341547700_ref16","doi-asserted-by":"crossref","first-page":"5611","DOI":"10.1016\/j.ins.2007.04.013","article-title":"The $m$-pancycle-connectivity of a WK-recursive network","volume":"177","author":"Fang","year":"2007","journal-title":"Inf. Sci."},{"key":"2020091506341547700_ref17","first-page":"131","article-title":"Novel broadcasting algorithm of the complete recursive network","volume":"31","author":"Fang","year":"2007","journal-title":"Informatica"},{"key":"2020091506341547700_ref18","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1109\/71.588608","article-title":"A shortest path routing algorithm for incomplete WK-recursive networks","volume":"8","author":"Su","year":"1997","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2020091506341547700_ref19","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1109\/TPDS.2005.109","article-title":"Hamiltonicity of the WK-recursive network with and without faulty nodes","volume":"16","author":"Fu","year":"2005","journal-title":"IEEE Trans. Parallel Distrib Syst."},{"key":"2020091506341547700_ref20","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.dam.2008.04.018","article-title":"The hierarchical product of graphs","volume":"157","author":"Barri\u00e8re","year":"2009","journal-title":"Discrete Appl. Math."},{"key":"2020091506341547700_ref21","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1080\/03081080802305381","article-title":"On the hierarchical product of graphs and the generalized binomial tree","volume":"57","author":"Barri\u00e8re","year":"2009","journal-title":"Linear Multilinear Algebra"},{"key":"2020091506341547700_ref22","doi-asserted-by":"crossref","first-page":"3871","DOI":"10.1016\/j.disc.2008.10.028","article-title":"The generalized hierarchical product of graphs","volume":"309","author":"Barri\u00e8re","year":"2009","journal-title":"Discrete Math."},{"key":"2020091506341547700_ref23","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1017\/S0004972700007760","article-title":"A new graph product and its spectrum","volume":"18","author":"Godsil","year":"1978","journal-title":"Bull. Austral. Math. Soc."},{"key":"2020091506341547700_ref24","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1093\/comjnl\/bxx094","article-title":"Extended corona product as an exactly tractable model for weighted heterogeneous networks","volume":"61","author":"Qi","year":"2018","journal-title":"Comput. J."},{"key":"2020091506341547700_ref25","first-page":"985","article-title":"Kronecker graphs: an approach to modeling networks","volume":"11","author":"Leskovec","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"2020091506341547700_ref26","doi-asserted-by":"crossref","first-page":"2131","DOI":"10.1098\/rsif.2011.0840","article-title":"Dynamics and processing in finite self-similar networks","volume":"9","author":"DeDeo","year":"2012","journal-title":"J. R. Soc. Interface"},{"key":"2020091506341547700_ref27","doi-asserted-by":"crossref","first-page":"9024","DOI":"10.1038\/srep09024","article-title":"Laplacian spectra of a class of small-world networks and their applications","volume":"5","author":"Liu","year":"2015","journal-title":"Sci. Rep."},{"key":"2020091506341547700_ref28","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1109\/TCYB.2017.2781714","article-title":"Consensus in self-similar hierarchical graphs and Sierpi\u0144ski graphs: convergence speed, delay robustness, and coherence","volume":"49","author":"Qi","year":"2019","journal-title":"IEEE Trans. Cybern."},{"key":"2020091506341547700_ref29","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.92.118701","article-title":"Random walks on complex networks","volume":"92","author":"Noh","year":"2004","journal-title":"Phys. Rev. Lett."},{"key":"2020091506341547700_ref30","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"},{"volume-title":"Finite Markov Chains","year":"1976","author":"Kemeny","key":"2020091506341547700_ref31"},{"key":"2020091506341547700_ref32","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-4149(74)90001-5","article-title":"Random walks on graphs","volume":"2","author":"Gobel","year":"1974","journal-title":"Stoch. Proc. Their Appl."},{"key":"2020091506341547700_ref33","first-page":"218","article-title":"Random walks, universal traversal sequences, and the complexity of maze problems","volume-title":"Proc. 20th Ann. Symp. Found. Comput. Sci.","author":"Aleliunas","year":"1979"},{"key":"2020091506341547700_ref34","first-page":"1","article-title":"Random Walks on Graphs: A Survey","volume":"2","author":"Lov\u00e1sz","year":"1993","journal-title":"Combinatorics , Paul Erdos is Eighty"},{"key":"2020091506341547700_ref35","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511606014","volume-title":"A Guide to First-Passage Processes","author":"Redner","year":"2001"},{"key":"2020091506341547700_ref36","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1145\/956750.956782","article-title":"Algorithms for estimating relative importance in networks","volume-title":"Proc. 9th ACM SIGKDD Int. Conf. Knowl. Disc. Data Mining","author":"White","year":"2003"},{"key":"2020091506341547700_ref37","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1109\/JSAC.2010.100105","article-title":"Autonomic traffic engineering for network robustness","volume":"28","author":"Tizghadam","year":"2010","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"2020091506341547700_ref38","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.89.248701","article-title":"Optimal network topologies for local search with congestion","volume":"89","author":"Guimer\u00e0","year":"2002","journal-title":"Phys. Rev. Lett."},{"key":"2020091506341547700_ref39","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1109\/TCNS.2014.2357552","article-title":"Consensus and coherence in fractal networks","volume":"1","author":"Patterson","year":"2014","journal-title":"IEEE Trans. Control Netw. Syst."},{"key":"2020091506341547700_ref40","doi-asserted-by":"crossref","first-page":"2512","DOI":"10.1109\/TNET.2015.2475616","article-title":"On the efficiency of social recommender networks","volume":"24","author":"Wong","year":"2016","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"2020091506341547700_ref41","doi-asserted-by":"crossref","DOI":"10.5948\/UPO9781614440222","volume-title":"Random Walks and Electric Networks","author":"Doyle","year":"1984"},{"key":"2020091506341547700_ref42","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1007\/s00214-003-0460-4","article-title":"Resistance distance and Laplacian spectrum","volume":"110","author":"Xiao","year":"2003","journal-title":"Theor. Chem. Acc."},{"key":"2020091506341547700_ref43","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF01164627","article-title":"Resistance distance","volume":"12","author":"Klein","year":"1993","journal-title":"J. Math. Chem."},{"key":"2020091506341547700_ref44","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/qua.560500102","article-title":"Molecular cyclicity and centricity of polycyclic graphs. I. Cyclicity based on resistance distances or reciprocal distances","volume":"50","author":"Bonchev","year":"1994","journal-title":"Int. J. Quantum Chem."},{"key":"2020091506341547700_ref45","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1021\/ci960007t","article-title":"The quasi-Wiener and the Kirchhoff indices coincide","volume":"36","author":"Gutman","year":"1996","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"2020091506341547700_ref46","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1021\/ci950116s","article-title":"Extensions of the Wiener number","volume":"36","author":"Zhu","year":"1996","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"2020091506341547700_ref47","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1137\/050645452","article-title":"Minimizing effective resistance of a graph","volume":"50","author":"Ghosh","year":"2008","journal-title":"SIAM Rev."},{"key":"2020091506341547700_ref48","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1007\/BF01270385","article-title":"The electrical resistance of a graph captures its commute and cover times","volume":"6","author":"Chandra","year":"1996","journal-title":"Comput. Complex."},{"key":"2020091506341547700_ref49","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1140\/epjb\/e2011-20338-0","article-title":"Random walks on dual Sierpi\u0144ski gaskets","volume":"82","author":"Wu","year":"2011","journal-title":"Eur. Phys. J. B"},{"key":"2020091506341547700_ref50","doi-asserted-by":"crossref","first-page":"11149","DOI":"10.1073\/pnas.200327197","article-title":"Classes of small-world networks","volume":"97","author":"Amaral","year":"2000","journal-title":"Proc. Natl. Acad. Sci. U. S. A."},{"key":"2020091506341547700_ref51","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"2020091506341547700_ref52","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1515\/9781400881338-007","article-title":"Solving the Tower of Hanoi with Random Moves","volume-title":"The Mathematics of Various Entertaining Subjects: Research in Recreational Math","author":"Alekseyev","year":"2016"},{"key":"2020091506341547700_ref53","first-page":"574","article-title":"The electrical resistance of a graph captures its commute and cover times","volume-title":"Proc. 21st ACM Symp. Theory Comput","author":"Chandra","year":"1989"},{"key":"2020091506341547700_ref54","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF01046996","article-title":"Random walks and the effective resistance of networks","volume":"4","author":"Tetali","year":"1991","journal-title":"J. Theor. Probab."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/9\/1385\/33747641\/bxz080.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/9\/1385\/33747641\/bxz080.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,14]],"date-time":"2021-01-14T16:40:43Z","timestamp":1610642443000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/63\/9\/1385\/5612725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,17]]},"references-count":54,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,4,17]]},"published-print":{"date-parts":[[2020,8,20]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz080","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2020,9]]},"published":{"date-parts":[[2020,4,17]]}}}