The Social Network model

  • Jonathan Hermon | UC Berkeley

At time 0 start several independent lazy simple random walks on a finite or infinite connected graph (for instance, start with 1 walker at each vertex). When two walkers visit the same vertex at the same time they are declared acquaintance. The social connectivity time is defined to be the minimal time in which any two walkers have a path of acquaintances between them. The main result in the finite settings (Joint work with Itai Benjamini and Gady Kozma) is poly-logarithmic bounds on the social connectivity time (when the underlying graph is of bounded degree). As time permits a joint work with Ben Morris, Allan Sly and Chuan Qin in which we study the model on infinite graphs will also be discussed. The main question studied: Is it true that a.s. any two walkers will have a path of acquaintances between them? The answer provides a characterization of amenability.

Speaker Details

Jonathan Hermon is currently a p.h.d student at UC Berkeley (statistics). He wrote a Master’s Thesis at the Weizman Institute with Itai Benjamini as advisor.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks