An efficient adaptive degree-based heuristic algorithm for influence maximization in hypergraphs |
| |
| Institution: | 1. Alibaba Research Center for Complexity Sciences, Hangzhou Normal University, Hangzhou 311121, China;2. Computer, Electrical and Mathematical Sciences & Engineering, King Abdullah University of Science and Technology, Saudi Arabia;3. Web Sciences Center, University of Electronic Science and Technology of China, China;1. Faculty of Social and Political Sciences, Institute of Social Sciences, Life Course and Social Inequality Research Centre, Lausanne University, Switzerland;2. Institute of Computational Linguistics, Zurich University, Switzerland |
| |
| Abstract: | Influence maximization (IM) has shown wide applicability in immense fields over the past decades. Previous researches on IM mainly focused on the dyadic relationship but lacked the consideration of higher-order relationship between entities, which has been constantly revealed in many real systems. An adaptive degree-based heuristic algorithm, i.e., Hyper Adaptive Degree Pruning (HADP) which aims to iteratively select nodes with low influence overlap as seeds, is proposed in this work to tackle the IM problem in hypergraphs. Furthermore, we extend algorithms from ordinary networks as baselines. Results on 8 empirical hypergraphs show that HADP surpasses the baselines in terms of both effectiveness and efficiency with a maximally 46.02% improvement. Moreover, we test the effectiveness of our algorithm on synthetic hypergraphs generated by different degree heterogeneity. It shows that the improvement of our algorithm effectiveness increases from 2.66% to 14.67% with the increase of degree heterogeneity, which indicates that HADP shows high performance especially in hypergraphs with high heterogeneity, which is ubiquitous in real-world systems. |
| |
| Keywords: | Influence maximization Hypergraphs Spreading dynamics Complex networks |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
