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

Minimum cost seed set for threshold influence problem under competitive models

  • Published:
World Wide Web Aims and scope Submit manuscript

Abstract

Single source influence propagation based models have been widely studied, but a key challenge remains: How does a company utilize the minimum cost to select a seed set such that its influence spread can reach a desired threshold in competitive environment. One efficient way to overcome this challenge is to design an influence spread function with monotonicity and submodularity, which can provide a nice theoretical analysis of approximation ratio. In this paper, we first propose the Threshold Influence (TI) problem, i.e., selecting a seed set with minimum cost such that the influence spread reaches a given threshold η. Then we present two influence diffusion models named One-To-Many (OTM) and One-To-One (OTO) respectively. On one hand, for One-To-Many model, we prove that the influence spread function is monotone increasing as well as submodular and develop a greedy algorithm with a \((1+\ln (\frac {\eta }{\delta }))\) approximation ratio, where \(\delta >0\). In particular, the approximation ratio is (\(1+\ln (\eta )\)) if \(\eta \) is a positive integer. On the other hand, for One-To-One model, we demonstrate that the influence spread function is non-submodular. Besides, a heuristic framework is developed to solve this problem. Finally, we evaluate our algorithms by simulations on different scale networks. Through experiments, our algorithms outperform comparative methods.

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

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7

Similar content being viewed by others

Notes

  1. http://konect.uni-koblenz.de

  2. http://snap.stanford.edu

References

  1. Bharathi, S., Kempe, D., Salek, M.: Competitive influence maximization in social networks[J]. Internet and Network Economics, pp. 306–311 (2007)

  2. Budak, C., Agrawal, D., El Abbadi, A.: Limiting the spread of misinformation in social networks. In: Proceedings of the 20th international conference on World Wide Web, pp. 665–674. ACM (2011)

  3. Cornuejols, G., Fisher, M., Nemhauser, G.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms[J]. Manag. Sci. 23(8), 789–810 (1977)

    Article  MathSciNet  Google Scholar 

  4. Du, N., Liang, Y., Balcan, M., Manuel, G., Zha, H., Song, L: Scalable influence maximization for multiple products in continuous-time diffusion networks. J. Mach. Learn. Res. 18, 1–45 (2017)

    MathSciNet  MATH  Google Scholar 

  5. Fan, L., Lu, Z., Wu, W., Thuraisingham, B., Ma, H., Bi, Y.: Least cost rumor blocking in social networks. In: 33rd international conference on distributed computing systems (2013)

  6. Gao, S., Ma, J., Chen, Z., Wang, G., Xing, C.: Ranking the spreading ability of nodes in complex networks based on local structure[J]. Physica A: Statistical Mechanics and its Applications 403, 130–147 (2014)

    Article  Google Scholar 

  7. Goyal, A., Bonchi, F., Lakshmanan, L.V.S., Venkatasubramanian, S.: On minimizing budget and time in influence propagation over social networks. Soc. Netw. Anal. Min. 3(2), 179–192 (2013)

    Article  Google Scholar 

  8. Han, M., Yan, M., Cai, Z., Li, Y., Cai, X., Yu, J.: Influence maximization by probing partial communities in dynamic online social networks[J]. Transactions on Emerging Telecommunications Technologies 28(4) (2017)

    Article  Google Scholar 

  9. Karp, R.M.: Reducibility among combinatorial problems. In: Thatcher, R.E., Miller, J.W. (eds.) Complexity of computer computations, pp 85–103. Plenum, New York (1972)

    Chapter  Google Scholar 

  10. Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. KDD’03, pp. 137–146 (2003)

  11. Kuhnle, A., Pan, T., Alim, M., Thai, T.: Scalable bicriteria algorithms for the threshold activation problem in online social networks. In: IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, pp. 1–9. Atlanta (2017)

  12. Lawyer, G.: Understanding the influence of all nodes in a network[J]. Sci. Rep. 5, 8665 (2015)

    Article  Google Scholar 

  13. Li, S., Zhu, Y., Li, D., Kim, D., Huang, H.: Rumor restriction in online social networks. In: Performance computing and communications conference (IPCCC), 2013 IEEE 32nd International. IEEE, pp. 1–10 (2013)

  14. Long, C., Wong, R.C.: Minimizing seed set for viral marketing. In: Proceedings of the 2011 IEEE 11th international conference on data mining, ICDM 11, pp. 427–436 (2011)

  15. Lu, W., Bonchi, F., Goyal, A., Lakshmanan, L.V.S.: The bang for the buck: Fair competitive viral marketing from the host perspective. In: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD ’13), pp. 928–936

  16. Myers, S.A., Zhu, C., Leskovec, J.: Information diffusion and external influence in networks. In: Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 33–41. ACM (2012)

  17. Nemhauser, G., Wolsey, L., Fisher, M.: An analysis of the approximations for maximizing submodular set functions. Math. Program. 14, 265–294 (1978)

    Article  MathSciNet  Google Scholar 

  18. Page, L., Brin, S., Motwani, R, Winograd, T.: The PageRank citation ranking: Bringing order to the Web. Stanford InfoLab (1999)

  19. Tong, G., Wu, W., Tang, S., Du, D.: Adaptive influence maximization in dynamic social networks[J]. IEEE/ACM Trans. Networking (TON) 25(1), 112–125 (2017)

    Article  Google Scholar 

  20. Tong, G., Wu, W., Guo, L., Li, D., Liu, C., Liu, B., Du, D.: An efficient randomized algorithm for rumor blocking in online social networks. In: IEEE international conference on computer communications (2016)

  21. Yan, Q., Huang, H., Gao, Y., Lu, W., He, Q.: Group-level influence maximization with budget constraint. In: Database systems for advanced applications (DASFAA), Part I, LNCS, 10177, pp. 625–641 (2017)

    Chapter  Google Scholar 

  22. Zhang, P., Chen, W., Sun, X., Wang, Y., Zhang, J.: Minimizing seed set selection with probabilistic coverage guarantee in a social network. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD14), pp. 1306–1315 (2014)

  23. Zhu, Y.D.L., Zhang, Z.: Minimum cost seed set for competitive social influence. In: IEEE INFOCOM 2016-The 35th annual IEEE international conference on computer communications, pp. 1–9 (2016)

Download references

Acknowledgment

This research was supported in part by the National Natural Science Foundation of China under grant 11671400, 61672524, the Fundamental Research Funds for the Central University, and the Research Funds of Renmin University of China 2015030273, and the Research Funds of Renmin University of China 16XNH116.

Author information

Authors and Affiliations

  1. School of Information, Renmin University of China, Beijing, 100872, China

    Ruidong Yan & Deying Li

  2. Department of Computer Science, California State University at Los Angeles, Los Angeles, CA, 90032, USA

    Yuqing Zhu & Zilong Ye

Authors
  1. Ruidong Yan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuqing Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Deying Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zilong Ye
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Deying Li.

Additional information

This article belongs to the Topical Collection: Special Issue on Social Computing and Big Data Applications

Guest Editors: Xiaoming Fu, Hong Huang, Gareth Tyson, Lu Zheng, and Gang Wang

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yan, R., Zhu, Y., Li, D. et al. Minimum cost seed set for threshold influence problem under competitive models. World Wide Web 22, 2977–2996 (2019). https://doi.org/10.1007/s11280-018-0607-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11280-018-0607-9

Keywords

Search

Navigation