{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T02:31:41Z","timestamp":1771900301854,"version":"3.50.1"},"reference-count":33,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computer Networks"],"published-print":{"date-parts":[[2008,1]]},"DOI":"10.1016\/j.comnet.2007.09.012","type":"journal-article","created":{"date-parts":[[2007,10,2]],"date-time":"2007-10-02T11:31:13Z","timestamp":1191324673000},"page":"44-60","source":"Crossref","is-referenced-by-count":37,"title":["The power of choice in random walks: An empirical study"],"prefix":"10.1016","volume":"52","author":[{"given":"Chen","family":"Avin","sequence":"first","affiliation":[]},{"given":"Bhaskar","family":"Krishnamachari","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.comnet.2007.09.012_bib1","unstructured":"M. Alanyali, V. Saligrama, O. Sava, A random-walk model for distributed computation in energy-limited network, in: Proc. of 1st Workshop on Information Theory and its Application, San Diego, 2006."},{"key":"10.1016\/j.comnet.2007.09.012_bib2","unstructured":"D. Aldous, J. Fill, Reversible Markov Chains and Random Walks on Graphs. 1999. Unpublished. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/stat-www.berkeley.edu\/users\/aldous\/RWG\/book.html."},{"issue":"1","key":"10.1016\/j.comnet.2007.09.012_bib3","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF01048272","article-title":"Lower bounds for covering times for reversible Markov chains and random walks on graphs","volume":"2","author":"Aldous","year":"1989","journal-title":"J. Theor. Prob."},{"key":"10.1016\/j.comnet.2007.09.012_bib4","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lov\u00e1sz, C. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, in: 20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, 1979), IEEE, New York, 1979, pp. 218\u2013223.","DOI":"10.1109\/SFCS.1979.34"},{"key":"10.1016\/j.comnet.2007.09.012_bib5","doi-asserted-by":"crossref","unstructured":"C. Avin, C. Brito, Efficient and robust query processing in dynamic environments using random walk techniques, in: Proc. of the Third International Symposium on Information processing in sensor networks, 2004, pp. 277\u2013286.","DOI":"10.1145\/984622.984663"},{"key":"10.1016\/j.comnet.2007.09.012_bib6","doi-asserted-by":"crossref","unstructured":"C. Avin, G. Ercal, On the cover time of random geometric graphs, in: Proc. Automata, Languages and Programming, 32nd International Colloquium, ICALP05 2005, pp. 677\u2013689.","DOI":"10.1007\/11523468_55"},{"key":"10.1016\/j.comnet.2007.09.012_bib7","doi-asserted-by":"crossref","unstructured":"Y. Azar, A. Broder, A. Karlin, E. Upfal, E. Balanced allocations, in: Proc. 26th ACM Symp. Theory of Computing 1994, pp. 593\u2013602.","DOI":"10.1145\/195058.195412"},{"key":"10.1016\/j.comnet.2007.09.012_bib8","doi-asserted-by":"crossref","unstructured":"D. Braginsky, D. Estrin, Rumor routing algorithm for sensor networks, in: Proc. of the 1st ACM Int. workshop on Wireless sensor networks and applications 2002, ACM Press, pp. 22\u201331.","DOI":"10.1145\/570738.570742"},{"key":"10.1016\/j.comnet.2007.09.012_bib9","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF01048273","article-title":"Bounds on the cover time","volume":"2","author":"Broder","year":"1989","journal-title":"J. Theor. Prob."},{"key":"10.1016\/j.comnet.2007.09.012_bib10","doi-asserted-by":"crossref","unstructured":"A.K. Chandra, P. Raghavan, W.L. Ruzzo, R. Smolensky, The electrical resistance of a graph captures its commute and cover times, in: Proc. of the Twenty-first Annual ACM Symposium on Theory of Computing 1989, ACM Press, pp. 574\u2013586.","DOI":"10.1145\/73007.73062"},{"key":"10.1016\/j.comnet.2007.09.012_bib11","unstructured":"C. Cooper, A. Frieze, The cover time of sparse random graphs, in: Proceedings of the fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), ACM Press, Baltimore, Maryland, USA, 2003, pp. 140\u2013147."},{"key":"10.1016\/j.comnet.2007.09.012_bib12","doi-asserted-by":"crossref","unstructured":"S. Dolev, E. Schiller, J. Welch, Random walk for self-stabilizing group communication in ad-hoc networks, in: Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS\u201902) IEEE Computer Society, 2002, p. 70.","DOI":"10.1145\/571865.571872"},{"issue":"4","key":"10.1016\/j.comnet.2007.09.012_bib13","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1002\/rsa.3240060406","article-title":"A tight lower bound on the cover time for random walks on graphs","volume":"6","author":"Feige","year":"1995","journal-title":"Rand. Struct. Algorithms"},{"issue":"1","key":"10.1016\/j.comnet.2007.09.012_bib14","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/rsa.3240060106","article-title":"A tight upper bound on the cover time for random walks on graphs","volume":"6","author":"Feige","year":"1995","journal-title":"Rand. Struct. Algorithms"},{"key":"10.1016\/j.comnet.2007.09.012_bib15","doi-asserted-by":"crossref","unstructured":"C. Gkantsidis, M. Mihail, A. Saberi, Random walks in peer-to-peer networks, INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, 7\u201311 March 2004, pp. 120\u2013130.","DOI":"10.1109\/INFCOM.2004.1354487"},{"issue":"1\u20132","key":"10.1016\/j.comnet.2007.09.012_bib16","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1023\/A:1006314320276","article-title":"Heavy-tailed phenomena in satisfiability and constraint satisfaction problems","volume":"24","author":"Gomes","year":"2000","journal-title":"J. Autom. Reason."},{"key":"10.1016\/j.comnet.2007.09.012_bib17","doi-asserted-by":"crossref","unstructured":"P. Gupta, P.R. Kumar, Critical power for asymptotic connectivity in wireless networks, in: Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, 1998, pp. 547\u2013566.","DOI":"10.1007\/978-1-4612-1784-8_33"},{"key":"10.1016\/j.comnet.2007.09.012_bib18","series-title":"Approximations for NP-hard Problems","first-page":"482","article-title":"The Markov chain monte carlo method: an approach to approximate counting and integration","author":"Jerrum","year":"1997"},{"issue":"3","key":"10.1016\/j.comnet.2007.09.012_bib19","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1017\/S0963548398003538","article-title":"On the cover time for random walks on random graphs","volume":"7","author":"Jonasson","year":"1998","journal-title":"Comb. Prob. Comput."},{"key":"10.1016\/j.comnet.2007.09.012_bib20","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1214\/ECP.v5-1022","article-title":"On the cover time of planar graphs","volume":"5","author":"Jonasson","year":"2000","journal-title":"Electron. Commun. Prob."},{"key":"10.1016\/j.comnet.2007.09.012_bib21","unstructured":"D. Kempe, A. Dobra, J. Gehrke, Gossip-based computation of aggregate information, in: Proc. of the 44th Annual IEEE Symposium on Foundations of Computer Science 2003, pp. 482\u2013491."},{"key":"10.1016\/j.comnet.2007.09.012_bib22","unstructured":"L. Lov\u00e1sz, Random walks on graphs: A survey, in: Combinatorics, Paul Erd\u0151s is eighty, vol. 2 (Keszthely, 1993), vol. 2 of Bolyai Soc. Math. Stud. J\u00e1nos Bolyai Math. Soc., Budapest, 1996, pp. 353\u2013397."},{"issue":"1","key":"10.1016\/j.comnet.2007.09.012_bib23","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1214\/aop\/1176991894","article-title":"Covering problems for Brownian motion on spheres","volume":"16","author":"Matthews","year":"1988","journal-title":"Ann. Prob."},{"key":"10.1016\/j.comnet.2007.09.012_bib24","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher, A.M. Richa, R. Sitaraman, The power of two random choices: A survey of techniques and results, in: Handbook of Randomized Computing, vol. I. Kluwer Academic Press, 2001, pp. 255\u2013312.","DOI":"10.1007\/978-1-4615-0013-1_9"},{"key":"10.1016\/j.comnet.2007.09.012_bib25","series-title":"Randomized Algorithms","author":"Motwani","year":"1995"},{"issue":"1","key":"10.1016\/j.comnet.2007.09.012_bib26","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF01205239","article-title":"Vertex-reinforced random walk","volume":"92","author":"Pemantle","year":"1992","journal-title":"Prob. Theory Relat. Fields"},{"issue":"3","key":"10.1016\/j.comnet.2007.09.012_bib27","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1137\/1037083","article-title":"Convergence rates for Markov chains","volume":"37","author":"Rosenthal","year":"1995","journal-title":"SIAM Rev."},{"issue":"1","key":"10.1016\/j.comnet.2007.09.012_bib28","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.adhoc.2003.08.001","article-title":"Active query forwarding in sensor networks (acquire)","volume":"3","author":"Sadagopan","year":"2005","journal-title":"J. Ad Hoc Networks"},{"key":"10.1016\/j.comnet.2007.09.012_bib29","doi-asserted-by":"crossref","unstructured":"S.D. Servetto, G. Barrenechea, Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks, in: Proc. of the first ACM Int. workshop on Wireless sensor networks and applications ACM Press, 2002, pp. 12\u201321.","DOI":"10.1145\/570738.570741"},{"key":"10.1016\/j.comnet.2007.09.012_bib30","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":"Sinclair","year":"1992","journal-title":"Comb. Prob. Comput."},{"issue":"1","key":"10.1016\/j.comnet.2007.09.012_bib31","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1214\/aop\/1008956322","article-title":"Vertex-reinforced random walk on arbitrary graphs","volume":"29","author":"Volkov","year":"2001","journal-title":"Ann. Prob."},{"key":"10.1016\/j.comnet.2007.09.012_bib32","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/3-540-49543-6_10","article-title":"Robotic exploration, brownian motion and electrical resistance","volume":"1518","author":"Wagner","year":"1998","journal-title":"Lecture Notes Comput. Sci."},{"key":"10.1016\/j.comnet.2007.09.012_bib33","doi-asserted-by":"crossref","unstructured":"D. Zuckerman, A technique for lower bounding the cover time, in: Proc. of the twenty-second annual ACM symposium on Theory of computing, ACM Press, 1990, pp. 254\u2013259.","DOI":"10.1145\/100216.100249"}],"container-title":["Computer Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S138912860700268X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S138912860700268X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T10:31:17Z","timestamp":1737455477000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/linkinghub.elsevier.com\/retrieve\/pii\/S138912860700268X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["S138912860700268X"],"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1016\/j.comnet.2007.09.012","relation":{},"ISSN":["1389-1286"],"issn-type":[{"value":"1389-1286","type":"print"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}