Balancing Speed and Accuracy in Influence Maximization: A Reinforcement Learning Solution

Khabat Atar; Amir Sheikhahmadi; Keyhan Khamforoosh

doi:10.24017/

Authors

Khabat Atar Department of Science Computer, Faculty of Health and Science, Koya University, Koya, Iraq https://orcid.org/0009-0005-7008-9041
Amir Sheikhahmadi Department of Engineering, RMIT University, Melbourne, Australia https://orcid.org/0000-0002-0696-2900
Keyhan Khamforoosh Department of Computer Engineering, Sa.C., Islamic Azad University, Sanandaj, Iran https://orcid.org/0000-0003-0792-0523

Abstract

Influence maximization involves selecting an optimal subset of nodes within a graph to activate as many nodes as possible in a network. This approach is categorized as non-polynomial time, and no specific algorithm is currently available to run efficiently within a reasonable time frame, especially for large-scale networks. Numerous methods have been introduced to resolve this challenge, including greedy algorithms, structural heuristics, and metaheuristic approaches. Although greedy algorithms and their improved versions achieve high accuracy, they often suffer from poor scalability and slow execution times on large graphs. In contrast, structural methods offer faster computation but at the cost of reduced accuracy. Metaheuristic algorithms, while promising, face difficulties in balancing speed and accuracy due to the expansive search space inherent in complex social networks. This study introduces a novel method that leverages Q-learning, a reinforcement learning technique, to optimize influence maximization. The proposed method narrows down the search space by focusing on high-degree influential nodes. It dynamically updates the Q-table by assigning rewards and penalties based on the nodes’ impact during influence propagation, modeled using the Independent Cascade framework. This approach effectively balances exploration and exploitation, enabling the identification of a highly influential seed set with improved efficiency. Experiments conducted on various real-world datasets show that the Q-learning-based method significantly reduces execution time compared to genetic, particle swarm optimization, random, degree centrality, and K-shell algorithms while achieving higher influence spread in most cases. These results underscore the promise of reinforcement learning techniques in addressing complex network optimization problems such as influence maximization.

Keywords:

Influence maximization, Q-learning, Genetic algorithm, Weighted networks, independent cascade model

References

S. Banerjee, M. Jenamani, and D. K. Pratihar, "A survey on influence maximization in a social network," Knowledge and Information Systems, vol. 62, no. 9, pp. 3417–3455, Sep. 2020, doi: 10.1007/s10115-020-01461-4

D. H. Zanette, "Dynamics of rumor propagation on small-world networks," Physical Review E, vol. 65, no. 4, p. 041908, Apr. 2002, doi: 10.1103/PhysRevE.65.041908

M. Czuba and P. Bródka, “Rank-refining seed selection methods for budget constrained influence maximization in multilayer networks under linear threshold model,” Social Network Analysis and Mining, vol. 15, no. 1, p. 46, Apr. 2025. doi: 10.1007/s13278-025-01454-7

A. Mohammadi, K. Khamforoosh. “Influence maximization in social networks using learning automata”, International Journal of Computer Applications, 129(8):4-10, Nov. 2015, doi:10.5120/ijca2015906898

D. Kempe, J. Kleinberg, and É. 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, pp. 137–146, Aug. 2003, doi: 10.1145/956750.956769

T. Chen, S. Yan, J. Guo, and W. Wu, "ToupleGDD: A fine-designed solution of influence maximization by deep rein-forcement learning," IEEE Transactions on Computational Social Systems, pp. 1–12, Oct. 2023, doi: 10.1109/TCSS.2023.3245670

L. Wei, Z. Deng, Y. Chen, and L. Chen, "A Greedy Descent Method for Budget Constrained Continuous Influence Max-imization in Online Social Network," in IEEE Transactions on Computational Social Systems, PP. 1-21, Apr. 2025, doi: 10.1109/TCSS.2025.3551651.

