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. 17

 

Conclusion

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 next.

 

References

1. albert, r., Jeong, H., and barabási, a.-l. diameter of the World-Wide Web. Nature 401 (sept. 1999), 130–131.

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, 2011); http://www.guardian.co.uk/world/2011/feb/25/ twitter-facebook-uprisings-arab-libya

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. mpi-sws.org

7. bohman, t. and Frieze, a. M. Hamilton cycles in 3-out. Random Structures & Algorithms 35, 4 (2009), 393–417.

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
members within
only eight rounds
of communication.

classical random graphs. Internet Mathematics 1, 2 (2003), 215–225.

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 (2001), 279–290.

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), 261–270.

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, 1999, 639–650.

23. leskovec, J. stanford large network dataset Collection; http://snap.stanford.edu/data/

24. Mihail, M. Papadimitriou, C., and saberi, a. on certain connectivity properties of the Internet topology. Journal of Computer and System Sciences 72, 2 (2006), 239–251.

25. Milgram, s. the small-world program. Psychology Today 2 (1967), 60–67.

 

Benjamin Doerr ( [e-mail]) 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 ( [e-mail]) 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, Germany. Tobias Friedrich ( [e-mail]) 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, saarbrücken, Germany.

© 2012 aCM 0001-0782/12/06 $10.00