Better Bounds for Coalescing-Branching Random Walks
Abstract
Coalescing-branching random walks, or cobra walks for short, are a natural variant of random walks on graphs that can model the spread of disease through contacts or the spread of information in networks. In a k -cobra walk, at each timestep, a subset of the vertices are active; each active vertex chooses k random neighbors (sampled independently and uniformly with replacement) that become active at the next step, and these are the only active vertices at the next step. A natural quantity to study for cobra walks is the cover time, which corresponds to the expected time when all nodes have become infected or received the disseminated information.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 31, 2018
- Source ID
- 10.1145/3209688
Entities
People
- Michael Mitzenmacher
- Rajmohan Rajaraman
- Scott Roche
Organizations
- Akamai Technologies
- Harvard University
- National Science Foundation
- Northeastern University
- Office of Naval Research