Modeling Influence Diffusion over Signed Social Networks

In offline or online worlds, many social systems can be represented as signed social networks including both positive and negative relationships. Although a variety of studies on signed social networks have been conducted motivated by the great application value of unique polarity characteristics, how to model the process of influence propagation over signed social networks is still an important problem that remains pretty much open. Currently, a few studies extended traditional diffusion models (e.g., Independent Cascade model and Linear Threshold model) from unsigned social networks to signed social networks for estimating positive and negative influence of user sets. However, all of above extension models are stochastic and descriptive models. In order to ensure the accuracy of estimated influence, existing models require a significant number of Monte-Carlo simulations which are very time-consuming and not scalable. Aiming at this issue, we propose the Polarity-related Linear Influence Diffusion (PLID) model which can quickly and accurately calculate polarity-related influence of user sets without simulations. To validate effectiveness and efficiency of our proposed model, we make use of our PLID model to solve the positive influence maximization problem in signed social networks under rigorous mathematical proofs. Extensive experiments demonstrate that our PLID model and approximation algorithm significantly outperform state-of-the-art methods in terms of positive influence spread and running time, using Epinions and Slashdot datasets.