Skip to main content
SpringerLink
Log in

Seeds Buffering for Information Spreading Processes

  • Conference paper
  • First Online:
Social Informatics (SocInfo 2017)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 10539))

Included in the following conference series:

Abstract

Seeding strategies for influence maximization in social networks have been studied for more than a decade. They have mainly relied on the activation of all resources (seeds) simultaneously in the beginning; yet, it has been shown that sequential seeding strategies are commonly better. This research focuses on studying sequential seeding with buffering, which is an extension to basic sequential seeding concept. The proposed method avoids choosing nodes that will be activated through the natural diffusion process, which is leading to better use of the budget for activating seed nodes in the social influence process. This approach was compared with sequential seeding without buffering and single stage seeding. The results on both real and artificial social networks confirm that the buffer-based consecutive seeding is a good trade-off between the final coverage and the time to reach it. It performs significantly better than its rivals for a fixed budget. The gain is obtained by dynamic rankings and the ability to detect network areas with nodes that are not yet activated and have high potential of activating their neighbours.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.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

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 39.99
Price excludes VAT (USA)
Softcover Book
USD 54.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Adamic, L.A., Glance, N.: The political blogosphere and the 2004 US election: divided they blog. In: Proceedings of the 3rd International Workshop on Link discovery, pp. 36–43. ACM (2005)

    Google Scholar 

  2. Bulut, E., Wang, Z., Szymanski, B.: Cost-effective multiperiod spraying for routing in delay-tolerant networks. IEEE/ACM Trans. Netw. 18(5), 1530–1543 (2010)

    Article  Google Scholar 

  3. Ghosh, B.K., Sen, P.K. (eds.): Handbook of sequential analysis. In: Statistics, Textbooks and Monographs. Marcel Dekker, New York (1991)

    Google Scholar 

  4. Jakab, G.J.: Sequential virus infections, bacterial superinfections, and fibrogenesis. Am. Rev. Respir. Dis. 142(2), 374–9 (1990)

    Article  Google Scholar 

  5. Granovetter, M.: Threshold models of collective behavior. Am. J. Sociol. 83(6), 1420–1443 (1978)

    Article  Google Scholar 

  6. Horel, T., Singer, Y.: Scalable methods for adaptively seeding a social network. In: Proceedings of the 24th International Conference on World Wide Web, pp. 441–451. ACM (2015)

    Google Scholar 

  7. Jankowski, J., Bródka, P., Kazienko, P., Szymanski, B., Michalski, R., Kajdanowicz, T.: Balancing speed and coverage by sequential seeding in complex networks. arXiv preprint (2016). arXiv:1609.07526

  8. Jankowski, J., Kozielski, M., Filipowski, W., Michalski, R.: The diffusion of viral content in multi-layered social networks. In: Bǎdicǎ, C., Nguyen, N.T., Brezovan, M. (eds.) ICCCI 2013. LNCS, vol. 8083, pp. 30–39. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40495-5_4

    Chapter  Google Scholar 

  9. Jankowski, J., Michalski, R., Kazienko, P.: Compensatory seeding in networks with varying availability of nodes. In: The 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining - ASONAM 2013, pp. 1242–1249. IEEE (2013)

    Google Scholar 

  10. Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2003, pp. 137–146. ACM, New York (2003)

    Google Scholar 

  11. Kempe, D., Kleinberg, J.M., Tardos, É.: Maximizing the spread of influence through a social network. Theory Comput. 11(4), 105–147 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Kitsak, M., Gallos, L.K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H.E., Makse, H.A.: Identification of influential spreaders in complex networks. Nat. Phys. 6(11), 888–893 (2010)

    Article  Google Scholar 

  13. Kumar, A., Lifson, J.D., Li, Z., Jia, F., Mukherjee, S., Adany, I., Liu, Z., Piatak, M., Sheffer, D., McClure, H.M., Narayan, O.: Sequential immunization of macaques with two differentially attenuated vaccines induced long-term virus-specific immune responses and conferred protection against AIDS caused by heterologous simian human immunodeficiency virus (shiv89.6p). Virology 279(1), 241–256 (2001)

    Article  Google Scholar 

  14. de Lange, F.P., Jensen, O., Dehaene, S.: Accumulation of evidence during sequential decision making: the importance of top-down factors. J. Neurosci.: Off. J. Soc. Neurosci. 30(2), 731–738 (2010)

    Article  Google Scholar 

  15. Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. In: Proceedings of the SIGCHI conference on human factors in computing systems, pp. 1361–1370. ACM (2010)

    Google Scholar 

  16. Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: densification and shrinking diameters. ACM Trans. Knowl. Discov. Data (TKDD) 1(1), 2 (2007)

    Article  Google Scholar 

  17. Leskovec, J., Mcauley, J.J.: Learning to discover social circles in ego networks. In: Advances in Neural Information Processing Systems, pp. 539–547 (2012)

    Google Scholar 

  18. Liu-Thompkins, Y.: Seeding viral content : the role of message and network factors (2012)

    Google Scholar 

  19. Michalski, R., Kajdanowicz, T., Bródka, P., Kazienko, P.: Seed selection for spread of influence in social networks: temporal vs. static approach. New Gener. Comput. 32(3–4), 213–235 (2014)

    Article  Google Scholar 

  20. Michalski, R., Kazienko, P.: Maximizing social influence in real-world networks—the state of the art and current challenges. In: Król, D., Fay, D., Gabryś, B. (eds.) Propagation Phenomena in Real World Networks. ISRL, vol. 85, pp. 329–359. Springer, Cham (2015). doi:10.1007/978-3-319-15916-4_14

    Google Scholar 

  21. Morone, F., Makse, H.A.: Influence maximization in complex networks through optimal percolation. Nature 524(7563), 65–68 (2015)

    Article  Google Scholar 

  22. Newman, M.E.: The structure of scientific collaboration networks. Proc. Nat. Acad. Sci. 98(2), 404–409 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  23. Newman, M.E.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74(3), 036104 (2006)

    Article  MathSciNet  Google Scholar 

  24. Opsahl, T.: Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Soc. Netw. 35(2), 159–167 (2013)

    Article  Google Scholar 

  25. Opsahl, T., Panzarasa, P.: Clustering in weighted networks. Soc. Netw. 31(2), 155–163 (2009)

    Article  Google Scholar 

  26. Price, W.H.: Sequential immunization as a vaccination procedure against dengue viruses. Am. J. Epidemiol. 88(3), 392–397 (1968)

    Article  Google Scholar 

  27. Seeman, L., Singer, Y.: Adaptive seeding in social networks. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 459–468. IEEE (2013)

    Google Scholar 

  28. Sela, A., Ben-Gal, I., Pentland, A., Shmueli, E.: Improving information spread through a scheduled seeding approach. In: The international conference on Advances in Social Network Analysis and Mining 2015 (2015)

    Google Scholar 

  29. Siegmund, D.: Sequential Analysis : Tests and Confidence Intervals. Springer Series in Statistics. Springer-Verlag, New York (1985)

    Book  MATH  Google Scholar 

  30. Sridhar, S., Mantrala, M.K., Naik, P.A., Thorson, E.: Dynamic marketing budgeting for platform firms: theory, evidence, and application. J. Mark. Res. 48(6), 929–943 (2011)

    Article  Google Scholar 

  31. Wald, A.: Sequential Analysis. Wiley, Hoboken (1947)

    MATH  Google Scholar 

  32. Wang, C., Chen, W., Wang, Y.: Scalable influence maximization for independent cascade model in large-scale social networks. Data Min. Knowl. Discov. 25(3), 545–576 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  33. Watts, D.J., Strogatz, S.H.: Collective dynamics of small-worldnetworks. Nature 393(6684), 440–442 (1998)

    Article  MATH  Google Scholar 

  34. Zhang, H., Procaccia, A.D., Vorobeychik, Y.: Dynamic influence maximization under increasing returns to scale. In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pp. 949–957. International Foundation for Autonomous Agents and Multiagent Systems (2015)

    Google Scholar 

  35. Zhang, J.X., Duan-Bing Chen, Q.D., Zhao, Z.D.: Identifying a set of influential spreaders in complex networks. Sci. Rep. 6 (2016)

    Google Scholar 

