popular nodes are informed, a symmetric argument can show that after
another O(log(n)3/4 log(log(n))) rounds,
the remaining small-degree nodes,
mostly by calling more popular nodes,
would all be informed; for more, see
Doerr et al.
We simulated a natural rumor-spreading process on various graphs representing real-world social networks
and several classical network topologies. We also performed a mathematical analysis of the process in PA
graphs. Simulation and analysis both
demonstrate the speediness of rumor
spreading in social networks.
A key observation in the mathematical proof, as well as being a good
explanation for this phenomenon, is
that small-degree nodes learn a rumor
once one of their neighbors knows it,
then quickly forward it to their neighbors. This propagation scheme facilitates sending rumors from one large-degree node to another.
How does this play out in everyday
life? It partially explains why social
networks are observed to spread information quickly, even though the
process is not organized centrally,
and the network is not designed in
an intelligent way. Crucial is fruitful
interaction between hubs with many
connections and average users with
few friends. Hubs make the news
available to a big audience, whereas
average users quickly convey the information from one neighbor to the
1. albert, r., Jeong, H., and barabási, a.-l. diameter
of the World-Wide Web. Nature 401 (sept. 1999),
2. barabási, a.-l. Linked: How Everything Is Connected
to Everything Else and What It Means. Plume, 2003.
3. barabási, a.-l. and albert, r. emergence of scaling in
random networks. Science 286 (oct. 1999), 509–512.
4. beaumont, P. the truth about twitter, Facebook, and
the uprisings in the arab world. The Guardian (Feb. 25,
5. berger, n., borgs, C., Chayes, J.t., and saberi, a. on
the spread of viruses on the Internet. In Proceedings
of the 16th ACM-SIAM Symposium on Discrete
Algorithms (Vancouver, b.C., 2005), 301–310.
6. bhattacharjee, b., druschel, P., Gummadi, k. et al.
online social net works research the Max Planck
Institute for software systems; http://socialnetworks.
7. bohman, t. and Frieze, a. M. Hamilton cycles in 3-out.
Random Structures & Algorithms 35, 4 (2009),
8. bollobás, b and riordan, o. robustness and
vulnerability of scale-free random graphs. Internet
Mathematics 1, 1 (2003), 1–35.
9. bollobás, b and riordan, o. Coupling scale-free and
A rumor begun at
a random node of
the Twitter network
reaches on average
45. 6 million of the
total of 51. 2 million
only eight rounds
classical random graphs. Internet Mathematics 1, 2
10. bollobás, b and riordan, o. the diameter of a scale-free random graph. Combinatorica 24, 1 (2004), 5–34.
11. bollobás, b., riordan, o., spencer, J., and tusnády, G.
the degree sequence of a scale- free random graph
process. Random Structures & Algorithms 18, 3
12. boyd, s.P., Ghosh, a., Prabhakar, b., and shah, d.
randomized gossip algorithms. IEEE Transactions on
Information Theory 52, 6 (2006), 2508–2530.
13. broder, a., kumar, r., Maghoul, F., raghavan, P.,
rajagopalan, s., stata, r., tomkins, a., and Wiener, J.
Graph structure in the Web. Computer Networks 33,
1–6 (2000), 309–320.
14. Chierichetti, F., lattanzi, s., and Panconesi, a. rumor
spreading in social networks. Theoretical Computer
Science 412, 24 (2011), 2602–2610.
15. Cooper, C., Frieze, a.M., and Vera, J. random deletion
in a scale-free random graph process. Internet
Mathematics 1, 4 (2004), 463–483.
16. demers, a.J., Greene, d.H., Hauser, C., Irish, W.,
larson, J., shenker, s., sturgis, H.e., swinehart, d.C.,
and terry, d.b. epidemic algorithms for replicated
database maintenance. Operating Systems Review 22,
1 (1988), 8–32.
17. doerr, b., Fouz, M., and Friedrich, t. social networks
spread rumors in sublogarithmic time. In Proceedings
of the 43rd ACM Symposium on Theory of Computing
(san Jose, Ca). aCM Press, new york, 2011, 21–30.
18. Flaxman, a.d., Frieze, a.M., and Vera, J. adversarial
deletion in a scale-free random graph process.
Combinatorics, Probability & Computing 16, 2 (2007),
19. Fountoulakis, n., Huber, a., and Panagiotou, k. reliable
broadcasting in random networks and the effect of
density. In Proceedings of the IEEE Conference on
Computer Communications (san diego, Mar. 15–19).
Ieee Press, 2010, 2552–2560.
20. karp, r., schindelhauer, C., shenker, s., and Vöcking, b.
randomized rumor spreading. In Proceedings of the
41st IEEE Symposium on Foundations of Computer
Science (redondo beach, Ca, nov. 12–14). Ieee
Computer society Press, 2000, 565–574.
21. kempe, d., dobra, a., and Gehrke, J. Gossip-based
computation of aggregate information. In Proceedings
of the 44th IEEE Symposium on Foundations of
Computer Science (Cambridge, Ma, oct. 11–14). Ieee
Computer society Press, 2003, 482–491.
22. kumar, s.r., raghavan, P., rajagopalan, s., and
tomkins, a. extracting large-scale knowledge
bases from the Web. In Proceedings of the 25th
International Conference on Very Large Data Bases
(edinburgh, scotland, sept. 7–10). Morgan kaufmann,
23. leskovec, J. stanford large network dataset
24. Mihail, M. Papadimitriou, C., and saberi, a. on certain
connectivity properties of the Internet topology.
Journal of Computer and System Sciences 72, 2
25. Milgram, s. the small-world program. Psychology
Today 2 (1967), 60–67.
Benjamin Doerr ( email@example.com) is a senior
researcher in the department of algorithms and
Complexity at Max-Planck-Institut für Informatik,
saarbrücken, Germany, and an adjunct professor at
saarland university, saarbrücken, Germany.
Mahmoud Fouz ( firstname.lastname@example.org)
is a managing director of rocket Internet, dubai, u.a.e.;
this work was done while he was a Ph.d. student in the
Computational Complexity group of the department of
Computer science at saarland university, saarbrücken,
Tobias Friedrich ( email@example.com) is an
independent research group leader in the Cluster of
excellence on Multimodal Computing and Interaction
at saarland university, saarbrücken, Germany, and
a senior researcher in the department of algorithms
and Complexity at Max-Planck-Institut für Informatik,
© 2012 aCM 0001-0782/12/06 $10.00