Sequential seeding policy on social influence maximization: a Q-learning-driven discrete differential evolution optimization | The Journal of Supercomputing Skip to main content
Springer Nature Link
Log in

Sequential seeding policy on social influence maximization: a Q-learning-driven discrete differential evolution optimization

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

The influence maximization problem that has caused great attention in social network analysis aims at selecting a small set of influential spreaders so that the information cascade triggered by the seed set is maximized. The majority of the existing works mainly focus on developing single-stage seeding strategies that would ignite all the seeds before the influence spread. However, it cannot depict the scenarios of the practical, where ones would like to make further decisions based on observed activation. In this paper, we investigate the policies for the intractable sequential influence maximization problem. A Q-learning-driven discrete differential evolution algorithm based on the reinforcement Q-learning model, which is treated as a parameter controller to adaptively adjust the parameters during the evolution of the algorithm, is proposed. The policy distributes the seeding actions over the spreading process by estimating the latest node status of the network dynamically. Extensive simulations are conducted on six social networks of the practical, and the findings demonstrate the superiority and effectiveness of the hybrid meta-heuristic algorithm compared with the state-of-the-art 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
¥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

Availability of data and materials

The authors declare that the data supporting the findings of this study are available within the paper.

References

  1. Azaouzi M, Mnasri W, Romdhane LB (2021) New trends in influence maximization models. Comput Sci Rev 40(100):393. https://doi.org/10.1016/j.cosrev.2021.100393

    Article  Google Scholar 

  2. Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 137–146

  3. Lin Y, Lui JC (2015) Analyzing competitive influence maximization problems with partial information: an approximation algorithmic framework. Perform Eval 91:187–204. https://doi.org/10.1016/j.peva.2015.06.012

    Article  Google Scholar 

  4. Lu W, Chen W, Lakshmanan LV (2015) From competition to complementarity: comparative influence diffusion and maximization. arXiv preprint arXiv:1507.00317https://doi.org/10.48550/arXiv.1507.00317

  5. Guo J, Zhang Y, Wu W (2021) An overall evaluation on benefits of competitive influence diffusion. IEEE Trans Big Data. https://doi.org/10.1109/TBDATA.2021.3084468

    Article  Google Scholar 

  6. Tong A, Du DZ, Wu W (2018) On misinformation containment in online social networks. Adv Neural Inform Process Syst, 341–351

  7. Zhang Y, Yang W, Du DZ (2021) Rumor correction maximization problem in social networks. Theoret Comput Sci 861(1):102–116. https://doi.org/10.1016/j.tcs.2021.02.014

    Article  MathSciNet  Google Scholar 

  8. Zhou Z, Lu H, Deng C et al (2016) User preference learning for online social recommendation. IEEE Trans Knowl Data Eng 28(9):2522–2534. https://doi.org/10.1109/TKDE.2016.2569096

    Article  Google Scholar 

  9. Jankowski J, Szymanski BK, Kazienko P et al (2018) Probing limits of information spread with sequential seeding. Sci Rep 8(1):1–9. https://doi.org/10.1038/s41598-018-32081-2

    Article  Google Scholar 

  10. Jankowski J, Bródka P, Kazienko P et al (2017) Balancing speed and coverage by sequential seeding in complex networks. Sci Rep 7(1):1–11. https://doi.org/10.1038/s41598-017-00937-8

    Article  Google Scholar 

  11. Ni Y (2017) Seeding strategies for viral marketing: an empirical comparison. Appl Soft Comput 56:730–737. https://doi.org/10.1016/j.asoc.2016.04.025

    Article  Google Scholar 

  12. Zhao J, Yang TH, Huang Y et al (2011) Ranking candidate disease genes from gene expression and protein interaction: a katz-centrality based approach. PLoS ONE 6(9):e24,306. https://doi.org/10.1371/journal.pone.0024306

    Article  Google Scholar 

  13. Hu Q, Gao Y, Ma P, et al (2013) A new approach to identify influential spreaders in complex networks. International Conference on Web-Age Information Management, 99–104

  14. Page L, Brin S, Motwani R et al (1999) The pagerank citation ranking: bringing order to the web. Tech. rep, Stanford InfoLab

  15. Brandes U, Borgatti SP, Freeman LC (2016) Maintaining the duality of closeness and betweenness centrality. Soc Netw 44:153–159. https://doi.org/10.1016/j.socnet.2015.08.003

    Article  Google Scholar 

  16. Tang J, Zhang R, Yao Y et al (2018) Maximizing the spread of influence via the collective intelligence of discrete bat algorithm. Knowl-Based Syst 160:88–103. https://doi.org/10.1016/j.knosys.2018.06.013

    Article  Google Scholar 

  17. Leskovec J, Krause A, Guestrin C, et al (2007) Cost-effective outbreak detection in networks. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 420–429

  18. Borgs C, Brautbar M, Chayes J, et al (2014) Maximizing social influence in nearly optimal time. Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, 946–957

  19. Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: A martingale approach. Proceedings of the 2015 ACM SIGMOD international conference on management of data, 1539–1554

  20. Ko YY, Cho KJ, Kim SW (2018) Efficient and effective influence maximization in social networks: a hybrid-approach. Inf Sci 465:44–161. https://doi.org/10.1016/j.ins.2018.07.003

    Article  MathSciNet  Google Scholar 

  21. Li W, Fan Y, Mo J et al (2020) Three-hop velocity attenuation propagation model for influence maximization in social networks. World Wide Web 23:1261–1273. https://doi.org/10.1007/s11280-019-00750-5

    Article  Google Scholar 

  22. Cui L, Hu H, Yu S et al (2018) Ddse: a novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks. J Netw Comput Appl 103(FEB):119–130. https://doi.org/10.1016/j.jnca.2017.12.003

    Article  Google Scholar 

  23. Wang L, Ma L, Wang C et al (2021) Identifying influential spreaders in social networks through discrete moth-flame optimization. IEEE Trans Evol Comput 25(6):1091–1102. https://doi.org/10.1109/TEVC.2021.3081478

    Article  Google Scholar 

  24. Qiu L, Tian X, Zhang J et al (2021) Lidde: A differential evolution algorithm based on local-influence-descending search strategy for influence maximization in social networks. J Netw Comput Appl 178(102):973. https://doi.org/10.1016/j.jnca.2020.102973

    Article  Google Scholar 

  25. Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 199–208

  26. Sela A, Goldenberg D, Ben-Gal I et al (2018) Active viral marketing: Incorporating continuous active seeding efforts into the diffusion model. Expert Syst Appl 107:45–60. https://doi.org/10.1016/j.eswa.2018.04.016

    Article  Google Scholar 

  27. Shakarian P, Eyre S, Paulo D (2013) A scalable heuristic for viral marketing under the tipping model. Soc Netw Anal Min 3(4):1225–1248. https://doi.org/10.1007/s13278-013-0135-7

    Article  Google Scholar 

  28. Banerjee A, Chandrasekhar AG, Duflo E et al (2013) The diffusion of microfinance. Science 341(6144):1236,498. https://doi.org/10.1126/science.1236498

    Article  Google Scholar 

  29. Tong G, Wang R (2020) On adaptive influence maximization under general feedback models. IEEE Trans Emerg Top Comput. https://doi.org/10.1109/TETC.2020.3031057

    Article  Google Scholar 

  30. Michalski R, Jankowski J, Bródka P (2020) Effective influence spreading in temporal networks with sequential seeding. IEEE Access 8:151,208-151,218. https://doi.org/10.1109/ACCESS.2020.3016913

    Article  Google Scholar 

  31. Ni C, Yang J, Kong D (2020) Sequential seeding strategy for social influence diffusion with improved entropy-based centrality. Physica A 545(123):659. https://doi.org/10.1016/j.physa.2019.123659

    Article  Google Scholar 

  32. Bródka P, Jankowski J, Michalski R (2021) Sequential seeding in multilayer networks. Chaos: An Interdisciplin J Nonlinear Sci 31(3):033,130. https://doi.org/10.1063/5.0023427

    Article  MathSciNet  Google Scholar 

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

  34. Tong G, Wu W, Tang S et al (2016) Adaptive influence maximization in dynamic social networks. IEEE/ACM Trans Netw 25(1):112–125. https://doi.org/10.1109/TNET.2016.2563397

    Article  Google Scholar 

  35. Goldenberg D, Sela A, Shmueli E (2018) Timing matters: Influence maximization in social networks through scheduled seeding. IEEE Trans Comput Soc Syst 5(3):621–638. https://doi.org/10.1109/TCSS.2018.2852742

    Article  Google Scholar 

  36. Lev T, Ben-Gal I, Shmueli E (2021) Influence maximization through scheduled seeding in a real-world setting. IEEE Trans Comput Soc Syst PP(99):1–14. https://doi.org/10.1109/TCSS.2021.3109043

    Article  Google Scholar 

  37. Tang S, Yuan J (2020) Influence maximization with partial feedback. Oper Res Lett 48(1):24–28. https://doi.org/10.1016/j.orl.2019.10.013

    Article  MathSciNet  Google Scholar 

  38. Tong G, Wang R, Dong Z et al (2020) Time-constrained adaptive influence maximization. IEEE Trans Comput Soc Syst 8(1):33–44. https://doi.org/10.1109/TCSS.2020.3032616

    Article  Google Scholar 

  39. Golovin D, Krause A (2011) Adaptive submodularity: theory and applications in active learning and stochastic optimization. J Artificial Intell Res 42:427–486. https://doi.org/10.1613/jair.3278

    Article  MathSciNet  Google Scholar 

  40. Zhu T, Wang B, Wu B et al (2014) Maximizing the spread of influence ranking in social networks. Inf Sci 278:535–544. https://doi.org/10.1016/j.ins.2014.03.070

    Article  MathSciNet  Google Scholar 

  41. Lü L, Chen D, Ren XL et al (2016) Vital nodes identification in complex networks. Phys Rep 650:1–63. https://doi.org/10.1016/j.physrep.2016.06.007

    Article  MathSciNet  Google Scholar 

  42. Pant M, Zaheer H, Garcia-Hernandez L et al (2020) Differential evolution: a review of more than two decades of research. Eng Appl Artif Intell 90(103):479. https://doi.org/10.1016/j.engappai.2020.103479

    Article  Google Scholar 

  43. Leskovec J, Krevl A, Datasets S (2011) Stanford large network dataset collection. http://snap.stanford.edu/data/

  44. Gong M, Yan J, Shen B et al (2016) Influence maximization in social networks based on discrete particle swarm optimization. Inf Sci 367:600–614. https://doi.org/10.1016/j.ins.2016.07.012

    Article  Google Scholar 

