Boosting a genetic algorithm with graph neural networks for multi-hop influence maximization in social networks

• Autorzy: Chacón Sartori Camilo , Blum Christian

Identyfikatory

DOI

10.15439/2022F78

• Konferencja: Federated Conference on Computer Science and Information Systems (17 ; 04-07.09.2022 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

computer science; social networking; spread spectrum communication; prediction algorithm; boosting; graph neural networks; genetic algorithm

PL

informatyka; sieci społecznościowe; komunikacja; widmo rozproszone; wzmacnianie; sieci neuronowe; graf; algorytm genetyczny

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2022
• Tom: Vol. 30
• Strony: 363--371
• Opis fizyczny: Bibliogr. 27 poz., il., tab., wz.

Twórcy

autor

Chacón Sartori Camilo

• Artificial Intelligence Research Institute (IIIA-CSIC) Campus of the UAB, Bellaterra, Spain

autor

Blum Christian

• Artificial Intelligence Research Institute (IIIA-CSIC) Campus of the UAB, Bellaterra, Spain

Bibliografia

• 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

Uwagi

1. This paper was supported by grant PID2019-104156GB-100 funded by MCIN/AEI/10.13039/501100011033.

2. Track 6: 15th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).