Logo PTI Logo FedCSIS

Proceedings of the 17th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 30

Boosting a Genetic Algorithm with Graph Neural Networks for Multi-Hop Influence Maximization in Social Networks

,

DOI: http://dx.doi.org/10.15439/2022F78

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 363–371 ()

Full text

Abstract. In this paper we solve a variant of the multi-hop influence maximization problem in social networks by means of a hybrid algorithm that combines a biased random key genetic algorithm with a graph neural network. Hereby, the predictions of the graph neural network are used with the biased random key genetic algorithm for a more accurate translation of individuals into valid solutions to the tackled problem. The obtained results show that the hybrid algorithm is able to outperform both the biased random key genetic algorithm and the graph neural network when used as standalone techniques. In other words, we were able to show that an integration of both techniques leads to a better algorithm.

References

  1. D. Kempe, J. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network,” in Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD ’03. New York, NY, USA: Association for Computing Machinery, 2003, p. 137–146. [Online]. Available: https://doi.org/10.1145/956750.956769
  2. W. Chen, A. Collins, R. Cummings, T. Ke, Z. Liu, D. Rincon, X. Sun, Y. Wang, W. Wei, and Y. Yuan, Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate, 2011, pp. 379–390. [Online]. Available: https://epubs.siam.org/doi/abs/10.1137/1.9781611972818.33
  3. S. Tang, “When social advertising meets viral marketing: Sequencing social advertisements for influence maximization,” in Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, ser. AAAI’18/IAAI’18/EAAI’18. AAAI Press, 2018. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/11306
  4. Y. Mei, W. Zhao, and J. Yang, “Influence maximization on twitter: A mechanism for effective marketing campaign,” in 2017 IEEE International Conference on Communications (ICC), 2017, pp. 1–6. [Online]. Available: https://ieeexplore.ieee.org/document/7996805/
  5. J. Li, T. Cai, K. Deng, X. Wang, T. Sellis, and F. Xia, “Community-diversified influence maximization in social networks,” Information Systems, vol. 92, p. 101522, 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0306437920300326
  6. H. Zhuang, Y. Sun, J. Tang, J. Zhang, and X. Sun, “Influence maximization in dynamic social networks,” in 2013 IEEE 13th International Conference on Data Mining, 2013, pp. 1313–1318. [Online]. Available: https://ieeexplore.ieee.org/document/6729640
  7. A. Goyal, W. Lu, and L. V. Lakshmanan, “Simpath: An efficient algorithm for influence maximization under the linear threshold model,” in 2011 IEEE 11th International Conference on Data Mining, 2011, pp. 211–220. [Online]. Available: https://ieeexplore.ieee.org/document/6137225
  8. R. Ni, X. Li, F. Li, X. Gao, and G. Chen, “Fastcover: An unsupervised learning framework for multi-hop influence maximization in social networks,” 2021. [Online]. Available: https://arxiv.org/abs/2111.00463
  9. J. F. Gonçalves and M. G. C. Resende, “Biased random-key genetic algorithms for combinatorial optimization,” Journal of Heuristics, vol. 17, no. 5, pp. 487–525, Oct 2011. [Online]. Available: https://doi.org/10.1007/s10732-010-9143-1
  10. W. Chen, Y. Wang, and S. Yang, “Efficient influence maximization in social networks,” in Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD ’09. New York, NY, USA: Association for Computing Machinery, 2009, p. 199–208. [Online]. Available: https://doi.org/10.1145/1557019.1557047
  11. W. Chen, Y. Yuan, and L. Zhang, “Scalable influence maximization in social networks under the linear threshold model,” in 2010 IEEE International Conference on Data Mining, 2010, pp. 88–97. [Online]. Available: https://ieeexplore.ieee.org/document/5693962
  12. K. Jung, W. Heo, and W. Chen, “Irie: Scalable and robust influence maximization in social networks,” in 2012 IEEE 12th International Conference on Data Mining, 2012, pp. 918–923. [Online]. Available: https://ieeexplore.ieee.org/document/6413832
  13. A. Goyal, W. Lu, and L. V. Lakshmanan, “Celf++: Optimizing the greedy algorithm for influence maximization in social networks,” in Proceedings of the 20th International Conference Companion on World Wide Web, ser. WWW ’11. New York, NY, USA: Association for Computing Machinery, 2011, p. 47–48. [Online]. Available: https://doi.org/10.1145/1963192.1963217
  14. D.-L. Nguyen, T.-H. Nguyen, T.-H. Do, and M. Yoo, “Probability-based multi-hop diffusion method for influence maximization in social networks,” Wireless Personal Communications, vol. 93, no. 4, pp. 903–916, Apr 2017. [Online]. Available: https://doi.org/10.1007/s11277-016-3939-8
  15. M. H. Nguyen, M. H. Hà, D. N. Nguyen, and T. T. Tran, “Solving the k-dominating set problem on very large-scale networks,” Computational Social Networks, vol. 7, no. 1, p. 4, Jul 2020. [Online]. Available: https://doi.org/10.1186/s40649-020-00078-5
  16. Y. Wang, S. Cai, J. Chen, and M. Yin, “A fast local search algorithm for minimum weight dominating set problem on massive graphs,” in Proceedings of the 27th International Joint Conference on Artificial Intelligence, ser. IJCAI’18. AAAI Press, 2018, p. 1514–1522. [Online]. Available: https://www.ijcai.org/proceedings/2018/210
  17. Y. Bengio, A. Lodi, and A. Prouvost, “Machine learning for combinatorial optimization: a methodological tour d’horizon,” 2018. [Online]. Available: https://arxiv.org/abs/1811.06128
  18. H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song, “Learning combinatorial optimization algorithms over graphs,” 2017. [Online]. Available: https://arxiv.org/abs/1704.01665
  19. P. Basuchowdhuri and S. Majumder, “Finding influential nodes in social networks using minimum k-hop dominating set,” in Applied Algorithms, P. Gupta and C. Zaroliagis, Eds. Cham: Springer International Publishing, 2014, pp. 137–151. [Online]. Available: https://link.springer.com/chapter/10.1007/978-3-319-04126-1_12
  20. L. Wu, P. Cui, J. Pei, and L. Zhao, Eds., Graph Neural Networks: Foundations, Frontiers, and Applications. Springer, Singapore, 2022. [Online]. Available: https://link.springer.com/book/10.1007/978-981-16-6054-2
  21. Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, “A comprehensive survey on graph neural networks,” IEEE Transactions on Neural Networks and Learning Systems, vol. 32, no. 1, pp. 4–24, jan 2021. [Online]. Available: https://doi.org/10.1109%2Ftnnls.2020.2978386
  22. K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” 2018. [Online]. Available: https://arxiv.org/abs/1810.00826
  23. P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” 2017. [Online]. Available: https://arxiv.org/abs/1710.10903
  24. P. Erdos and A. Renyi, “On the evolution of random graphs,” Publ. Math. Inst. Hungary. Acad. Sci., vol. 5, pp. 17–61, 1960. [Online]. Available: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.5943
  25. M. López-Ibáñez, J. Dubois-Lacoste, L. Pérez Cáceres, M. Birattari, and T. Stützle, “The irace package: Iterated racing for automatic algorithm configuration,” Operations Research Perspectives, vol. 3, pp. 43–58, 2016. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2214716015300270
  26. J. Leskovec and R. Sosic, “Snap: A general purpose network analysis and graph mining library,” 2016. [Online]. Available: https://arxiv.org/abs/1606.07550
  27. G. Ochoa, K. M. Malan, and C. Blum, “Search trajectory networks: A tool for analysing and visualising the behaviour of metaheuristics,” Applied Soft Computing, vol. 109, p. 107492, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1568494621004154