H. Kaur and J. He, "Blocking negative influential node set in social networks: From host perspective," Transactions on Emerging Telecommunications Technologies, vol. 28, p. e4723, Jun. 2017, doi: 10.1002/ett.4723

I. H. Sarker, “Machine learning: Algorithms, real-world applications and research directions,” SN Computer Science., vol. 2, no. 3, pp. 1–21, Mar. 2021, doi: 10.1007/s42979-021-00592-x.

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, “Cost effective outbreak detection in networks,” in Proceedings of the 13th ACMSIG international conference on Knowledge discovery and data mining, Aug. 2007, pp.420-429, https://doi.org/10.1145/1281192.1281239

T. Chen, S. Yan, J. Guo, and W. Wu, "ToupleGDD: A fine-designed solution of influence maximization by deep rein-forcement learning," IEEE Transactions on Computational Social Systems, pp. 1–12, 2023, doi: 10.1109/TCSS.2023.3245670

B. Guo, F. Z. Chen, and M. Q. Li, "A multi-objective optimization approach for influence maximization in social net-works," in Proceedings of the 24th International Conference on Industrial Engineering and Engineering Management, Springer, May 2019, pp. 706–715, doi: 10.1007/978-981-13-3402-3_74

K. Garimella, A. Gionis, N. Parotsidis, and N. Tatti, "Balancing information exposure in social networks," in Proceedings of the 31st International Conference on Neural Information Processing Systems (NeurIPS),May 2017, pp. 4666–4674, doi: 10.5555/3294996.3295219

R. Becker, F. Corò, G. D’Angelo, and H. Gilbert, "Balancing spreads of influence in a social network," in Proceedings of the 34th AAAI Conference on Artificial Intelligence, vol. 34, Feb, 2020, pp. 3–10, doi: 10.1609/aaai. v34i01.5327

K. Ma, X. Xu, H. Yang, R. Cao and L. Zhang, "Fair Influence Maximization in Social Networks: A Community-Based Evolutionary Algorithm," in IEEE Transactions on Emerging Topics in Computing, vol. 13, no. 1, pp. 262-275, Jan.-Mar. 2025, doi: 10.1109/TETC.2024.3403891.

S. Yang, Q. Du, G. Zhu, J. Cao, L. Chen, W. Qin, and Y. Wang, “Balanced influence maximization in social networks based on deep reinforcement learning,” Neural Networks, vol. 169, pp. 334–351, Jan. 2024, doi: 10.1016/j.neunet.2023.10.030

Q. He et al., "Multistage Competitive Opinion Maximization With Q-Learning-Based Method in Social Networks," in IEEE Transactions on Neural Networks and Learning Systems, vol. 36, no. 4, pp. 7158-7168, Apr. 2025, doi: 10.1109/TNNLS.2024.3387293.

J. J. Lotf, M. A. Azgomi, and M. R. E. Dishabi, “An improved influence maximization method for social networks based on genetic algorithm,” Physica A: Statistical Mechanics and its Applications. vol. 586, p. 126480, Jan. 2022, doi: 10.1016/j.physa.2021.126480.

W. Ahmad and B. Wang, “A learning-based influence maximization framework for complex networks via K-core hier-archies and reinforcement learning,” Expert Systems with Applications, vol. 259, p. 125393, Jan. 2025, doi: 10.1016/j.eswa.2024.125393

S. Nandi, M. C. Malta, G. Maji, S. Saha, R. K. Mishra, and N. Ganguly, “IC-SNI: Measuring nodes’ influential capability in complex networks through structural and neighboring information,” *Knowledge. Information System*, vol. 67, pp. 1309–1350, Apr. 2025, doi: 10.1007/s10115-024-02262-9.

N. Song, W. Sheng, Y. Sun, T. Lin, Z. Wang, Z. Xu, and F. Zhang , “Online dynamic influence maximization based on deep reinforcement learning,” Neurocomputing, vol. 618, p. 129117, Feb. 2025, doi: 10.1016/j.neucom.2024.129117.

