A Universal Meta-Heuristic Framework for Influence Maximisation in Hypergraphs

Abstract

Influence maximisation (IM) aims to select a small number of nodes that are able to maximise their influence in a network and covers a wide range of applications. Despite numerous attempts to provide effective solutions in simple networks, higher-order interactions between entities in various real-world systems are usually not taken into account. In this paper, we propose a versatile meta-heuristic approach, Hypergraph Genetic Algorithm (HGA), to tackle the IM problem in hypergraphs, which is based on the concept of genetic evolution. Systematic validations in synthetic and empirical hypergraphs under both simple and complex hypergraph-based contagion models indicate that HGA achieves universal and plausible performance compared to baseline methods. We explore the cause of the excellent performance of HGA through ablation studies and correlation analysis. The findings show that the solution of HGA is distinct from that of other prior methods. Moreover, a closer look at the local topological features of the seed nodes acquired by different algorithms reveals that the selection of seed nodes cannot be based on a single topological characteristic but should involve a combination of multiple topological features to address the IM problem.

Keywords

datamining / deep learning / machine learning / mathematics computing

Acknowledgments

This work was supported by the China Postdoctoral Science Foundation (2024M762809), the National Natural Science Foundation of China (Grant 62473123, 72371224), the Major Project of The National Social Science Fund of China (Grant 19ZDA324), and the Fundamental Research Funds for the Central Universities.

Conflicts of Interest

The authors declare no conflicts of interest.

Data Availability Statement

The codes of our work are available on https://github.com/DDMXIE/A-universal-meta-heuristic-framework-for-influence-maximization-in-hypergraphs.

References

[1] Y. Zhang, M. Lucas, and F. Battiston, “Higher-Order Interactions Shape Collective Dynamics Differently in Hypergraphs and Simplicial Complexes,” Nature Communications 14, no. 1 (2023): 1605, https://doi.org/10.1038/s41467-023-37190-9.

[2] F. Battiston, G. Cencetti, I. Iacopini, et al., Networks Beyond Pairwise Interactions: Structure and Dynamics,” Physics Reports 874 (2020): 1-92, https://doi.org/10.1016/j.physrep.2020.05.004.

[3] H. Wang, C. Ma, H.-S. Chen, Y.-C. Lai, and H.-F. Zhang, “Full Reconstruction of Simplicial Complexes From Binary Contagion and Ising Data,” Nature Communications 13, no. 1 (2022): 3043, https://doi.org/10.1038/s41467-022-30706-9.

[4] X. Liu, H. Qi, W. Wang, X. Zhan, L. Lu, and Z. Ye, “GAWF: Influence Maximization Method Based on Graph Attention Weight Fusion,” International Journal of Modern Physics C (2025): 2542002, https://doi.org/10.1142/s0129183125420021.

[5] S. S. Singh, S. Muhuri, S. Mishra, D. Srivastava, H. Kumar Shakya, and N. Kumar, “Social Network Analysis: A Survey on Process, Tools, and Application,” ACM Computing Surveys 56, no. 8 (2024): 1-39, https://doi.org/10.1145/3648470.

[6] S. S. Singh, S. Kumar, S. Kumar Meena, K. Singh, S. Mishra, and A. Y. Zomaya, “Quantum Social Network Analysis: Methodology, Implementation, Challenges, and Future Directions,” Information Fusion 117 (2024): 102808, https://doi.org/10.1016/j.inffus.2024.102808.

[7] U. Alvarez-Rodriguez, F. Battiston, G. Ferraz de Arruda, et al., Evolutionary Dynamics of Higher-Order Interactions in Social Networks,” Beyond Behavior 5, no. 5 (2021): 586-595, https://doi.org/10.1038/s41562-020-01024-1.

[8] R. Zhang, X. Qu, Q. Zhang, X. Xu, and S. Pei, “Influence Maximization Based on Threshold Models in Hypergraphs,” Chaos: An Interdisciplinary Journal of Nonlinear Science 34, no. 2 (2024): 023111, https://doi.org/10.1063/5.0178329.

[9] M. Xie, X. X. Zhan, C. Liu, and Z. K. Zhang, “An Efficient Adaptive Degree-Based Heuristic Algorithm for Influence Maximization in Hypergraphs,” Information Processing & Management 60, no. 2 (2023): 103161, https://doi.org/10.1016/j.ipm.2022.103161.

[10] S. S. Singh, V. Srivastava, A. Kumar, S. Tiwari, D. Singh, and H.-No Lee , “ ACM Transactions on Asian and Low-Resource Language Information Processing,” ACM Transactions on Asian and Low-Resource Language Information Processing 22, no. 5 (2023): 1-47, https://doi.org/10.1145/3539732.

