Adaptive overlap penalization and probabilistic modeling in hypergraph influence maximization

• We demonstrate the monotonicity and submodularity of the SICP model, which makes the Greedy algorithm a benchmark with a theoretical performance lower bound in the HyperIM problem. • We propose CC, BCC, ACC, and GIP metrics, along with HACE and HCLI heuristic algorithms. The proposed algorithms balance the effectiveness in selecting an influential seed set and the computational efficiency. • The results of the experiments on large-scale hypergraphs demonstrate the strong practical applicability of HACE and HCLI algorithms, which efficiently select high-influence seeds on large-scale hypergraphs. Influence maximization (IM) algorithms aim to iteratively identify a seed set that could maximize the spreading range. In this paper, we concentrate on the hypergraph influence maximization (HyperIM) problem. The overlapping neighborhood caused by the higher-order interactions leads to an overestimation of the diffusion capability of candidate nodes. Moreover, selecting the candidate node with a high infected probability as a new seed node is low payoff with a small influence range gain. Thus, we develop adaptive metrics and propose two algorithms, i.e., high adaptive contact efficiency (HACE) algorithm and high contact with a low infected probability (HCLI) algorithm. First, we penalize the contribution of the neighborhood of the seed set to the evaluation of the influence gain to the seed set to correct the impact of overlapping influence. Additionally, the proposed HACE algorithm uses the being contacted capability to reveal the infected possibility of candidate nodes, while the proposed HCLI algorithm estimates the global infected probability of nodes. The experiments and analysis on eight real-world hypergraphs demonstrate the better balance of the HACE and HCLI algorithms than the state-of-the-art (SOTA) algorithms in selecting influential seed set and ensuring computational efficiency. Compared with the existing SOTA algorithms, HACE and HCLI run at least ten times faster than SOTA, and at most nearly 70 times faster. On large-scale hypergraphs, the HACE and HCLI algorithms still show great computational efficiency and significantly improved performances compared with other low-time complexity algorithms.