Repository logo
 

Rapid social connectivity

Published version
Peer-reviewed

Type

Article

Change log

Authors

Benjamini, I 

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 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 clog|V| ≤ SC(G)≤Cd1+5⋅1G is not regular log3|V|. When G is regular the lower bound is improved to SC(G) ≥ log|V| - 6 log log|V|, with high probability. We determine SC(G) up to a constant factor in the cases that G is an expander and when it is the n-cycle.

Description

Keywords

social network, random walks, giant component, coalescence process

Journal Title

Electronic Journal of Probability

Conference Name

Journal ISSN

1083-6489
1083-6489

Volume Title

24

Publisher

Institute of Mathematical Statistics
Sponsorship
J. Hermon is financially supported by the EPSRC grant EP/L018896/1