Influence maximization in Independent Cascade model with positive and negative word of mouth

Influence maximization - the problem of finding a small set of seed nodes in social network such that the spread of influence under certain model of cascading influence is maximized- is one of the important problems in viral marketing. For this problem first an influence cascade model should be specified and based on that the influence maximization problem is formulated and solved. Almost all previous influence cascade models ignore negative opinions. They ignore the fact that negative opinions may originate and propagate in populations as much as positive opinions and even they are stronger and more dominant. In this paper we proposed a new model of influence cascade called Independent Cascade with Positive and Negative WOM (ICPN). ICPN has two explicit parameters. First parameter is called quality ratio, which is presented to model the natural behavior of customers in changing their opinions about product/service from positive to negative due to product/service defects and problems; and second one is complaint factor, that is used to model different types of consumer complaining behaviors. ICPN models some important facts that people may encounter in social environment; such as negativity bias, asymmetric behavior of negative and positive WOM, and different types of consumer complaining behaviors. At the end of this paper influence maximization on ICPN is formulated and finally we show that the presented model maintains some nice properties such as submodularity, which allows a greedy approximation algorithm for maximizing the positive influence within a ratio of 1-1/e approximation.