Download references

Acknowledgments

This work was partially supported by Wrocław University of Science and Technology statutory funds (PB) and by the National Science Centre, Poland, project nos. 2015/17/D/ST6/04046 (RM), 2016/21/B/ST6/01463 (PK), 2013/09/B/ST6/02317 and 2016/21/B/HS4/01562 (JJ); by European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant no. 691152 (RENOIR); by the Polish Ministry of Science and Higher Education fund for supporting internationally co-financed projects in 2016–2019, no. 3628/H2020/2016/2.

Author information

Authors and Affiliations

  1. Faculty of Computer Science for Information Technology, West Pomeranian University of Technology, Szczecin, Poland

    Jarosław Jankowski

  2. Department of Computational Intelligence, Wrocław University of Science and Technology, Wrocław, Poland

    Piotr Bródka, Radosław Michalski & Przemysław Kazienko

Authors
  1. Jarosław Jankowski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Piotr Bródka
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Radosław Michalski
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Przemysław Kazienko
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jarosław Jankowski .

Editor information

Editors and Affiliations

  1. Indiana University, Bloomington, Indiana, USA

    Giovanni Luca Ciampaglia

  2. University of Washington, Seattle, Washington, USA

    Afra Mashhadi

  3. University of Oxford, Oxford, United Kingdom

    Taha Yasseri

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Jankowski, J., Bródka, P., Michalski, R., Kazienko, P. (2017). Seeds Buffering for Information Spreading Processes. In: Ciampaglia, G., Mashhadi, A., Yasseri, T. (eds) Social Informatics. SocInfo 2017. Lecture Notes in Computer Science(), vol 10539. Springer, Cham. https://doi.org/10.1007/978-3-319-67217-5_37

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-67217-5_37

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-67216-8

  • Online ISBN: 978-3-319-67217-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation