Skip to main content
SpringerLink
Log in

An influence maximization algorithm based on low-dimensional representation learning

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Influence maximization (IM) problem is to choose k seed nodes in the social network to maximize the number of nodes that can be affected. As an essential part of the social network analysis, the influence maximization problem has been extensively investigated. Most existing algorithms usually set the activation probability to a fixed value or reciprocal of the in-degree. However, this operation is not accurate because the activation probability is more complicated than those mentioned above in the real social networks. To solve this problem, this paper proposes a new algorithm called Low-Dimensional Representation Learning for IM (LDRLIM) to address the IM problem. The LDRLIM utilizes Discount-degree Descending (DED) search strategy to generate the candidate nodes set ℂ and IC Walk to obtain the influence context of the candidate nodes. The LDRLIM algorithm learns the low-dimensional embedding vectors of influencers and susceptible nodes according to a Multi-task Neural Network Low-dimensional Representation learning model (MNNLR). Afterwards, the Similarity Influence (SI) of the node is obtained according to the representation vectors of the nodes. The LDRLIM algorithm employs SI to consider the potential influence relationship between nodes by embedding vector. Furthermore, the Cost-Effective Lazy Forward (CELF) strategy is used to accelerate the process of selecting the influential nodes, which avoids a large amount of model simulation time to improve efficiency. Therefore, the proposed LDRLIM algorithm is suitable for large-scale social networks. The experimental results on seven real-world datasets indicate that the LDRLIM significantly outperforms other comparison algorithms.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

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
Fig. 9

Similar content being viewed by others

References

  1. Cheng J, Wu X, Zhou M, Gao S, Huang Z, Liu C (2019) A novel method for detecting new overlapping Community in Complex Evolving Networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems 49:1832–1844

    Article  Google Scholar 

  2. Sun H, Jie W, Loo J, Wang L, Ma S, Han G, Wang Z, Wei X (2018) A parallel self-organizing overlapping community detection algorithm based on swarm intelligence for large scale complex networks. Futur Gener Comput Syst 89:265–285

    Article  Google Scholar 

  3. J. Olkhovskaya, G. Neu, G. Lugosi, Online Influence Maximization with Local Observations, (2018)

  4. Devarapalli RK, Biswas A (2021) Rumor Detection and Tracing its Source to Prevent Cyber〤rimes on Social Media, Intelligent Data Analytics for Terror Threat Prediction

  5. Mondal T, Pramanik P, Bhattacharya I, Boral N, Ghosh S (2018) Analysis and early detection of rumors in a post disaster scenario. Inf Syst Front 20:961–979

    Article  Google Scholar 

  6. Santhoshkumar S, Babu L (2020) Earlier detection of rumors in online social networks using certainty-factor-based convolutional neural networks. Social Network Analysis and Mining 10

  7. Lin L, Chen Z , (2020) Social rumor detection based on multilayer transformer encoding blocks, Concurrency and Computation: Practice and Experience

  8. Mittal S, Sengupta D, Chakraborty T (2021) Hide and Seek: Outwitting Community Detection Algorithms. IEEE Transactions on Computational Social Systems

  9. Ghasemian A, Hosseinmardi H, Clauset A (2018) Evaluating Overfit and Underfit in models of network community structure. IEEE Transactions on Knowledge & Data Engineering

  10. Liu C, Kang Q, Kong H, Li W, Kang Y (2020) An iterated local search algorithm for community detection in complex networks. International Journal of Modern Physics B

  11. G. Panagopoulos, F.D. Malliaros, M. Vazirgiannis, Influence Maximization via Representation Learning, (2019)

  12. G.D. A, #X, Angelo, L.S. B, Y.V. C (2019) Recommending links through influence maximization. Theoretical Computer Science 764:30–41

  13. Gao H, Kim J, Sakurai Y (2019) Influence maximization algorithm based on cross propagation in location-based social networks. Information Systems Research:27–42. https://doi.org/10.1007/978-3-319-32055-7

  14. He Q, Wang X, Lei Z, Huang M, Cai Y, Ma L (2019) TIFIM: a two-stage iterative framework for influence maximization in social networks. Appl Math Comput 354:338–352

    MathSciNet  MATH  Google Scholar 

  15. Vega-Oliveros DA, Costa L, Rodrigues FA (2020) Influence maximization by rumor spreading on correlated networks through community identification. Commun Nonlinear Sci Numer Simul 105094

  16. S. Bourigault, S. Lamprier, P. Gallinari, Representation learning for information diffusion through social networks: an embedded cascade model, the ninth ACM international conference, 2016

    Book  Google Scholar 

  17. Aral S, Dhillon PS (2018) Social influence maximization under empirical influence models. Nature Human Behaviour

  18. Li Y, Fan J, Wang Y, Tan KL (2018) Influence maximization on social graphs: a survey. IEEE Transactions on Knowledge & Data Engineering:1–1

  19. Yuezhi LI, Zhu Y, Zhong M, Computer SO, W. University (2018) k-core filtered influence maximization algorithms in social networks. Journal of Computer Applications

  20. Li D, Wang W, Jin C, Ma J, Liu J (2019) User recommendation for promoting information diffusion in social networks. Physica A: Statistical Mechanics and its Applications 534:121536

    Article  Google Scholar 

  21. Feng S, Cong G, Khan A, Li X, Liu Y, Chee YM (2018) Inf2vec: Latent representation model for social influence embedding. In: 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE, pp 941–952

    Chapter  Google Scholar 

  22. M. Heimann, H. Shen, T. Safavi, D. Koutra, Node Representation Learning for Multiple Networks: The Case of Graph Alignment, (2018)

  23. Chen W, Yuan Y, Zhang L (2010) Scalable influence maximization in social networks under the linear threshold model, ICDM 2010, the 10th IEEE international conference on data mining, Sydney, Australia, 14-17 December 2010, 2011

  24. Y. Tang, Y. Shi, X. Xiao, Influence maximization in near-linear time:a martingale approach, the 2015 ACM SIGMOD international conference, 2015

    Book  Google Scholar 

  25. Cui L, Hu H, Yu S, Yan Q, Ming Z, Wen Z, Lu N (2018) DDSE: a novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks. Journal of Network & Computer Applications 103:119–130

    Article  Google Scholar 

  26. Singh SS, Kumar A, Singh K, Biswas B (2019) LAPSO-IM: a learning-based influence maximization approach for social networks. Appl Soft Comput 82:105554

    Article  Google Scholar 

  27. Qiu L, Tian X, Sai S, Gu C (2020) LGIM: a global selection algorithm based on local influence for influence maximization in social networks. IEEE Access 8:4318–4328

    Article  Google Scholar 

  28. Qiu L, Tian X, Zhang J, Gu C, Sai S (2021) LIDDE: A differential evolution algorithm based on local-influence-descending search strategy for influence maximization in social networks. Journal of Network and Computer Applications

  29. Lu X, Li X, Mou L (2017) Semi-supervised multitask learning for scene recognition. IEEE Transactions on Cybernetics 45:1967–1976

    Google Scholar 

  30. J. Bhatta, D. Shrestha, S. Nepal, S. Pandey, S. Koirala, Efficient Estimation of Nepali Word Representations in Vector Space, (2020)

  31. Miao, Zhongchen, Fang, Yi, Zhou, Chen, Kai, Zhang, Wenjun, Zha, Cost-Effective Online Trending Topic Detection and Popularity Prediction in Microblogging, ACM transactions on information systems, (2017)

Download references

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China [Grant No. 71772107] and Natural Science Foundation of Shandong Province [Grant No. ZR2020MF044].

Author information

Authors and Affiliations

  1. Shandong Province Key Laboratory of Wisdom Mine Information Technology, College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao, 266590, China

    Yuening Liu, Liqing Qiu & Chengai Sun

Authors
  1. Yuening Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Liqing Qiu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chengai Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Liqing Qiu.

Additional information

Publisher’s note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, Y., Qiu, L. & Sun, C. An influence maximization algorithm based on low-dimensional representation learning. Appl Intell 52, 15865–15882 (2022). https://doi.org/10.1007/s10489-022-03178-z

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-022-03178-z

Keywords

Search

Navigation