Rapid social connectivity

DOI10.1214/19-EJP294MaRDI QIDQ2631858zbMATH OpenOpenAlexFDO

Authors Itai Benjamini, Jonathan Hermon

Publication date 16 May 2019

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.07621, https://projecteuclid.org/euclid.ejp/1554775411

zbMATH Keywords

social networkrandom walksgiant componentcoalescence process

Mathematics Subject Classification ID

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

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 $mathrmSC(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 [ clog |V| le mathrm{SC}(G) le C d^{1+5 cdot 1_{G ext{ is not regular}} } log^3 |V|.] When $G$ is regular the lower bound is improved to $mathrmSC(G)gelog|V|-6loglog|V|$, with high probability. We determine $mathrmSC(G)$ up to a constant factor in the cases that $G$ is an expander and when it is the $n$-cycle.

Recommendations

• FAST INFORMATION PROPAGATION IN SOCIAL NETWORKS
• Rapid innovation diffusion in social networks
• Connectivity
• Ultra-fast rumor spreading in social networks

Cites work

• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• A shape theorem for the spread of an infection
• Balls and bins: A study in negative dependence
• Branching and tree indexed random walks on fractals
• Frogs in random environment
• Frogs on trees?
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing time bounds via the spectral profile
• On an epidemic model on finite graphs
• Percolation on finite graphs and isoperimetric inequalities.
• Phase transition for the frog model
• Recurrence and transience for the frog model on trees
• Sensitivity of mixing times in Eulerian digraphs
• The exclusion process mixes (almost) faster than independent particles
• The shape theorem for the frog model
• The social network model on infinite graphs
• The spread of a rumor or infection in a moving population

Cited in

(7)

• On an epidemic model on finite graphs
• Acquaintance time of random graphs near connectivity threshold
• Frogs on trees?
• The social network model on infinite graphs
• The exclusion process mixes (almost) faster than independent particles
• Cover time for the frog model on trees
• Acquaintance time of a graph

This page was built for publication: Rapid social connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2631858)