Rumor Spreading in Random Hyperbolic Graphs.

Abstract: We analyze several variants of the following randomized broadcast algorithm (a.k.a.~rumor spreading process) on Random Hyperbolic Graphs (RHG).  At the beginning, only one node from the giant component (largest connected component) of the RHG is informed. Then, in each round, each informed node chooses a  neighbor uniformly and independently at random and pushes the information to it. We give precise estimates (in terms of the RHG’s parameters) for the number of steps this algorithm takes to inform every node in the giant component of the RHG. Our estimates hold with high probability.

Our results show a large gap between the involved graphs giant component diameter and broadcast time, contrary to the advocated use of RHGs as good models of social networks where folklore as well as some empirical studies suggest rumors spread fast.

We also discuss algorithmic variants where uninformed nodes may pull information from neighbors (both in the case where informed nodes may or may not push information).

Joint work with Dieter Mitsche (U. Jean Monnet, France)

Posted on Aug 10, 2020 in ACGO, Seminars