Competitive Impact Maximization Propagation Based On Extended Independent Cascade Model

Recently, with the development of mobile communication and web technologies, more and more people start to use the social networks, such as Facebook, Twitter, Line-din, renren, sina weibo etc, which have become the major platform of online communi-cation and spread information. The research of online social networks has attracted much more attention, which includes the space structure of online social networks, the features of information dissemination, the analysis of blog contents and the recommend-ing system of social networks etc.In this thesis, we mainly focused on the problem that how to maximize the com-petitive influence spread. Maximization the influence spread in social network is to find k number of nodes as seeds under certain diffusion model, and which can maximize the spread of information. Kemple proposed two influence spread models, Linear Threshold Model (LTM) and Independent Cascade Model (ICM). The linear threshold model is suitable to describe the behaviour of individual influenced by multiple individuals, and the independent cascade model is suitable for the situation that the behaviour of indi-vidual is just influenced by an independent individual, but these two diffusion models are just suitable for one influence to spread in a social network. However, there are two or more influences competing in a social network in reality. In this paper, we mainly focus on the competitive influence spread, the works of this thesis as follows.(1)We extend the classical independent cascade model, which includes two or more competitive influence spread.(2)We mainly study the problem how to select k seed nodes of one product when the seed set of another product has been given.(3)We prove the objective function is monotone and submodular under the ex-tended independent cascade model, thus the greedy algorithm or cost effective lazy for-ward algorithm can be used to approximate1-1/e of the optimal result.(4)This thesis also implements the proposed algorithm and makes preliminary ex-periments, and the experimental results reveal the feasibility and effectiveness of the algorithm.