Rumor propagation on a spread-out lattice graph

Faculty Member
Partha Dey

We consider the simplest rumor propagation model, where an agent passes the rumor to one of its neighbors (chosen uniformly at random) according to its Poisson clock, independent of each other. For the base graph, we take the spread-out version of the d-dimensional lattice box of side length n. Given a positive integer L, in the L spread-out version, all vertices within distance L are connected to each other. When L = n*d, the graph becomes the complete graph, whereas, for L=1, we get the usual lattice graph. We aim to understand the first-passage time needed for the rumor to propagate from one corner to the other and how it depends on L for large n in d = 1 or 2 dimensions. In general, for L=1, the time needed is of order n, whereas for L=n*d, the time needed is of order log(n)/n. We want to find the threshold on L as a function of n and d when the time needed changes from large to small. If time permits, we will use simulation to understand the distributional limit for the passage time.

Team Meetings
Project Difficulty
Undergrad Prerequisites

Math 416 and 461. Some knowledge of algorithms is required for simulation. Python programming language will be used for simulation.