Rapid social connectivity. (English) Zbl 1419.82053

Authors’ abstract: Given a graph \(G=(V,E)\), consider Poisson (\(|V|\)) walkers performing independent lazy simple random walks on \(G\) simultaneously, where the initial position of each walker is chosen independently with probability proportional to the degrees. When two walkers visit the same vertex at the same time, they are declared to be acquainted. The social connectivity time \(\text{SC} (G)\) is defined as the first time in which there is a path of acquaintances between every pair of walkers. It is shown that, when the average degree of \(G\) is \(d\), with high probability \[ c\log |V| \le \text{SC} (G) \le C d^{1+5 \cdot 1_{G \text{ is not regular}}} \log ^3 |V|. \] When \(G\) is regular, the lower bound is improved to \(\text{SC} (G) \ge \log |V| -6 \log \log |V| \), with high probability. We determine \(\text{SC} (G)\) up to a constant factor in the cases that \(G\) is an expander and when it is the \(n\)-cycle.


82C41 Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics
60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
05C81 Random walks on graphs
91D30 Social networks; opinion dynamics
Full Text: DOI arXiv Euclid


[1] David Aldous and Jim Fill, Reversible Markov chains and random walks on graphs, 2002, Unfinished manuscript. Available at http://www.stat.berkeley.edu/ aldous/RWG/book.html.
[2] Noga Alon, Itai Benjamini, and Alan Stacey, Percolation on finite graphs and isoperimetric inequalities, Ann. Probab. 32 (2004), no. 3A, 1727-1745. · Zbl 1046.05071
[3] O. S. M. Alves, F. P. Machado, and S. Yu. Popov, Phase transition for the frog model, Electron. J. Probab. 7 (2002), no. 16, 21. · Zbl 1012.60081
[4] O. S. M. Alves, F. P. Machado, and S. Yu. Popov, The shape theorem for the frog model, Ann. Appl. Probab. 12 (2002), no. 2, 533-546. · Zbl 1013.60081
[5] Itai Benjamini, Luiz Renato Fontes, Jonathan Hermon, and Fabio Pabio Machado, On an epidemic model on finite graphs, Arxiv preprint arXiv:1610.04301 (2016).
[6] Lucas Boczkowski, Yuval Peres, and Perla Sousi, Sensitivity of mixing times in Eulerian digraphs, SIAM J. Discrete Math. 32 (2018), no. 1, 624-655. · Zbl 1390.05219
[7] Devdatt Dubhashi and Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures Algorithms 13 (1998), no. 2, 99-124. · Zbl 0964.60503
[8] Sharad Goel, Ravi Montenegro, and Prasad Tetali, Mixing time bounds via the spectral profile, Electron. J. Probab. 11 (2006), no. 1, 1-26. · Zbl 1109.60061
[9] Jonathan Hermon, Frogs on trees?, Electron. J. Probab. 23 (2018), Paper No. 17, 40. · Zbl 1390.60351
[10] Jonathan Hermon, Ben Morris, Chuan Qin, and Allan Sly, The social network model on infinite graphs, Arxiv preprint arXiv:1610.04293 (2016).
[11] Jonathan Hermon and Richard Pymar, The exclusion process mixes (almost) faster than independent particles, arXiv preprint arXiv:1808.10846 (2018).
[12] Christopher Hoffman, Tobias Johnson, and Matthew Junge, Recurrence and transience for the frog model on trees, Ann. Probab. 45 (2017), no. 5, 2826-2854. · Zbl 1385.60058
[13] Olav Kallenberg, Foundations of modern probability, second ed., Probability and its Applications (New York), Springer-Verlag, New York, 2002. · Zbl 0996.60001
[14] Harry Kesten and Vladas Sidoravicius, The spread of a rumor or infection in a moving population, Ann. Probab. 33 (2005), no. 6, 2402-2462. · Zbl 1111.60074
[15] Harry Kesten and Vladas Sidoravicius, A shape theorem for the spread of an infection, Ann. of Math. 167 (2008), no. 3, 701-766. · Zbl 1202.92077
[16] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov chains and mixing times, American Mathematical Society, Providence, RI, 2017, Second edition of [MR2466937], With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson. · Zbl 1390.60001
[17] S. Yu. Popov, Frogs in random environment, J. Statist. Phys. 102 (2001), no. 1-2, 191-201. · Zbl 0972.60101
[18] András Telcs and Nicholas C. Wormald, Branching and tree indexed random walks on fractals, J. Appl. Probab. 36 (1999), no. 4, 999-1011. · Zbl 0967.60059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.