S. Yang, et al., “Balanced influence maximization in social networks based on deep reinforcement learning,” Neural Networks, vol. 169, pp. 334–351, Jan., 2024, doi: 10.1016/j.neunet.2023.10.030.

K. Ali, C.-Y. Wang, M.-Y. Yeh, and Y.-S. Chen, “Addressing competitive influence maximization on unknown social network with deep reinforcement learning,” in 2020 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), The Hague, Netherlands, pp. 196–203, Aug., 2020, doi: 10.1109/ASONAM49781.2020.9381471.

J. Wang, Z. Cao, C. Xie, Y. Li, J. Liu, and Z. Gao, “DGN: Influence maximization based on deep reinforcement learning,” The Journal of Supercomputing, vol. 81, no. 1, p. 130, Jan. 2025, doi.org/10.1007/s11227-024-06300-9.

F. Wang, Z. Zhu, P. Liu, and P. Wang, “Influence maximization in social netwnhhjhork considering memory effect and social reinforcement effect,” Future Internet, vol. 11, no. 4, p. 95, Apr. 2019, doi: 10.3390/fi11040095.

Z. Wang, X. Chen, X. Li, Y. Du, and X. Lan, “Influence maximization based on network representation learning in so-cial network,” Intelligent Data Analysis, vol. 26, no. 5, pp. 1321–1340, Sep. 2022, doi.org/10.3233/IDA-216149.

J. Tang, C. Li, L. Liu, T. Xu, and Y. Yao, “A novel evolutionary deep reinforcement learning algorithm for the influence maximization problem in multilayer social networks,” Chaos, Solitons & Fractals, vol. 200, p. 116967, Nov. 2025, doi:

1016/j.chaos.2025.116967.

P. Liu, L. Li, S. Fang, and Y. Yao, “Identifying influential nodes in social networks: A voting approach,” Chaos, Solitons & Fractals, vol. 152, p. 111309, Nov. 2021, doi: 10.1016/j.chaos.2021.111309.

A. Zareie, A. Sheikhahmadi, and K. Khamforoosh, “Influence maximization in social networks based on TOPSIS,” Expert Systems with Applications, vol. 108, pp. 96–107, Oct. 2018, doi: 10.1016/j.eswa.2018.05.001.

Adesokan, A. B. Rahman, and E. E. Tsiropoulou, “INFLUTRUST: Trust-based influencer marketing campaigns in online social networks,” Future Internet, vol. 16, no. 7, p. 222, jun. 2024, doi: 10.3390/fi16070222.

A. C. Khosroshahi, S. T. Afshord, B. Zarei, and B. Arasteh, “Influence maximization in social networks using improved genetic algorithm,” IEEE Access, Jul., 2025, doi:10.1109/ACCESS.2025.3589189.

J. J. Lotf, M. A. Azgomi, and M. R. Dishabi, “An improved influence maximization method for social networks based on genetic algorithm,” Physica A: Statistical Mechanics and its Applications, vol. 586, p. 126480, Jan. 15, 2022, doi: 10.1016/j.physa.2021.126480.

D. Bucur and G. Iacca, “Influence maximization in social networks with genetic algorithms,” in European Conference on the Applications of Evolutionary Computation, Cham: Springer International Publishing, Mar., 2016, pp. 379–392, doi: 10.1007/978-3-319-77538-8_9.

H. Khavandi, B. N. Moghadam, J. Abdollahi, and A. Branch, “Maximizing the impact on social networks using the combination of PSO and GA algorithms,” Future Generation in Distributed Systems, vol. 5, pp. 1–3 ,Jun., 2023, https://doi.org/10.82553/josc.2025.140309071191740.

A. Maleki Ghalghachi and M. Roayaei, "deep q learning enhanced variable neighborhood search for influence maximi-zation in social networks," International Journal of Web Research, vol. 7, no. 2, pp. 23–36, Apr. 2024, doi: 10.22133/ijwr.2024.459158.1219.