Probabilistic analysis of rumor-spreading time

摘要

Randomized rumor spreading is a well-established mechanism in the dissemination of information in complex large networks through pairwise interactions. After the approach was proposed by Demers et al. (Ref. 1) this has been adapted in many applications such as resource recovery, data aggregation and virus propagation in computer networks. Many studies have been undertaken on rumor-spreading algorithms where a rumor placed in a node is propagated to all nodes through pairwise interactions. One important aspect is the time taken to spread the rumor in all the nodes. Several models have been used by various studies to derive the time for dissemination. The most studied model is the synchronous push-pull model. This model assumes that all nodes in the network are in synchrony which facilitates the algorithms to divide time in synchronized rounds. In each round, node i sends the rumor to a random neighbor j if i knows it (push operation), or receives it from j if j knows it (pull operation). The spreading time of the rumor is the number of synchronous rounds required for all nodes to know the rumor. Recently it has been shown that the rumor spreading time is closely related to the conductance graph of the network. Investigations have been carried out for the time to spread the rumor in different types of topologies. However, the assumption that all nodes synchronously act is not realistic. Many studies have been conducted by dropping this assumption for different types of network topologies. In Mocquard et al. (Ref. 2), the rumor spreading is analyzed in a discrete-time, asynchronous push-pull model. This article extends the results of the above study by proving the conjecture therein with a continuous-time asynchronous push-pull model.