{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T13:47:13Z","timestamp":1744120033423,"version":"3.37.3"},"reference-count":60,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2019,12,9]],"date-time":"2019-12-09T00:00:00Z","timestamp":1575849600000},"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"}]},{"DOI":"10.13039\/501100012166","name":"National Key R & D Program of China","doi-asserted-by":"publisher","award":["2018YFB1305104"],"award-info":[{"award-number":["2018YFB1305104"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003399","name":"Shanghai Municipal Science and Technology Commission","doi-asserted-by":"publisher","award":["2018SHZDZX01"],"award-info":[{"award-number":["2018SHZDZX01"]}],"id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ZJLab"},{"name":"Fudan's Undergraduate Research Opportunities Program"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,1,19]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Subdivision, triangulation, Kronecker product, corona product and many other graph operations or products play an important role in complex networks. In this paper, we study the properties of $q$-subdivision graphs, which have been applied to model complex networks. For a simple connected graph $G$, its $q$-subdivision graph $S_q(G)$ is obtained from $G$ through replacing every edge $uv$ in $G$ by $q$ disjoint paths of length 2, with each path having $u$ and $v$ as its ends. We derive explicit formulas for many quantities of $S_q(G)$ in terms of those corresponding to $G$, including the eigenvalues and eigenvectors of normalized adjacency matrix, two-node hitting time, Kemeny constant, two-node resistance distance, Kirchhoff index, additive degree-Kirchhoff index and multiplicative degree-Kirchhoff index. We also study the properties of the iterated $q$-subdivision graphs, based on which we obtain the closed-form expressions for a family of hierarchical lattices, which has been used to describe scale-free fractal networks.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz141","type":"journal-article","created":{"date-parts":[[2019,10,28]],"date-time":"2019-10-28T12:07:48Z","timestamp":1572264468000},"page":"76-92","source":"Crossref","is-referenced-by-count":6,"title":["Spectra, Hitting Times and Resistance Distances of<i>q<\/i>- Subdivision Graphs"],"prefix":"10.1093","volume":"64","author":[{"given":"Yibo","family":"Zeng","sequence":"first","affiliation":[{"name":"Shanghai Key Laboratory of Intelligent Information, Shanghai 200433, China"},{"name":"School of Mathematical Sciences, Fudan University, Shanghai 200433, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhongzhi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of Intelligent Information, Shanghai 200433, China"},{"name":"School of Computer Science, Fudan University, Shanghai 200433, China"},{"name":"Fudan-Zhongan Joint Laboratory of Blockchain and Information Security, Fudan University, Shanghai, 200433, China"},{"name":"Shanghai Engineering Research Institute of Blockchain, Fudan University, Shanghai 200433, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,12,9]]},"reference":[{"key":"2021011807353164900_ref1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barab\u00e1si","year":"1999","journal-title":"Science"},{"key":"2021011807353164900_ref2","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":"2021011807353164900_ref3","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1038\/nature03248","article-title":"Self-similarity of complex networks","volume":"433","author":"Song","year":"2005","journal-title":"Nature"},{"key":"2021011807353164900_ref4","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","article-title":"The structure and function of complex networks","volume":"45","author":"Newman","year":"2003","journal-title":"SIAM Rev."},{"key":"2021011807353164900_ref5","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"key":"2021011807353164900_ref6","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.298.5594.824","article-title":"Network motifs: Simple building blocks of complex networks","volume":"298","author":"Milo","year":"2002","journal-title":"Science"},{"key":"2021011807353164900_ref7","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1145\/2736277.2741098","article-title":"The $k$-clique densest subgraph problem","volume-title":"Proceedings of the 24th International Conference on World Wide Web","author":"Tsourakakis","year":"2015"},{"key":"2021011807353164900_ref8","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.65.066122","article-title":"Pseudofractal scale-free web","volume":"65","author":"Dorogovtsev","year":"2002","journal-title":"Phys. Rev. E"},{"key":"2021011807353164900_ref9","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1016\/j.tcs.2010.11.036","article-title":"Farey graphs as models for complex networks","volume":"412","author":"Zhang","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"2021011807353164900_ref10","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.tcs.2017.03.009","article-title":"Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpi\u0144ski graph","volume":"677","author":"Shan","year":"2017","journal-title":"Theoret. Comput. Sci."},{"key":"2021011807353164900_ref11","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.tcs.2018.02.022","article-title":"Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpi\u0144ski gasket","volume":"720","author":"Shan","year":"2018","journal-title":"Theoret. Comput. Sci."},{"key":"2021011807353164900_ref12","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.94.018702","article-title":"Apollonian networks: Simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs","volume":"94","author":"Andrade","year":"2005","journal-title":"Phys. Rev. Lett."},{"key":"2021011807353164900_ref13","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.71.016128","article-title":"Self-similar disk packings as model spatial scale-free networks","volume":"71","author":"Doye","year":"2005","journal-title":"Phys. Rev. E"},{"key":"2021011807353164900_ref14","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.tcs.2017.08.024","article-title":"Maximum matchings and minimum dominating sets in apollonian networks and extended tower of Hanoi graphs","volume":"703","author":"Jin","year":"2017","journal-title":"Theoret. Comput. Sci."},{"key":"2021011807353164900_ref15","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1090\/S0002-9939-1962-0133816-6","article-title":"The Kronecker product of graphs","volume":"13","author":"Weichsel","year":"1962","journal-title":"Proc. Am. Math. Soc."},{"key":"2021011807353164900_ref16","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1145\/1273496.1273559","article-title":"Scalable modeling of real graphs using Kronecker multiplication","volume-title":"Proceedings of the 24th International Conference on Machine Learning, New York, NY, USA, 20-24 June","author":"Leskovec","year":"2007"},{"key":"2021011807353164900_ref17","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":"2021011807353164900_ref18","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":"Barriere","year":"2009","journal-title":"Discrete Appl. Math."},{"key":"2021011807353164900_ref19","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":"2021011807353164900_ref20","doi-asserted-by":"crossref","DOI":"10.1088\/1751-8113\/49\/22\/225202","article-title":"Deterministic hierarchical networks","volume":"49","author":"Barriere","year":"2016","journal-title":"J. Phys. A: Math. Theoret."},{"key":"2021011807353164900_ref21","doi-asserted-by":"crossref","DOI":"10.1088\/1742-5468\/2015\/11\/P11024","article-title":"Corona graphs as a model of small-world networks","volume":"2015","author":"Lv","year":"2015","journal-title":"J. Stat. Mech."},{"key":"2021011807353164900_ref22","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.dam.2017.01.005","article-title":"Structural and spectral properties of corona graphs","volume":"228","author":"Sharma","year":"2017","journal-title":"Discrete Appl. Math."},{"key":"2021011807353164900_ref23","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":"2021011807353164900_ref24","doi-asserted-by":"crossref","first-page":"37","DOI":"10.46298\/dmtcs.344","article-title":"Acyclic, star and oriented colourings of graph subdivisions","volume":"7","author":"Wood","year":"2005","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"2021011807353164900_ref25","doi-asserted-by":"crossref","first-page":"1349","DOI":"10.1007\/s40840-014-0095-8","article-title":"Maximal energy of subdivisions of graphs with a fixed chromatic number","volume":"38","author":"Hu","year":"2015","journal-title":"Bull. Malays. Math. Sci. Soc."},{"key":"2021011807353164900_ref26","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/j.endm.2016.09.051","article-title":"The group inverse of subdivision networks","volume":"54","author":"Carmona","year":"2016","journal-title":"Electron. Notes Discrete Math."},{"key":"2021011807353164900_ref27","first-page":"250","article-title":"The normalized Laplacian spectrum of subdivisions of a graph","volume":"286","author":"Xie","year":"2016","journal-title":"Appl. Math. Comput."},{"volume-title":"Introduction to Graph Theory","year":"2001","author":"West","key":"2021011807353164900_ref28"},{"key":"2021011807353164900_ref29","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/j.ipl.2012.04.004","article-title":"Acyclic chromatic indices of fully subdivided graphs","volume":"112","author":"Fiedorowicz","year":"2012","journal-title":"Inform. Process. Lett."},{"key":"2021011807353164900_ref30","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1103\/PhysRevB.38.728","article-title":"Family of diamond-type hierarchical lattices","volume":"38","author":"Yang","year":"1988","journal-title":"Phys. Rev. B"},{"key":"2021011807353164900_ref31","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1038\/nphys266","article-title":"Origins of fractality in the growth of complex networks","volume":"2","author":"Song","year":"2006","journal-title":"Nat. Phys."},{"key":"2021011807353164900_ref32","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1140\/epjb\/e2007-00107-6","article-title":"Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices","volume":"56","author":"Zhang","year":"2007","journal-title":"Eur. Phys. J. B"},{"key":"2021011807353164900_ref33","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1088\/1367-2630\/9\/6\/175","article-title":"Fractal and transfractal recursive scale-free nets","volume":"9","author":"Rozenfeld","year":"2007","journal-title":"New J. Phys."},{"key":"2021011807353164900_ref34","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1140\/epjb\/e2011-20564-4","article-title":"Role of fractal dimension in random walks on scale-free networks","volume":"84","author":"Zhang","year":"2011","journal-title":"Eur. Phys. J. B"},{"key":"2021011807353164900_ref35","doi-asserted-by":"crossref","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":"2021011807353164900_ref36","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.tcs.2017.02.027","article-title":"Maximum matchings in scale-free networks with identical degree distribution","volume":"675","author":"Li","year":"2017","journal-title":"Theoret. Comput. Sci."},{"volume-title":"Spectra of graphs: theory and application","year":"1980","author":"Cvetkovi\u0107","key":"2021011807353164900_ref37"},{"volume-title":"Spectral graph theory","year":"1997","author":"Chung","key":"2021011807353164900_ref38"},{"key":"2021011807353164900_ref39","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511606014","volume-title":"A guide to first-passage processes","author":"Redner","year":"2001"},{"key":"2021011807353164900_ref40","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1093\/comjnl\/bxy028","article-title":"Non-backtracking centrality based random walk on networks","volume":"62","author":"Lin","year":"2019","journal-title":"Comput. J."},{"key":"2021011807353164900_ref41","doi-asserted-by":"crossref","first-page":"1309","DOI":"10.1080\/03610926.2012.741742","article-title":"The role of Kemeny\u2019s constant in properties of Markov chains","volume":"43","author":"Hunter","year":"2014","journal-title":"Commun. Stat. \u2014 Theor. Methods"},{"key":"2021011807353164900_ref42","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":"2021011807353164900_ref43","first-page":"1","article-title":"Random walks on graphs","volume":"2","author":"Lov\u00e1sz","year":"1993","journal-title":"Combinatorics, Paul Erd\u00f6s is eighty"},{"key":"2021011807353164900_ref44","doi-asserted-by":"crossref","DOI":"10.5948\/UPO9781614440222","volume-title":"Random Walks and Electric Networks","author":"Doyle","year":"1984"},{"key":"2021011807353164900_ref45","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":"Discrete Appl. Math."},{"key":"2021011807353164900_ref46","first-page":"333","article-title":"The average impedance of an electrical network","author":"Foster","year":"1949","journal-title":"Contributions to Applied Mechanics (Reissner Anniversary Volume), ?"},{"key":"2021011807353164900_ref47","first-page":"574","article-title":"The electrical resistance of a graph captures its commute and cover times","volume-title":"Proc. 21st Ann. ACM Symp. Theory Comput.","author":"Chandra","year":"1989"},{"key":"2021011807353164900_ref48","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":"2021011807353164900_ref49","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":"2021011807353164900_ref50","doi-asserted-by":"crossref","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":"2021011807353164900_ref51","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":"2021011807353164900_ref52","doi-asserted-by":"crossref","first-page":"3242","DOI":"10.1093\/comjnl\/bxv014","article-title":"Small-world topology can significantly improve the performance of noisy consensus in a complex network","volume":"58","author":"Yi","year":"2015","journal-title":"Comput. J."},{"key":"2021011807353164900_ref53","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":"2021011807353164900_ref54","first-page":"2377","article-title":"Kirchhoff index as a measure of edge centrality in weighted networks: Nearly linear time algorithms","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Li","year":"2018"},{"key":"2021011807353164900_ref55","first-page":"27","article-title":"Degree resistance distance of unicyclic graphs","volume":"1","author":"Gutman","year":"2012","journal-title":"Trans. Combin."},{"key":"2021011807353164900_ref56","first-page":"250","article-title":"The normalized Laplacian spectrum of subdivisions of a graph","volume":"286","author":"Xie","year":"2016","journal-title":"Appl. Math. Comput."},{"key":"2021011807353164900_ref57","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.dam.2014.02.015","article-title":"The Kirchhoff index of subdivisions of graphs","volume":"171","author":"Yang","year":"2014","journal-title":"Discrete Appl. Math."},{"key":"2021011807353164900_ref58","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.dam.2014.08.039","article-title":"Resistance distance-based graph invariants of subdivisions and triangulations of graphs","volume":"181","author":"Yang","year":"2015","journal-title":"Discrete Appl. Math."},{"key":"2021011807353164900_ref59","first-page":"1123","article-title":"On the spectrum of the normalized Laplacian of iterated triangulations of graphs","volume":"273","author":"Xie","year":"2016","journal-title":"Appl. Math. Comput."},{"key":"2021011807353164900_ref60","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/j.physa.2006.11.006","article-title":"A general geometric growth model for pseudofractal scale-free web","volume":"377","author":"Zhang","year":"2007","journal-title":"Physica A"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/1\/76\/35886274\/bxz141.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/1\/76\/35886274\/bxz141.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,2]],"date-time":"2022-10-02T20:39:31Z","timestamp":1664743171000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/1\/76\/5670503"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,9]]},"references-count":60,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2019,12,9]]},"published-print":{"date-parts":[[2021,1,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz141","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2021,1]]},"published":{"date-parts":[[2019,12,9]]}}}