{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T04:42:16Z","timestamp":1768106536283,"version":"3.49.0"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2020,12,14]],"date-time":"2020-12-14T00:00:00Z","timestamp":1607904000000},"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"],"award-info":[{"award-number":["61872093"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61803248"],"award-info":[{"award-number":["61803248"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U20B2051"],"award-info":[{"award-number":["U20B2051"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U19A2066"],"award-info":[{"award-number":["U19A2066"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,2,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The mixing time of random walks on a graph has found broad applications across both theoretical and practical aspects of computer science, with the application effects depending on the behavior of mixing time. It is extensively believed that real-world networks, especially social networks, are fast mixing with their mixing time at most $O(\\log N)$ where $N$ is the number of vertices. However, the behavior of mixing time in the real-life networks has not been examined carefully, and exactly analytical research for mixing time in models mimicking real networks is still lacking. In this paper, we first experimentally evaluate the mixing time of various real-world networks with scale-free small-world properties and show that their mixing time is much higher than anticipated. To better understand the behavior of the mixing time for real-world networks, we then analytically study the mixing time of the Apollonian network, which is simultaneously scale-free and small-world. To this end, we derive the recursive relations for all eigenvalues, especially the second largest eigenvalue modulus of the transition matrix, based on which we deduce a lower bound for the mixing time of the Apollonian network, which approximately scales sublinearly with $N$. Our results indicate that real-world networks are not always fast mixing, which has potential implications in the design of algorithms related to mixing time.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaa150","type":"journal-article","created":{"date-parts":[[2020,10,13]],"date-time":"2020-10-13T11:38:13Z","timestamp":1602589093000},"page":"236-244","source":"Crossref","is-referenced-by-count":3,"title":["Real-World Networks Are Not Always Fast Mixing"],"prefix":"10.1093","volume":"64","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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wanyue","family":"Xu","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 200433, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liwang","family":"Zhu","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, 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":"Shanghai Engineering Research Institute of Blockchain, Shanghai 200433, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,12,14]]},"reference":[{"key":"2021021509575152100_ref1","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":"2021021509575152100_ref2","doi-asserted-by":"crossref","first-page":"7746","DOI":"10.1073\/pnas.0700250104","article-title":"Scaling theory of transport in complex biological networks","volume":"104","author":"Gallos","year":"2007","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"key":"2021021509575152100_ref3","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1561\/0400000003","article-title":"Mathematical aspects of mixing times in Markov chains","volume":"1","author":"Montenegro","year":"2006","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"2021021509575152100_ref4","volume-title":"Markov Chains and Mixing Times","author":"Levin","year":"2009"},{"key":"2021021509575152100_ref5","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1198\/jasa.2006.s74","article-title":"Probability and computing: randomized algorithms and probabilistic analysis","volume":"101","author":"Buot","year":"2006","journal-title":"J. Am. Stat. Assoc."},{"key":"2021021509575152100_ref6","doi-asserted-by":"crossref","first-page":"2508","DOI":"10.1109\/TIT.2006.874516","article-title":"Randomized gossip algorithms","volume":"52","author":"Boyd","year":"2006","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2021021509575152100_ref7","first-page":"670","article-title":"Towards efficient sampling: exploiting random walk strategies","volume-title":"Proc. 18th AAAI Conf. Artificial Intelligence","author":"Wei","year":"2004"},{"key":"2021021509575152100_ref8","first-page":"471","article-title":"On sampling nodes in a network","volume-title":"Proc. 25th Int. Conf. World Wide Web","author":"Chiericetti","year":"2016"},{"key":"2021021509575152100_ref9","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/s10618-018-0587-5","article-title":"Sampling online social networks by random walk with indirect jumps","volume":"33","author":"Zhao","year":"2019","journal-title":"Data Min. Knowl. Disc."},{"key":"2021021509575152100_ref10","first-page":"3","article-title":"Sybillimit: a near-optimal social network defense against sybil attacks","volume-title":"IEEE Symposium on Security and Privacy","author":"Yu","year":"2008"},{"key":"2021021509575152100_ref11","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1109\/TNET.2008.923723","article-title":"Sybilguard: defending against sybil attacks via social networks","volume":"16","author":"Yu","year":"2008","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"2021021509575152100_ref12","first-page":"1","article-title":"Sybilinfer: detecting sybil nodes using social networks","volume-title":"Proc. 16th Network and Distributed System Security Conf.","author":"Danezis","year":"2009"},{"key":"2021021509575152100_ref13","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1145\/2034575.2034593","article-title":"Sybil defenses via social networks: a tutorial and survey","volume":"42","author":"Yu","year":"2011","journal-title":"ACM SIGACT News"},{"key":"2021021509575152100_ref14","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1137\/S0036144503423264","article-title":"Fastest mixing Markov chain on a graph","volume":"46","author":"Boyd","year":"2004","journal-title":"SIAM Rev."},{"key":"2021021509575152100_ref15","first-page":"1661","article-title":"The mixing time of the Newman\u2013Watts small world","volume-title":"Proc. Twenty-Third Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"Addario-Berry","year":"2012"},{"key":"2021021509575152100_ref16","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1002\/rsa.20539","article-title":"The mixing time of the giant component of a random graph","volume":"45","author":"Benjamini","year":"2014","journal-title":"Random Struct. Algor."},{"key":"2021021509575152100_ref17","first-page":"1459","article-title":"Mixing time estimation in reversible Markov chains from a single sample path","volume-title":"Proc. 28th Int. Conf. Neural Information Processing Systems","author":"Hsu","year":"2015"},{"key":"2021021509575152100_ref18","first-page":"524","article-title":"The mixing of Markov chains on linear extensions in practice","volume-title":"Proc. 26th Int. Joint Conf. Artificial Intelligence","author":"Talvitie","year":"2017"},{"key":"2021021509575152100_ref19","doi-asserted-by":"crossref","first-page":"105851","DOI":"10.1016\/j.ipl.2019.105851","article-title":"Mixing time bounds for graphlet random walks","volume":"152","author":"Agostini","year":"2019","journal-title":"Inform. Process. Lett."},{"key":"2021021509575152100_ref20","first-page":"1144","article-title":"On hitting time, mixing time and geometric interpretations of metropolis\u2013hastings reversiblizations","volume":"33","author":"Choi","year":"2020","journal-title":"J. Theor. Probab."},{"key":"2021021509575152100_ref21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s00440-019-00913-5","article-title":"Polynomial mixing time of edge flips on quadrangulations","volume":"176","author":"Caraceni","year":"2020","journal-title":"Probab. Theory Relat. Fields"},{"key":"2021021509575152100_ref22","first-page":"111","article-title":"Whanau: asybil-proof distributed hashtable","volume-title":"Proc. 9th Usenix Conf. Networked Systems Design and Implementation","author":"Chris Lesniewskilaas","year":"2012"},{"key":"2021021509575152100_ref23","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1145\/1879141.1879191","article-title":"Measuring the mixing time of social graphs","volume-title":"Proc. 10th ACM SIGCOMM Conf. Internet Measurement","author":"Mohaisen","year":"2010"},{"key":"2021021509575152100_ref24","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":"2021021509575152100_ref25","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":"2021021509575152100_ref26","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":"2021021509575152100_ref27","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":"2021021509575152100_ref28","volume-title":"Finite Markov Chains","author":"Kemeny","year":"1983"},{"key":"2021021509575152100_ref29","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1017\/S0963548300000390","article-title":"Improved bounds for mixing rates of Markov chains and multicommodity flow","volume":"1","author":"Alistair","year":"1992","journal-title":"Combin. Probab. Comput."},{"key":"2021021509575152100_ref30","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":"2021021509575152100_ref31","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.74.046105","article-title":"Evolving Apollonian networks with small-world scale-free topologies","volume":"74","author":"Zhang","year":"2006","journal-title":"Phys. Rev. E"},{"key":"2021021509575152100_ref32","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.dam.2014.01.015","article-title":"The number of spanning trees in Apollonian networks","volume":"169","author":"Zhang","year":"2014","journal-title":"Discrete Appl. Math."},{"key":"2021021509575152100_ref33","doi-asserted-by":"crossref","DOI":"10.1088\/1742-5468\/2014\/10\/P10043","article-title":"Tutte polynomial of the Apollonian network","volume":"2014","author":"Liao","year":"2014","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"2021021509575152100_ref34","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1017\/apr.2015.11","article-title":"The degree profile and weight in Apollonian networks and $\\mathrm{k}$-trees","volume":"48","author":"Zhang","year":"2016","journal-title":"Adv. Appl. Prob."},{"key":"2021021509575152100_ref35","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":"2021021509575152100_ref36","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":"2021021509575152100_ref37","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1006\/jfan.1998.3297","article-title":"Spectral analysis on infinite Sierpi\u0144ski gaskets","volume":"159","author":"Teplyaev","year":"1998","journal-title":"J. Funct. Anal."},{"key":"2021021509575152100_ref38","doi-asserted-by":"crossref","first-page":"2553","DOI":"10.1016\/j.spa.2011.07.007","article-title":"Markov chain mixing time on cycles","volume":"121","author":"Gerencser","year":"2011","journal-title":"Stoch. Process. Appl."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/2\/236\/36258822\/bxaa150.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/2\/236\/36258822\/bxaa150.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,15]],"date-time":"2021-02-15T10:51:08Z","timestamp":1613386268000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/2\/236\/6032261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,14]]},"references-count":38,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,12,14]]},"published-print":{"date-parts":[[2021,2,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaa150","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,2]]},"published":{"date-parts":[[2020,12,14]]}}}