Abstract：The influence maximization problem in hypergraphs has wide-ranging applications across various fields. Existing methods either inadequately address the redundancy of influence between nodes or only rely on a single metric for initial node ranking, which may fail to accurately capture the true propagation values of nodes. To simultaneously consider both influence redundancy between nodes and the actual propagation values of nodes, this paper proposes a Low Redundant Hypergraph based on the Genetic Algorithm (LR-HGA), which takes into account these two aspects in the selection and crossover operations of genetic algorithm. Experimental results on six real hypergraph networks using the SI propagation model defined on hypergraphs show that the seed set obtained by this algorithm generally has a wider influence spread compared to state-of-the-art benchmark algorithms.
[1] LI Y C, FAN J, WANG Y H, et al. Influence maximization on social graphs: a survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(10): 18521872. [2] LÜL Y, ZHOU T. Link prediction in complex networks: a survey[J]. Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 11501170. [3] 吴俊, 邓烨, 王志刚, 等. 复杂网络瓦解问题研究进展与展望[J]. 复杂系统与复杂性科学, 2022, 19(3): 113. WU J, DENG Y, WANG Z G, et al. Status and Prospects on Disintegration of Complex Networks[J]. Complex Systems and Complexity Science, 2022, 19(3): 113. [4] LIU X M, LI D Q, MA M Q, et al. Network resilience[J]. Physics Reports, 2022, 971: 1108. [5] WANG Y, LI H, ZHANG L, et al. Identifying influential nodes in social networks: centripetal centrality and seed exclusion approach[J]. Chaos Solitons Fractals, 2022, 162:112513. [6] GAMBUZZA LV, DI PATTI F, GALLO L, et al. Stability of synchronization in simplicial complexes[J]. Nature Communications, 2021, 12(1): 1255. [7] ZHANG Y, LUCAS M, BATTISTON F. Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes[J]. Nature Communications, 2023, 14(1): 1605. [8] TORRES L, BLEVINS AS, BASSETT D, et al. The why, how, and when of representations for complex systems[J]. SIAM Review, 2021, 63(3): 43585. [9] CASTELLANO C, FORTUNATO S, LORETO V. Statistical physics of social dynamics[J]. Reviews of Modern Physics, 2009, 81(2): 591. [10] 徐越, 刘雪明. 基于三元闭包模体的关键节点识别方法[J]. 复杂系统与复杂性科学, 2023, 20(4): 3339. XU Y, LIU X M. Method for identifying critical nodes based on closed triangle motifs[J]. Complex Systems and Complexity Science, 2023, 20(4): 3339. [11] MA A, RAJKUMAR A. Hyper-IMRANK: ranking-based influence maximization for hypergraphs[DB/OL].[2024-02-02]. https://qiniu.pattern.swarma.org/pdf/arxiv/2006.05645.pdf [12] 吴英晗, 李明达, 胡枫. 基于熵的多属性决策超网络重要节点识别方法[J]. 复杂系统与复杂性科学, 2023, 20(4): 4046. WU Y H, LI M D, HU F. A Multi-attribute decision-making method based on entropy to identify important nodes in hypernetworks[J]. Complex Systems and Complexity Science, 2023, 20(4): 4046. [13] AKTAS M E, JAWAID S, GOKALP I. Influence maximization on hypergraphs via similarity-based diffusion[C]//IEEE International Conference on Data Mining Workshops. Orlando: IEEE, 2022: 11971206. [14] ZHU J, ZHU J, GHOSH S, et al. Social influence maximization in hypergraph in social networks[J]. IEEE Transactions on Network Science and Engineering, 2018, 6(4): 801811. [15] ANTELMI A, CORDASCO G, SPAGNUOLO C, et al. Social influence maximization in hypergraphs[J]. Entropy, 2021, 23(7): 796. [16] XIE M, ZHAN X X, LIU C, et al. An efficient adaptive degree-based heuristic algorithm for influence maximization in hypergraphs[J]. Information Processing & Management, 2023, 60(2): 103161. [17] XIE M, ZHAN X X, LIU C, et al. A universal meta-heuristic framework for influence maximization in hypergraphs[EB/OL].[20231024]. https://doi.org/10.48550/arXiv.2310.15465. [18] KING ZA, LU J, DRÄGER A, et al. BiGG Models: A platform for integrating, standardizing and sharing genome-scale models[J]. Nucleic Acids Research, 2016, 44(D1): D515D522. [19] AMBURG I, VELDT N, BENSON AR. Fair Clustering for Diverse and Experienced Groups[J]. arXiv:2006.05645, 2020. [20] AMBURG I, VELDT N, BENSON AR. Diverse and experienced group discovery via hypergraph clustering[C]//Proceedings of the 2022 SIAM International Conference on Data Mining. Philadelphia: SIAM, 2022: 145153. [21] CHODROW PS, VELDT N, BENSON AR. Generative hypergraph clustering: from blockmodels to modularity[J]. Science Advances, 2021, 7(28): eabh1303. [22] BORGS C, BRAUTBAR M, CHAYES J, et al. Maximizing social influence in nearly optimal time[C]//Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms. Portland: SIMA, 2014: 946957. [23] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation[J], Nature, 2015, 524(7563): 6568.
