[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Spreading of Messages in Random Graphs

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds, of the Erdős-Rényi random graph G(n,p). Whenever more than a ρ∈(0,1) fraction of a vertex v’s neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower bounds on the minimum number of initial seeds, \(\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)\), needed to convince a δ∈{1/n,…,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that \(\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)=\Omega(\min\{\delta,\rho\}n)\) with probability 1−n −Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρ n) and (2) \(\mathrm{min\hbox{-}seed}(n,p,\delta,1/2)=\Omega(\delta n/\ln(e/\delta))\) with probability 1−exp (−Ω(δ n))−n −Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Artz, D., Gil, Y.: A survey of trust in computer science and the semantic web. J. Web Semant. Sci. Serv. Agents World Wide Web 5(2), 58–71 (2007)

    Article  Google Scholar 

  2. Berger, E.: Dynamic monopolies of constant size. J. Comb. Theory, Ser. B 83(2), 191–200 (2001)

    Article  MATH  Google Scholar 

  3. Bermond, J.-C., Bond, J., Peleg, D., Perennes, S.: The power of small coalitions in graphs. Discrete Appl. Math. 127(3), 399–414 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bollobás, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001)

    MATH  Google Scholar 

  5. Chang, C.-L., Lyuu, Y.-D.: Spreading messages. Theor. Comput. Sci. 410(27–29), 2714–2724 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  6. Chernoff, H.: A measure of the asymptotic efficiency of tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493–507 (1952)

    Article  MATH  MathSciNet  Google Scholar 

  7. Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 773–781 (2008)

  8. Flocchini, P., Geurts, F., Santoro, N.: Optimal irreversible dynamos in chordal rings. Discrete Appl. Math. 113(1), 23–42 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  9. Flocchini, P., Královič, R., Ružička, P., Roncato, A., Santoro, N.: On time versus size for monotone dynamic monopolies in regular topologies. J. Discrete Algorithms 1(2), 129–150 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  10. Flocchini, P., Lodi, E., Luccio, F., Pagli, L., Santoro, N.: Dynamic monopolies in tori. Discrete Appl. Math. 137(2), 197–212 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  11. Gleeson, J.P., Cahalane, D.J.: Seed size strongly affects cascades on random networks. Phys. Rev. E 75, 056103 (2007)

    Article  Google Scholar 

  12. Grandison, T., Sloman, M.: A survey of trust in Internet applications. IEEE Commun. Surv. Tutor. 3(4), 2–16 (2000)

    Article  Google Scholar 

  13. Guha, R., Kumar, R., Raghavan, P., Tomkins, A.: Propagation of trust and distrust. In: Proceedings of the 13th International World Wide Web Conference, pp. 403–412 (2004)

  14. Haykin, S.: Neural Networks: A Comprehensive Foundation, 2nd edn. Prentice Hall, New York (1998)

    Google Scholar 

  15. Hedetniemi, S.T., Hedetniemi, S.M., Liestman, A.L.: A survey of broadcasting and gossiping in communication networks. Networks 18(4), 319–349 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  16. Hromkovic, J., Klasing, R., Monien, B., Peine, R.: Dissemination of information in interconnection networks (broadcasting and gossiping). In: Du, D.-Z., Hsu, D.F. (eds.) Combinatorial Network Theory, pp. 125–212. Kluwer Academic, Norwell (1996)

    Google Scholar 

  17. Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, pp. 565–574 (2000)

  18. Linial, N., Peleg, D., Rabinovich, Y., Saks, M.: Sphere packing and local majorities in graphs. In: Proceedings of the 2nd Israel Symposium on Theory of Computing Systems, pp. 141–149 (1993)

  19. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)

    MATH  Google Scholar 

  20. Peleg, D.: Graph immunity against local influence. Technical Report CS96-11 (1996)

  21. Peleg, D.: Size bounds for dynamic monopolies. Discrete Appl. Math. 86(2–3), 263–273 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  22. Peleg, D.: Local majorities, coalitions and monopolies in graphs: a review. Theor. Comput. Sci. 282(2), 231–257 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  23. Rudin, W.: Principles of Mathematical Analysis, 3rd edn. McGraw-Hill, New York (1976)

    MATH  Google Scholar 

  24. Schelling, T.C.: Hockey helmets, concealed weapons, and daylight saving: a study of binary choices with externalities. J. Confl. Res. 17(3), 381–428 (1973)

    Article  Google Scholar 

  25. Watts, D.J.: A simple model of global cascades on random networks. Proc. Nat. Acad. Sci. 99(9), 5766–5771 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  26. West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, New York (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Information Engineering, National Taiwan University, No. 1, Sec. 4, Roosevelt Rd., Da-an District, Taipei, 10617, Taiwan

    Ching-Lueh Chang

  2. Department of Computer Science and Information Engineering & Department of Finance, National Taiwan University, Taipei, Taiwan

    Yuh-Dauh Lyuu

Authors
  1. Ching-Lueh Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuh-Dauh Lyuu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ching-Lueh Chang.

Additional information

The authors are supported in part by the National Science Council of Taiwan under grant 97-2221-E-002-096-MY3 and Excellent Research Projects of National Taiwan University under grant 98R0062-05.

The authors are grateful to the anonymous reviewers for their comments and suggestions.

A preliminary version of this paper is presented at the 15th Computing: the Australasian Theory Symposium (CATS 2009), Wellington, New Zealand.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chang, CL., Lyuu, YD. Spreading of Messages in Random Graphs. Theory Comput Syst 48, 389–401 (2011). https://doi.org/10.1007/s00224-010-9258-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-010-9258-7

Keywords

Search

Navigation