THE SOCIAL NETWORK MODEL ON INFINITE GRAPHS

• 成果类型: Article
• 署名作者: Hermon, Jonathan; Ben Morris; Qin, Chuan; Sly, Allan
• 署名单位: University of Cambridge; University of California System; University of California Davis; Princeton University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/19-AAP1520
• 发表日期: 2020
• 页码: 902-935
• 关键词: transience; recurrence

摘要

Given an infinite connected regular graph G = (V, E), place at each vertex Poisson(lambda) 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 lambda > 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 lambda(c) (G) > 0. We give general bounds on lambda(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 lambda there exists a finite time t(lambda) (G) such that a.s. there exists an infinite set of walkers having a path of acquaintances between them by time t(lambda)(G).