[11] R. Zhang, X. Qu, Q. Zhang, X. Xu, and P. Sen, “Influence Maximization Based on Threshold Models in Hypergraphs,” Chaos 34, no. 2 (2024): 023111, https://doi.org/10.1063/5.0178329.

[12] F. Amato, V. Moscato, A. Picariello, and G. Sperlí, “Influence Maximization in Social Media Networks Using Hypergraphs,” in International Conference on Green, Pervasive, and Cloud Computing (Springer International Publishing, 2017), 207-221.

[13] M. A. Athul and A. Rajkumar, “Hyper-Imrank: Ranking-Based Influence Maximization for Hypergraphs,” in Proceedings of the 5th Joint International Conference on Data Science & Management of Data (9th ACM IKDD CODS and 27th COMAD), (ACM (Association for Computing Machinery), 2022), 100-104.

[14] J. Zhu, J. Zhu, S. Ghosh, W. Wu, and J. Yuan, “Social Influence Maximization in Hypergraph in Social Networks,” IEEE Transactions on Network Science and Engineering 6, no. 4 (2018): 801-811, https://doi.org/10.1109/tnse.2018.2873759.

[15] Z. Aghaee, M. Mahdi Ghasemi, H. Ahmadi Beni, A. Bouyer, and A. Fatemi, “A Survey on Meta-Heuristic Algorithms for the Influence Maximization Problem in the Social Networks,” Computing 103, no. 11 (2021): 2437-2477, https://doi.org/10.1007/s00607-021-00945-7.

[16] L. Zhang, K. Ma, H. Yang, C. Zhang, H. Ma, and Q. Liu, “A Search Space Reduction-Based Progressive Evolutionary Algorithm for Influence Maximization in Social Networks,” IEEE Transactions on Computational Social Systems 10, no. 5 (2022): 2385-2399, https://doi.org/10.1109/tcss.2022.3189036.

[17] C. Fan, Z. Wang, J. Zhang, J. Zhao, and X. Meng , “Evolving Systems,” Evolving Systems 16, no. 1 (2025): 24, https://doi.org/10.1007/s12530-024-09640-2.

[18] S. Agarwal and S. Mehta , in 7th International Conference on Contemporary Computing (IC3) IEEE (Institute of Electrical and Electronics Engineers), 1-6.

[19] S. S. Singh, K. Singh, A. Kumar, and B. Biswas, “ACO-IM: Maximizing Influence in Social Networks Using Ant Colony Optimization,” Soft Computing 24, no. 13 (2020): 10181-10203, https://doi.org/10.1007/s00500-019-04533-y.

[20] S. S. Singh, A. Kumar, K. Singh, and B. Biswas, “LAPSO-IM: A Learning-Based Influence Maximization Approach for Social Networks,” Applied Soft Computing 82 (2019): 105554, https://doi.org/10.1016/j.asoc.2019.105554.

[21] S. S. Singh, A. Kumar, K. Singh, and B. Biswas, “Concurrency and Computation: Practice and Experience,” Concurrency and Computation: Practice and Experience 32, no. 2 (2020): e5421, https://doi.org/10.1002/cpe.5421.

[22] E. Cunegatti, G. Iacca, and D. Bucur, “Large-Scale Multi-Objective Influence Maximisation With Network Downscaling,” in International Conference on Parallel Problem Solving from Nature (Springer, 2022), 207-220.

[23] A. Chawla and N. Cheney, “Neighbor-Hop Mutation for Genetic Algorithm in Influence Maximization,” in Proceedings of the Companion Conference on Genetic and Evolutionary Computation (ACM (Association for Computing Machinery), 2023), 187-190.

[24] S. Genetti, E. Ribaga, E. Cunegatti, Q. F. Lotito, and G. Iacca, “Influence Maximization in Hypergraphs Using Multi-Objective Evolutionary Algorithms,” in International Conference on Parallel Problem Solving from Nature (Springer, 2024), 217-235.

[25] G. Ferraz de Arruda, G. Petri, P. M. Rodriguez, and Y. Moreno, “Multistability, Intermittency, and Hybrid Transitions in Social Contagion Models on Hypergraphs,” Nature Communications 14, no. 1 (2023): 1375, https://doi.org/10.1038/s41467-023-37118-3.

[26] A. Eriksson, D. Edler, A. Rojas, M. de Domenico, and M. Rosvall, “How Choosing Random-Walk Model and Network Representation Matters for Flow-Based Community Detection in Hypergraphs,” Communications Physics 4, no. 1 (2021): 133, https://doi.org/10.1038/s42005-021-00634-z.

