Study On Influence Maximization Problem And Its Diffusion Model In Social Network

There is a martketing strategy in marketing field, named "viral marketing", viral marketing need to select a few experience users in user groups with limit resource, through "world-of-mouth effect" bewteen users, products can atomatic spread among users, at lat it can get influence maximizaton. With the develop of social network study, this problem was introduced into social network and became influence maximization problem, after this problem was proposed, it became a hot study field immediately.At first, this thesis introduced the existing solution of influence maximization, meantime,analysis the advantage and disadvantage of those solution. After studied the weak tie in social network, we find that weak tie can be effectively through information barries between different societies in social network,and making infomation circulate in different societies. This thesis will make use of the tie weak’s advantage, and the greedy thouht to propose a new solution to resolve influence maximization problem,named BWTG algorithm. According to different solution space, we will divide the BWTG algorithm into two different algorithm:BCWTG and BNCWTG algorithm. Secondly, influence maximization problem has two traditional evaluation index:time complexity and the final actived nodes number, but considered the actual situation, we proposed ANNI evaluation index to measure the ratio of profit and pay. Besides, in order to verification the perfomance of the proposed algorithm, we will use the different scale and different type data set to experiment, in the experiment,we will compare the time complexity, the final actived nodes nunber and ANNI with classical Greedy algorithm. According to the experiment result, we find that BCWTG and BNCWTG algorithm have lower time complexity and higher ANNI, the final actived nodes number is lower than Greedy algorithm. But at some conditions, BCWTG and BNCWTG can almost equal to Greedy in actived nodes number.Information diffusion model is the base model of influence maximization,after analyzed the feature of information diffusion in Microblog network, we find that the classical IC model and LT model are hardly used to Microblog network. This thesis design and implement a new information diffusion model, named BIU diffusion model,which is based on IC model. The new diffusion model takes the effect of information in information diffusion into account, so we proposed a new concept named information diffusion power(IDP), to measure the power that information accumulated from diffusion, as a result, the diffusion probability between users in the new model can dynamic change with different time and different information,which is more suitable for the actual situation of information diffusion in Micorblog. At last, we use the Sina Microblog data set to verify the accuracy, compared to IC model, we find BIU model is better than IC model in accuracy.