Influence maximization on signed networks under independent cascade model

摘要

Influence maximization problem is to find a subset of nodes that can make the spread of influence maximization in a social network. In this work, we present an efficient influence maximization method in signed networks. Firstly, we address an independent cascade diffusion model in the signed network (named SNIC) for describing two opposite types of influence spreading in a signed network. We define the independent propagation paths to simulate the influence spreading in SNIC model. Particularly, we also present an algorithm for constructing the set of spreading paths and computing their probabilities. Based on the independent propagation paths, we define an influence spreading function for a seed as well as a seed set, and prove that the spreading function is monotone and submodular. A greedy algorithm is presented to maximize the positive influence spreading in the signed network. We verify our algorithm on the real-world large-scale networks. Experiment results show that our method significantly outperforms the state-of-the-art methods, particularly can achieve more positive influence spreading.