Stochastic dynamic programming heuristics for influence maximization–revenue optimization | International Journal of Data Science and Analytics Skip to main content
Springer Nature Link
Log in

Stochastic dynamic programming heuristics for influence maximization–revenue optimization

  • Regular Paper
  • Published:
International Journal of Data Science and Analytics Aims and scope Submit manuscript

Abstract

The well-known influence maximization (IM) problem has been actively studied by researchers over the past decade with emphasis on marketing and social networks. Existing research has determined solutions to the IM problem by obtaining the influence spread and utilizing the property of submodularity. This paper is based on a novel approach to the IM problem geared toward optimizing clicks, and consequently revenue, within an online social network (OSN). Our approach differs from existing approaches by adopting a novel, decision-making perspective using stochastic dynamic programming (SDP). Thus, we define a new problem, influence maximization–revenue optimization and propose SDP as a solution method. The SDP method has lucrative gains for an advertiser in terms of optimizing clicks and generating revenue, but one drawback to the method is its associated “curse of dimensionality” particularly for large OSNs. Thus, we introduce the L-degree heuristic, adaptive hill-climbing heuristic and the multistage particle swarm optimization heuristic as methods which are orders of magnitude faster than the SDP method while achieving near-optimal results. We compare these heuristics on both synthetic and real-world networks.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Abbassi, Z., Bhaskara, A., Misra, V.: Optimizing display advertising in online social networks. In: Proceedings of the 24th International Conference on World Wide Web, International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, Switzerland, WWW ’15, pp. 1–11, (2015). https://doi.org/10.1145/2736277.2741648

  2. Bellman, R.: Dynamic Programming. Princeton University Press, Princeton, NJ (1957)

    MATH  Google Scholar 

  3. Bertsekas, D.P., Tsitsiklis, J.N.: An analysis of stochastic shortest path problems. Math. Oper. Res. 16(3), 580–595 (1991). https://doi.org/10.1287/moor.16.3.580

    Article  MathSciNet  MATH  Google Scholar 

  4. Bhagat, S., Goyal, A., Lakshmanan, LV.: Maximizing product adoption in social networks. In: Proceedings of the Fifth ACM International Conference on Web Search and Data Mining, ACM, New York, NY, USA, WSDM ’12, pp. 603–612, (2012). https://doi.org/10.1145/2124295.2124368

  5. Cao, T., Wu, X., Hu, T.X., Wang, S.: Active learning of model parameters for influence maximization. In: Gunopulos, D., Hofmann, T., Malerba, D., Vazirgiannis, M. (eds.) Machine Learning and Knowledge Discovery in Databases, pp. 280–295. Springer, Berlin (2011)

    Chapter  Google Scholar 

  6. Chakrabarti, S., Dom, B., Indyk, P.: Enhanced hypertext categorization using hyperlinks. In: Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, ACM, New York, NY, USA, SIGMOD ’98, pp. 307–318, (1998).https://doi.org/10.1145/276304.276332

  7. Chang, B., Xu, T., Liu, Q., Chen, E.H.: Study on information diffusion analysis in social networks and its applications. Int. J. Autom. Comput. 15, 1–26 (2018)

    Article  Google Scholar 

  8. Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, KDD ’09, pp. 199–208, (2009). https://doi.org/10.1145/1557019.1557047

  9. Chen, W., Wang, C., Wang, Y.: 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, ACM, New York, NY, USA, KDD ’10, pp 1029–1038, (2010). https://doi.org/10.1145/1835804.1835934

  10. Chen, W., Collins, A., Cummings, R., Ke, T., Liu, Z., Rincon, D., Sun, X., Wei, W., Wang, Y., Yuan, Y.: Influence maximization in social networks when negative opinions may emerge and propagate. In: Proceedings of the 2011 SIAM International Conference on Data Mining (SDM’2011) (2011)

  11. Clerc, M.: Discrete Particle Swarm Optimization, Illustrated by the Traveling Salesman Problem, pp. 219–239. Springer, Berlin (2004). https://doi.org/10.1007/978-3-540-39930-8_8

    Book  MATH  Google Scholar 

  12. Davis, L.: Bit-climbing, representational bias, and test suit design. Proc. Int. Conf. Genetic Algorithm 1991, 18–23 (1991)

    Google Scholar 

  13. Domingos, P., Richardson, M.: Mining the network value of customers. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, KDD ’01, pp 57–66, (2001). https://doi.org/10.1145/502512.502525

  14. Eberhart, R., Kennedy, J.: A new optimizer using particle swarm theory. In: Symposium on Micro Machine and Human Science. Japan, Nagoya, Piscataway, NJ, pp. 39–43 (1995). https://doi.org/10.1109/MHS.1995.494215

  15. Eberhart, R.C., Shi, Y., Kennedy, J.: Swarm Intelligence. Morgan Kaufmann Publishers, San Francisco, Amsterdam (2001)

    Google Scholar 

  16. Facebook (2016) Facebook reports fourth quarter and full year 2016 results. https://investor.fb.com/investor-news/press-release-details/2017/facebook-Reports-Full-Year-2016 (2016). Accessed 3 Jan 2017

  17. Galhotra, S., Arora, A., Roy, S.: Holistic influence maximization: Combining scalability and efficiency with opinion-aware models. In: Proceedings of the 2016 International Conference on Management of Data, ACM, New York, NY, USA, SIGMOD ’16, pp. 743–758, (2016). https://doi.org/10.1145/2882903.2882929

  18. Galstyan, A., Musoyan, V.L., Cohen, P.R.: Maximizing influence propagation in networks with community structure. Phys. Rev. E Stat Nonlinearv Soft Matter Phys. 79(5 Pt 2), 056–102 (2009)

    Google Scholar 

  19. Geman, S., Geman, D.: Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Trans. Pattern Anal. Mac.h Intell. 6(6), 721–741 (1984). https://doi.org/10.1109/TPAMI.1984.4767596

    Article  MATH  Google Scholar 

  20. Gomez Rodriguez, M., Leskovec, J., Krause, A.: Inferring networks of diffusion and influence. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, KDD ’10, pp. 1019–1028, (2010). https://doi.org/10.1145/1835804.1835933

  21. Goyal, A., Bonchi, F., Lakshmanan, LV.: Learning influence probabilities in social networks. In: Proceedings of the Third ACM International Conference on Web Search and Data Mining, ACM, New York, NY, USA, WSDM ’10, pp. 241–250, (2010). https://doi.org/10.1145/1718487.1718518

  22. Granovetter, M.: Threshold models of collective behavior. Am. J. Sociol. 83(6), 1420–1443 (1978). https://doi.org/10.1086/226707

    Article  Google Scholar 

  23. Han, K., Xu, C., Gui, F., Tang, S., Huang, H., Luo, J.: Discount allocation for revenue maximization in online social networks. In: Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, ACM, New York, NY, USA, Mobihoc ’18, pp. 121–130, (2018). https://doi.org/10.1145/3209582.3209595

  24. He, X., Kempe, D.: Stability of influence maximization. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, KDD ’14, pp. 1256–1265, (2014). https://doi.org/10.1145/2623330.2623746

  25. Hosein, P., Lawrence, T.: Stochastic dynamic programming model for revenue optimization in social networks. 2015 IEEE 11th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob) pp. 378–383 (2015)

  26. Hosseini-Pozveh, M., Zamanifar, K., Naghsh-Nilchi, A.R., Dolog, P.: Maximizing the spread of positive influence in signed social networks. Intell. Data Anal. 20(1), 199–218 (2016)

    Article  Google Scholar 

  27. 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, ACM, New York, NY, USA, KDD ’03, pp. 137–146, (2003). https://doi.org/10.1145/956750.956769

  28. Kennedy, J., Eberhart, RC.: A discrete binary version of the particle swarm algorithm. In: Proceedings of Conference on System, Man and Cybernetics (1997)

  29. Kimura, M., Saito, K., Motoda, H.: Minimizing the spread of contamination by blocking links in a network. In: Proceedings of the 23rd National Conference on Artificial Intelligence , Vol. 2, AAAI Press, AAAI’08, pp 1175–1180, (2008). http://dl.acm.org/citation.cfm?id=1620163.1620255

  30. Kimura, M., Saito, K., Ohara, K., Motoda, H.: Speeding-up node influence computation for huge social networks. Int. J. Data Sci. Anal. 1(1), 3–16 (2016). https://doi.org/10.1007/s41060-015-0001-y

    Article  Google Scholar 

  31. Kossinets, G., Kleinberg, J., Watts, D.: The structure of information pathways in a social communication network. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, KDD ’08, pp. 435–443, (2008). https://doi.org/10.1145/1401890.1401945

  32. Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data (2014). Accessed 29 Feb 2017

  33. Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., Glance, N.: Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, KDD ’07, pp. 420–429, (2007). https://doi.org/10.1145/1281192.1281239

  34. Liu, B., Cong, G., Xu, D., Zeng, Y.: Time constrained influence maximization in social networks. In: 2012 IEEE 12th International Conference on Data Mining (ICDM), IEEE, pp. 439–448 (2012)

  35. Loukides, G., Gwadera, R.: Preventing the diffusion of information to vulnerable users while preserving pagerank. Int. J. Data Sci. Anal. 5(1), 19–39 (2018). https://doi.org/10.1007/s41060-017-0082-x

    Article  Google Scholar 

  36. Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model Comput. Simul. 8(1), 3–30 (1998). https://doi.org/10.1145/272991.272995

    Article  MATH  Google Scholar 

  37. Meerman, S.: Viral marketing: Let the world tell your story for free. https://www.pragmaticmarketing.com/resources/articles/Viral-Marketing-Let-The-World-Tell-Your-Story (2008). Accessed 10 Oct 2017

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

    Article  Google Scholar 

  39. Nascimento, J., Powell, W.B.: An optimal approximate dynamic programming algorithm for concave, scalar storage problems with vector-valued controls. IEEE Trans. Autom. Control 58(12), 2995–3010 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  40. Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions–I. Math. Progr. 14(1), 265–294 (1978). https://doi.org/10.1007/BF01588971

    Article  MathSciNet  MATH  Google Scholar 

  41. Powell, W.B.: Approximate Dynamic Programming: Solving the Curses of dimensionality, vol. 703. Wiley, London (2007)

    Book  MATH  Google Scholar 

  42. Pramanik, S., Sharma, M., Danisch, M., Wang, Q., Guillaume, JL., Bivas, M.: Easy-mention: a model-driven mention recommendation heuristic to boost your tweet popularity. Int. J. Data Sci. Anal. 5:1–17, (2018). https://doi.org/10.1007/s41060-018-0121-2

  43. Rahaman, I., Hosein, P.: On the Problem of Multi-Staged Impression Allocation in Online Social Networks, pp. 65–84. Springer, Cham (2018)

    Google Scholar 

  44. Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, KDD ’02, pp. 61–70, (2002).https://doi.org/10.1145/775047.775057

  45. Rossetti, G., Milli, L., Salvatore, R., Sîrbu, A., Pedreschi, D., Giannotti, F.: Ndlib: a python library to model and analyze diffusion processes over complex networks. Int. J. Data Sci. Anal. 5(1), 61–79 (2018). https://doi.org/10.1007/s41060-017-0082-x

    Article  Google Scholar 

  46. Saito, K., Nakano, R., Kimura, M.: Prediction of information diffusion probabilities for independent cascade model. In: Proceedings of the 12th International Conference on Knowledge-Based Intelligent Information and Engineering Systems, Part III, Springer-Verlag, Berlin, Heidelberg, KES ’08, pp. 67–75, (2008). https://doi.org/10.1007/978-3-540-85567-5_9

  47. Salman, A., Ahmad, I., Al-Madani, S.: Particle swarm optimization for task assignment problem. Microprocess. Microsyst. 26(8), 363–371 (2002)

    Article  Google Scholar 

  48. Sha, D., Hsu, C.Y.: A hybrid particle swarm optimization for job shop scheduling problem. Comput. Ind. Eng. 51(4), 791–808 (2006)

    Article  Google Scholar 

  49. Singer, Y.: How to win friends and influence people, truthfully: influence maximization mechanisms for social networks. In: Proceedings of the fifth ACM international conference on Web search and data mining, ACM, pp. 733–742 (2012)

  50. Song, Y., Dinh, T.: Optimal containment of misinformation in social media: A scenario-based approach. In: Combinatorial Optimization and Applications. COCOA 2014. Lecture Notes in Computer Science, Springer, pp. 547–556 (2014)

  51. Sun, H., Cheng, R., Xiao, X., Yan, J., Zheng, Y., Qian, Y.: Maximizing social influence for the awareness threshold model. In: Pei, J., Manolopoulos, Y., Sadiq, S., Li, J. (eds.) Database Systems for Advanced Applications, pp. 491–510. Springer, Cham (2018)

    Chapter  Google Scholar 

  52. Tsang, E., Voudouris, C.: Fast local search and guided local search and their application to british telecom’s workforce scheduling problem. Oper. Res. Lett. 20(3), 119–127 (1997). https://doi.org/10.1016/S0167-6377(96)00042-9

    Article  MATH  Google Scholar 

  53. Wang, K.P., Huang, L., Zhou, C.G., Pang, W.: Particle swarm optimization for traveling salesman problem. In: International Conference Machine Learning Cybernetics, IEEE, vol. 3, pp. 1583–1585 (2003)

  54. Wang, Y., Cong, G., Song, G., Xie, K.: Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, KDD ’10, pp. 1039–1048, (2010). https://doi.org/10.1145/1835804.1835935

  55. Wen, Y.T., Peng, W.C., Shuai, H.H.: Maximizing social influence on target users. In: Phung, D., Tseng, V.S., Webb, G.I., Ho, B., Ganji, M., Rashidi, L. (eds.) Advances in Knowledge Discovery and Data Mining, pp. 701–712. Springer, Cham (2018)

    Chapter  Google Scholar 

  56. Wu, H.H., Küçükyavuz, S.: A two-stage stochastic programming approach for influence maximization in social networks. Comput. Optim. Appl. 69(3), 563–595 (2018). https://doi.org/10.1007/s10589-017-9958-x

    Article  MathSciNet  MATH  Google Scholar 

  57. Yang, J., Liu, J.: Influence maximization-cost minimization in social networks based on a multiobjective discrete particle swarm optimization algorithm. IEEE Access 6, 2320–2329 (2018)

    Article  Google Scholar 

  58. Zafarani, R., Liu, H.: Social computing data repository at ASU. (2009). http://socialcomputing.asu.edu. Accessed 29 Feb 2017

  59. Zhang, Y., Zhang, P., Bao, Z., Xie, Z., Liu, Q., Zhang, B.: Finding influential nodes by a fast marginal ranking method. In: Wang, J., Cong, G., Chen, J., Qi, J. (eds.) Databases Theory and Applications, pp. 249–261. Springer, Cham (2018)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, The University of the West Indies, St. Augustine, Trinidad

    Trisha Lawrence

  2. Department of Computer Science, The University of the West Indies, St. Augustine, Trinidad

    Patrick Hosein

Authors
  1. Trisha Lawrence
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Patrick Hosein
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Trisha Lawrence.

Ethics declarations

Conflict of Interest

On behalf of all authors, the corresponding author states that there is no conflict of interest.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lawrence, T., Hosein, P. Stochastic dynamic programming heuristics for influence maximization–revenue optimization. Int J Data Sci Anal 8, 1–14 (2019). https://doi.org/10.1007/s41060-018-0155-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s41060-018-0155-5

Keywords

Search

Navigation