The Social Network Model on Infinite Graphs

Jonathan Hermon, Ben Morris, Chuan Qin, Allan Sly

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Given an infinite connected regular graph G = (V ,E), place at each vertex Poisson(λ) walkers performing independent lazy simple random walks on G simultaneously. When two walkers visit the same vertex at the same time they are declared to be acquainted. We show that when G is vertex-transitive and amenable, for all λ > 0 a.s. any pair of walkers will eventually have a path of acquaintances between them. In contrast, we show that when G is nonamenable (not necessarily transitive) there is always a phase transition at some λc(G) > 0.We give general bounds on λc(G) and study the case that G is the d-regular tree in more detail. Finally, we show that in the nonamenable setup, for every λ there exists a finite time tλ(G) such that a.s. there exists an infinite set of walkers having a path of acquaintances between them by time tλ(G).

Original languageEnglish (US)
Pages (from-to)902-935
Number of pages34
JournalAnnals of Applied Probability
Issue number2
StatePublished - Apr 2020

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


  • Amenability
  • Infinite cluster
  • Percolation
  • Phase transition
  • Random walks
  • Social network


Dive into the research topics of 'The Social Network Model on Infinite Graphs'. Together they form a unique fingerprint.

Cite this