Some centers with many connections share with many people with few connections. Figures 2 and 3 show how a rumor started in a random node spreads in graphs corresponding to the social networks Orkut and Twitter. For AR plots, it is easy to see that the diameter is of the order log (n), which is also clearly a lower limit for rumor propagation time. We support this empirical finding through mathematical analysis, demonstrating that the rumor spreading process spreads news in sublogarithmic time, or as long as it takes to inform all nodes, as well as any constant fraction (such as 1%, 10% or 50%).
Theorem 1 showed for the first time (in 2001) that the spread of rumors on the PA charts is much faster than for the other network topologies covered so far. This is substantially different from the probabilistic model of virus spread5, in which the probability of becoming infected is proportional to the number of infected neighbors. We simulate a natural process of spreading rumors on various graphs representing real-world social networks and various classic network topologies. We support this finding by analyzing information dissemination in the mathematically defined preferential connection network (PA) topology, a common model for real-world networks, which demonstrates that sublogarithmic time is sufficient to spread news to all nodes of a network.
For simplicity, as in most previous works, the rumor propagation process is synchronized; that is, it takes place at discrete points over time and at each time step, with each node contacting a neighbor to exchange information.