[27] Y. Jean-Gabriel, G. Petri, and T. P. Peixoto, “Hypergraph Reconstruction From Network Data,” Communications Physics 4, no. 1 (2021): 135, https://doi.org/10.1038/s42005-021-00637-w.

[28] N. Horsevad, D. Mateo, R. E. Kooij, A. Barrat, and R. Bouffanais, “Transition From Simple to Complex Contagion in Collective Decision-Making,” Nature Communications 13, no. 1 (2022): 1442, https://doi.org/10.1038/s41467-022-28958-6.

[29] X.-J. Xu, S. He, and Li-J. Zhang, “Dynamics of the Threshold Model on Hypergraphs,” Chaos 32, no. 2 (2022): 023125, https://doi.org/10.1063/5.0075667.

[30] S. Mirjalili, “Genetic Algorithm,” Studies in Computational Intelligence 780 (2019): 43-55, https://doi.org/10.1007/978-3-319-93025-1_4.

[31] J. Chen, M. Feng, D. Zhao, C. Xia, and Z. Wang, “Composite Effective Degree Markov Chain for Epidemic Dynamics on Higher-Order Networks,” IEEE Transactions on Systems, Man, and Cybernetics: Systems 53, no. 12 (2023): 7415-7426, https://doi.org/10.1109/tsmc.2023.3298019.

[32] F. Morone, B. Min, L. Bo, R. Mari, and H. A. Makse, “Collective Influence Algorithm to Find Influencers via Optimal Percolation in Massively Large Social Media,” Scientific Reports 6, no. 1 (2016): 30062, https://doi.org/10.1038/srep30062.

[33] G. Sun and C.-C. Chen, “Infinitely Many Homoclinic Solutions for Sublinear and Nonperiodic Schrödinger Lattice Systems,” Mathematical Problems in Engineering 2021, no. 1 (2021): 6, https://doi.org/10.1186/s13661-020-01479-1.

[34] L. Ma, Z. Shao, X. Li, et al., Influence Maximization in Complex Networks by Using Evolutionary Deep Reinforcement Learning,” IEEE Transactions on Emerging Topics in Computational Intelligence 7, no. 4 (2022): 995-1009, https://doi.org/10.1109/tetci.2021.3136643.

[35] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song, “Learning Combinatorial Optimization Algorithms Over Graphs,” Advances in Neural Information Processing Systems 30 (2017), https://doi.org/10.48550/arXiv.1704.01665.

[36] T. Chen, S. Yan, J. Guo, and W. Wu, “ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning,” IEEE Transactions on Computational Social Systems 11, no. 2 (2023): 2210-2221, https://doi.org/10.1109/tcss.2023.3272331.

[37] 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 (ACM (Association for Computing Machinery), 2009), 199-208.

[38] S. Li and Li Xiang , “ Chaos Solit,” Fractals 174 (2023): 113888, https://doi.org/10.1016/j.chaos.2023.113888.

[39] W. Chen, T. Lin, Z. Tan, M. Zhao, and X. Zhou, “Robust Influence Maximization,” in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM (Association for Computing Machinery), 2016), 795-804.

[40] M. Bouchard, A. L. Jousselme, and P. E. Doré, “A Proof for the Positive Definiteness of the Jaccard Index Matrix,” International Journal of Approximate Reasoning 54, no. 5 (2013): 615-626, https://doi.org/10.1016/j.ijar.2013.01.006.

[41] Y. Zeng, Bo Liu, F. Zhou, and L. Lü, “Hyper-Null Models and Their Applications,” Entropy 25, no. 10 (2023): 1390, https://doi.org/10.3390/e25101390.

[42] Su-Su Zhang, M. Xie, C. Liu, and X.-X. Zhan, “Influence Maximization in Multilayer Networks Based on Adaptive Coupling Degree,” Chaos: An Interdisciplinary Journal of Nonlinear Science 35, no. 3 (2025): 033136, https://doi.org/10.1063/5.0256704.

[43] X. X. Zhan, A. Hanjalic, and H. Wang, “Information Diffusion Backbones in Temporal Networks,” Scientific Reports 9, no. 1 (2019): 6798, https://doi.org/10.1038/s41598-019-43029-5.

[44] M. Gong, J. Yan, B. Shen, L. Ma, and Q. Cai, “Influence Maximization in Social Networks Based on Discrete Particle Swarm Optimization,” Information Sciences 367 (2016): 600-614, https://doi.org/10.1016/j.ins.2016.07.012.

[45] T. Fan, L. Lü, D. Shi, and T. Zhou, “Characterizing Cycle Structure in Complex Networks,” Communications Physics 4, no. 1 (2021): 272, https://doi.org/10.1038/s42005-021-00781-3.