Download references

Acknowledgements

This work was financially supported by the Gansu Provincial Science Fund for Distinguished Young Scholars [grant number 23JRRA766], the Lanzhou University of Technology Fund for Outstanding Young Scholars, the National Natural Science Foundations of China [grant number 62162040] and the Natural Science Foundation of Zhejiang Province [grant number LQ20F020011].

Author information

Author notes

  1. Shihui Song, Hongyu Zhu, Qian Du, and Jitao Qu contributed equally to this work.

Authors and Affiliations

  1. School of Computer and Communication, Lanzhou University of Technology, Lanzhou, 730050, China

    Jianxin Tang, Shihui Song, Hongyu Zhu, Qian Du & Jitao Qu

  2. Wenzhou Engineering Institute of Pump &Valve, Lanzhou University of Technology, Wenzhou, 325100, China

    Jianxin Tang

Authors
  1. Jianxin Tang
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Shihui Song
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Hongyu Zhu
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Qian Du
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Jitao Qu
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Jianxin Tang.

Ethics declarations

Ethical approval

This article does not contain any studies with animals performed by any of the authors.

Conflict of interest

The authors have no competing interests to declare that are relevant to the content of this paper.

Authors’ contributions

Jianxin Tang was involved in conceptualization, supervision, project administration, funding acquisition, and writing—review and editing. Shihui Song was involved in methodology, software, validation, and writing—original draft. Hongyu Zhu contributed to resources and software. Qian Du was involved in data curation and visualization. Jitao Qu was involved in formal analysis and writing—review and editing. All authors reviewed the manuscript.

Funding

This work was not supported by any organization.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tang, J., Song, S., Zhu, H. et al. Sequential seeding policy on social influence maximization: a Q-learning-driven discrete differential evolution optimization. J Supercomput 80, 3334–3359 (2024). https://doi.org/10.1007/s11227-023-05601-9

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-023-05601-9

Keywords