{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:18:01Z","timestamp":1763468281237,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2010-T2-2-082"],"award-info":[{"award-number":["MOE2010-T2-2-082"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2008348"],"award-info":[{"award-number":["2008348"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001475","name":"Nanyang Technological University","doi-asserted-by":"publisher","award":["M58110000"],"award-info":[{"award-number":["M58110000"]}],"id":[{"id":"10.13039\/501100001475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-0915985, CCF-1216038, CCF-1422715"],"award-info":[{"award-number":["CNS-0915985, CCF-1216038, CCF-1422715"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2015,11,2]]},"abstract":"<jats:p>\n            We study a distributed randomized information propagation mechanism in networks we call the\n            <jats:italic>coalescing-branching<\/jats:italic>\n            random walk (cobra walk, for short). A cobra walk is a generalization of the well-studied \u201cstandard\u201d random walk, and is useful in modeling and understanding the Susceptible-Infected- Susceptible (SIS)-type of epidemic processes in networks. It can also be helpful in performing light-weight information dissemination in resource-constrained networks. A cobra walk is parameterized by a\n            <jats:italic>branching factor<\/jats:italic>\n            <jats:italic>k<\/jats:italic>\n            . The process starts from an arbitrary vertex, which is labeled\n            <jats:italic>active<\/jats:italic>\n            for step 1. In each step of a cobra walk, each active vertex chooses\n            <jats:italic>k<\/jats:italic>\n            random neighbors to become active for the next step (\u201cbranching\u201d). A vertex is active for step\n            <jats:italic>t<\/jats:italic>\n            + 1 only if it is chosen by an active vertex in step\n            <jats:italic>t<\/jats:italic>\n            (\u201ccoalescing\u201d). This results in a stochastic process in the underlying network with properties that are quite different from both the standard random walk (which is equivalent to the cobra walk with branching factor 1) as well as other gossip-based rumor spreading mechanisms.\n          <\/jats:p>\n          <jats:p>\n            We focus on the\n            <jats:italic>cover time<\/jats:italic>\n            of the cobra walk, which is the number of steps for the walk to reach all the vertices, and derive almost-tight bounds for various graph classes. We show an\n            <jats:italic>O<\/jats:italic>\n            (log\u2009\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) high probability bound for the cover time of cobra walks on expanders, if either the expansion factor or the branching factor is sufficiently large; we also obtain an\n            <jats:italic>O<\/jats:italic>\n            (log\u2009\n            <jats:italic>n<\/jats:italic>\n            ) high probability bound for the\n            <jats:italic>partial cover time<\/jats:italic>\n            , which is the number of steps needed for the walk to reach at least a constant fraction of the vertices. We also show that the cover time of the cobra walk is, with high probability,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\u2009\n            <jats:italic>n<\/jats:italic>\n            ) on any\n            <jats:italic>n<\/jats:italic>\n            -vertex tree for\n            <jats:italic>k<\/jats:italic>\n            \u2265 2,\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>\n              n\n              <jats:sup>1\/d<\/jats:sup>\n            <\/jats:italic>\n            ) on a\n            <jats:italic>d<\/jats:italic>\n            -dimensional grid for\n            <jats:italic>k<\/jats:italic>\n            \u2265 2, and\n            <jats:italic>O<\/jats:italic>\n            (log\u2009\n            <jats:italic>n<\/jats:italic>\n            ) on the complete graph.\n          <\/jats:p>","DOI":"10.1145\/2817830","type":"journal-article","created":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T17:09:35Z","timestamp":1446484175000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Coalescing-Branching Random Walks on Graphs"],"prefix":"10.1145","volume":"2","author":[{"given":"Chinmoy","family":"Dutta","sequence":"first","affiliation":[{"name":"Twitter, San Francisco, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[{"name":"University of Houston, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Scott","family":"Roche","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780626"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378557"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0377-4"},{"key":"e_1_2_1_4_1","unstructured":"Itai Benjamini and Sebastian M\u00fcller. 2010. On the trace of branching random walks. arXiv preprint arXiv:1002.2781."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873716"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070475"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63516"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11553762_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/100793104"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806745"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873736"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-005-0237-z"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1208774"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2005.01.003"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332440"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582745"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835745"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_57"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10626-010-0092-5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0914402107"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_36"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.010"},{"key":"e_1_2_1_24_1","unstructured":"U. Feige. 1993. A Tight Upper Bound on the Cover Time for Random Walks on Graphs. (1993)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060406"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Uriel Feige David Peleg Prabhakar Raghavan and Eli Upfal. 1990. Randomized Broadcast in Networks. (1990) 128--137. http:\/\/dl.acm.org\/citation.cfm?id=646475.693450.","DOI":"10.5555\/646475.693450"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886521.1886565"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095246"},{"key":"e_1_2_1_29_1","first-page":"1466","article-title":"The effect of network topology on the spread of epidemics. In INFOCOM (2006-10-04)","volume":"1455","author":"Ganesh Ayalvadi J.","year":"2005","unstructured":"Ayalvadi J. Ganesh, Laurent Massouli, and Donald F. Towsley. 2005. The effect of network topology on the spread of epidemics. In INFOCOM (2006-10-04). IEEE, 1455.1466. http:\/\/dblp.uni-trier.de\/db\/conf\/infocom\/infocom2005.html#GaneshMT05.","journal-title":"IEEE"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2011.57"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095245"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2011.07.015"},{"volume-title":"The theory of branching processes","author":"Harris Theodore E.","key":"e_1_2_1_33_1","unstructured":"Theodore E. Harris. 1963. The theory of branching processes. Springer-Verlag, Berlin. xiv+230 pages."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap"},{"volume-title":"Markov chains and mixing times. Providence","author":"Levin David Asher","key":"e_1_2_1_35_1","unstructured":"David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer. 2009. Markov chains and mixing times. Providence, R.I. American Mathematical Society. http:\/\/opac.inria.fr\/record=b1128575. With a chapter on coupling from the past by James G. Propp and David B. Wilson."},{"volume-title":"Combinatorics, Paul Erd\u0151s is Eighty","author":"Lov\u00e1sz L.","key":"e_1_2_1_36_1","unstructured":"L. Lov\u00e1sz. 1996. Random walks on graphs: A survey. In Combinatorics, Paul Erd\u0151s is Eighty, D. Mikl\u00f3s, V. T. S\u00f3s, and T. Sz\u0151nyi (Eds.). Vol. 2. J\u00e1nos Bolyai Mathematical Society, Budapest, 353--398."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(92)90038-R"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.104.258701"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Daniel Spieman. 2012. Spectral graph theory lecture notes. Available at http:\/\/www.cs.yale.edu\/homes\/spielman\/561.","DOI":"10.1201\/b11644-19"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOP357"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0605030"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-011-0155-y"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1151374.1151386"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2817830","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2817830","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2817830","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:25Z","timestamp":1750225405000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2817830"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,11,2]]}},"alternative-id":["10.1145\/2817830"],"URL":"https:\/\/doi.org\/10.1145\/2817830","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}