An adaptive influence pruning algorithm for localized targets influence maximization problem

Abstract As a fundamental dynamical process in real-world systems, spreading is extensively studied in various fields. Several spreading models are proposed to simulate some real scenes, such as information propagation or epidemic contagion. One of the key challenges in the study is known as influence maximization problem, whose goal is to find k nodes that have the greatest influence on all the nodes in the network. The influence maximization problem has been proven to be NP-hard, leaving significant challenges in finding accurate solutions. Substantial effort has been dedicated to addressing this problem. More recently, in cases where spreading only aims to influence a specific node set rather than all the nodes, like promoting cigarette advertisements whose potential customers are only adults, a new problem called localized targets influence maximization problem came up. In this paper, we propose a novel method to address this localized target influence maximization problem based on an influential score discount method, which not only considers the influence of candidate nodes on the target node set, but also takes into account the overall influence of the candidate node set on the target node set. The simulation results show that our method can effectively promote infecting target nodes.