Rapid social connectivity

DOI10.1214/19-EJP294zbMATH Open1419.82053arXiv1608.07621OpenAlexW2510986799MaRDI QIDQ2631858FDOQ2631858

Authors: Itai Benjamini, Jonathan Hermon 

Publication date: 16 May 2019

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

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.

Full work available at URL: https://arxiv.org/abs/1608.07621

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Balls and bins: A study in negative dependence
• Recurrence and transience for the frog model on trees
• Phase transition for the frog model
• The shape theorem for the frog model
• Branching and tree indexed random walks on fractals
• Frogs in random environment
• The spread of a rumor or infection in a moving population
• A shape theorem for the spread of an infection
• Percolation on finite graphs and isoperimetric inequalities.
• On an epidemic model on finite graphs
• 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
• The exclusion process mixes (almost) faster than independent particles
• Sensitivity of mixing times in Eulerian digraphs
• Frogs on trees?
• The social network model on infinite graphs

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)