Skip to main content
SpringerLink
Log in

Robustness of Influence Maximization Against Non-adversarial Perturbations

  • Chapter
  • First Online:
Influence and Behavior Analysis in Social Networks and Social Media (ASONAM 2018)

Part of the book series: Lecture Notes in Social Networks ((LNSN))

Abstract

Influence maximization problem has been extensively studied. Given a social network, an influence maximization algorithm aims to find a set of influential (seed) nodes in the network such that the expected number of nodes influenced by the seed nodes is maximized under the given cascade model. Most influence maximization algorithms proposed in the literature assume that ground-truth influence spread probabilities between nodes are available. In reality, however, it is natural to assume that there exists a deviation of the influence spread probability used in the influence maximization algorithms from actual influence spread probability. In this paper, we examine the robustness of existing influence maximization algorithms against non-adversarial perturbations in influence spread probabilities. Existing work has investigated the worst-case effectiveness of influence maximization algorithms subject to adversarial perturbations. In contrast, we consider three types of non-adversarial perturbations and investigate the effectiveness of influence maximization algorithms for finding influential nodes in a more relaxed scenario. Our results show that, even in the context of non-adversarial perturbations, the effectiveness of the state-of-the-art approximation and heuristic algorithms may be significantly degraded and lightweight heuristic algorithms can outperform state-of-the-art algorithms when the perturbations are large.

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
$34.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)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 64.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 84.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. A. Adiga, C. Kuhlman, H. Mortveit, A.K.S. Vullikanti, Sensitivity of diffusion dynamics to network uncertainty, in Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI’13) (2013), pp. 2–8

    Google Scholar 

  2. C. Budak, D. Agrawal, A. El Abbadi, Limiting the spread of misinformation in social networks, in Proceedings of the 20th International Conference on World Wide Web (WWW’11), March 2011, pp. 665–674

    Google Scholar 

  3. W. Chen, Y. Wang, S. Yang, Efficient influence maximization in social networks, in Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’09), June 2009, pp. 199–208

    Google Scholar 

  4. W. Chen, C. Wang, Y. Wang, Scalable influence maximization for prevalent viral marketing in large scale social networks, in Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’10) July, 2010, pp. 1029–1038

    Google Scholar 

  5. W. Chen, W. Lu, N. Zhang, Time-critical influence maximization in social networks with time-delayed diffusion process, in Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI’12), July 2012, pp. 592–598

    Google Scholar 

  6. E. Cohen, D. Delling, T. Pajor, R.F. Werneck, Sketch-based influence maximization and computation: scaling up with guarantees, in Proceedings of the 23rd ACM International Conference on Information and Knowledge Management (CIKM’14), July 2014, pp. 629–638

    Google Scholar 

  7. H. Daneshmand, M. Gomez-Rodriguez, L. Song, B. Schoelkopf, Estimating diffusion network structures: recovery conditions, sample complexity & soft-thresholding algorithm, in Proceedings of the 31st International Conference on Machine Learning (ICML’14) (2014), pp. 793–801

    Google Scholar 

  8. Domingos, P., Richardson, M.: Mining the network value of customers, in Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’01), August 2001, pp. 57–66

    Google Scholar 

  9. M. Gomez-Rodriguez, L. Song, N. Du, H. Zha, B. Schölkopf, Influence estimation and maximization in continuous-time diffusion networks. ACM Trans. Inf. Syst. (TOIS) 34(2), 9:1–9:33 (2016)

    Google Scholar 

  10. A. Goyal, F. Bonchi, L.V. Lakshmanan, Learning influence probabilities in social networks, in Proceedings of the 3rd ACM International Conference on Web Search and Data Mining (WSDM’10), February 2010, pp. 241–250

    Google Scholar 

  11. A. Goyal, F. Bonchi, L.V. Lakshmanan, A data-based approach to social influence maximization. Proc. VLDB Endowment 5(1), 73–84 (2011)

    Article  Google Scholar 

  12. A. Goyal, W. Lu, L.V. Lakshmanan, CELF++: optimizing the greedy algorithm for influence maximization in social networks, in Proceedings of the 20th International Conference Companion on World Wide Web (WWW’11), March 2011, pp. 47–48

    Google Scholar 

  13. X. He, D. Kempe, Stability of influence maximization (April 2015). http://arxiv.org/pdf/1501.04579v2.pdf

  14. X. He, D. Kempe, Robust influence maximization, in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’16), August 2016 (ACM, New York, 2016), pp. 885–894

    Google Scholar 

  15. Z. Huiyuan, T.N. Dinh, M.T. Thai, Maximizing the spread of positive influence in online social networks, in Proceedings of the 33rd IEEE International Conference on Distributed Computing Systems (ICDCS’13), July 2013, pp. 317–326

    Google Scholar 

  16. K. Jung, W. Heo, W. Chen, IRIE: scalable and robust influence maximization in social networks, in Proceedings of the 12th IEEE International Conference on Data Mining (ICDM’12), December 2012, pp. 918–923

    Google Scholar 

  17. D. Kempe, J.M. Kleinberg, E. Tardos, Maximizing the spread of influence through a social network, in Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’03), August 2003, pp. 137–146

    Google Scholar 

  18. H. Lamba, R. Narayanam, A novel and model independent approach for efficient influence maximization in social networks, in Proceedings of the 14th International Conference on Web Information Systems Engineering (WISE’13), October 2013, pp. 73–87

    Google Scholar 

  19. J. Leskovec, D. Huttenlocher, J. Kleinberg, Signed networks in social media, in Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI’10), April 2010, pp. 1361–1370

    Google Scholar 

  20. J. Leskovec, J.J. Mcauley, Learning to discover social circles in ego networks, in Proceedings of the Neural Information Processing Systems (NIPS’12), December 2012, pp. 539–547

    Google Scholar 

  21. Y. Li, J. Fan, Y. Wang, K.L. Tan, Influence maximization on social graphs: a survey. IEEE Trans. Knowl. Data Eng. 30(10), 1852–1872 (2018)

    Article  Google Scholar 

  22. Q. Liu, B. Xiang, E. Chen, H. Xiong, F. Tang, Y.X. Jeffrey, Influence maximization over large-scale social networks: a bounded linear approach, in Proceedings of the 23rd ACM International Conference on Information and Knowledge Management (CIKM’14), November 2014, pp. 171–180

    Google Scholar 

  23. X. Liu, M. Li, S. Li, S. Peng, X. Liao, X. Lu, IMGPU: GPU-accelerated influence maximization in large-scale social networks. IEEE Trans. Parall. Distrib. Syst. 25(1), 136–145 (2014)

    Article  Google Scholar 

  24. L. Lü, D. Chen, X.L. Ren, Q.M. Zhang, Y.C. Zhang, T. Zhou, Vital nodes identification in complex networks. Phys. Rep. 650, 1–63 (2016)

    Article  Google Scholar 

  25. S. Mihara, S. Tsugawa, H. Ohsaki, Influence maximization problem for unknown social networks, in Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’15), August 2015, pp. 1539–1546

    Google Scholar 

  26. S. Mihara, S. Tsugawa, H. Ohsaki, On the effectiveness of random jumps in an influence maximization algorithm for unknown graphs, in Proceedings of the 31st International Conference on Information Networking (ICOIN’17), January 2017

    Google Scholar 

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

    Article  Google Scholar 

  28. N. Ohsaka, T. Akiba, Y. Yoshida, K. Kawarabayashi, Fast and accurate influence maximization on large networks with pruned Monte-Carlo simulations, in Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI’14), July 2014, pp. 138–144

    Google Scholar 

  29. M. Richardson, P. Domingos, Mining knowledge-sharing sites for viral marketing, in Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’02) (2002), pp. 61–70

    Google Scholar 

  30. K. Saito, R. Nakano, M. Kimura, Prediction of information diffusion probabilities for independent cascade model, in Proceedings of International Conference on Knowledge-Based and Intelligent Information and Engineering Systems (2008), pp. 67–75

    Google Scholar 

  31. Y. Tang, X. Xiao, Y. Shi, Influence maximization: near-optimal time complexity meets practical efficiency, in Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD’14), June 2014, pp. 75–86

    Google Scholar 

  32. Y. Tang, Y. Shi, X. Xiao, Influence maximization in near-linear time: a martingale approach, in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD’15), May 2015, pp. 1539–1554

    Google Scholar 

  33. S. Tsugawa, A survey of social network analysis techniques and their applications to socially aware networking. IEICE Trans. Commun. E102-B(1) (2018)

    Google Scholar 

  34. S. Tsugawa, H. Ohsaki, On the robustness of influence maximization algorithms against non-adversarial perturbations, in Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’17) (2017), pp. 91–94

    Google Scholar 

  35. S. Tsugawa, Y. Matsumoto, H. Ohsaki, On the robustness of centrality measures against link weight quantization in social networks. Comput. Math. Organ. Theory 21(3), 318–339 (2015)

    Article  Google Scholar 

  36. B. Wilder, N. Immorlica, E. Rice, M. Tambe, Maximizing influence in an unknown social network, in Proceedings of the AAAI Conference on Artificial Intelligence (AAAI’18) (2018)

    Google Scholar 

  37. H. Zhuang, Y. Sun, J. Tang, J. Zhang, X. Sun, Influence maximization in dynamic social networks, in Proceedings of the 13th IEEE International Conference on Data Mining (ICDM ’13), December 2013, pp. 1313–1318

    Google Scholar 

