Positive influence maximization and negative influence minimization in signed networks under competitive independent cascade model

Influence maximization refers to the process of identifying a predefined number of nodes within a given social network with the aim of maximizing the spread of influence. Most previous work has focused on unsigned networks, which means the existence of polarity relationships has largely been disregarded. In this work, we define a Sign-aware Influence Maximization (SIM) problem, which involves identification of the seed set that would simultaneously maximize positive influence and minimize negative influence. We begin by considered competitive influence under various dominance mechanisms on SCIC model, which extends the classic Independent Cascade (IC) model by incorporating binary opinions and signed relationships. We then proved that the influence of SIM under the SCIC model is non-monotonic and non-submodular, which implies that simple greedy hill-climbing would be unable to achieve an approximation ratio of 1-1/e in seeking to resolve the SIM problem. We then developed a simulation-based algorithm called Sign-aware Competitive Maximum Influence Arborescence (S-CMIA) to simulate the propagation of influence within a local region. Experiment results demonstrate the superiority of the proposed algorithm over existing methods in resolving the SIM problem in terms of reward.