Download references

Acknowledgment

This work was partly supported by JSPS KAKENHI Grant Number 16H02815 and 16K20931.

Author information

Authors and Affiliations

  1. University of Tsukuba, Tsukuba, Ibaraki, Japan

    Sho Tsugawa

  2. Kwansei Gakuin University, Sanda, Hyogo, Japan

    Hiroyuki Ohsaki

Authors
  1. Sho Tsugawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hiroyuki Ohsaki
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sho Tsugawa .

Editor information

Editors and Affiliations

  1. Department of Computer Engineering, Firat University, Elazig, Türkiye

    Mehmet Kaya

  2. Department of Computer Science, University of Calgary, Calgary, AB, Canada

    Reda Alhajj

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Tsugawa, S., Ohsaki, H. (2019). Robustness of Influence Maximization Against Non-adversarial Perturbations. In: Kaya, M., Alhajj, R. (eds) Influence and Behavior Analysis in Social Networks and Social Media. ASONAM 2018. Lecture Notes in Social Networks. Springer, Cham. https://doi.org/10.1007/978-3-030-02592-2_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-02592-2_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-02591-5

  • Online ISBN: 978-3-030-02592-2

  • eBook Packages: Social SciencesSocial Sciences (R0)

Publish with us

Policies and ethics

Search

Navigation