Maximization Algorithm Under The Influence Of Linear Threshold Model

In modern marketing field, a company need advertise its products or service through social networks frequently. When a company advertises its products in social networks, there is a problem that how to find some influential individuals for the company under limited budget to test the free samples or service. The company hopes the chosen individuals can influence the largest number of people finally with the strategies of "word-of-mouth" and "viral marketing".This is the initial motivation of influence maximization. Influence maximization becomes hot topics quickly when it is introduced in social networks by Domingos and Richardson firstly. Scientists build models to simulate the influence propagation firstly and then propose algorithms based on the proposed model to solve the influence maximization in social networks. Kempe et.al proposed independent cascade model and linear threshold model and designed greedy algorithm for the problem. The greedy algorithm is the most classical algorithm, which can get1-1/e optimal influence maximization.In this paper, we introduce the theory of the influence maximization firstly, in which we present the independent cascade model (IC) and linear threshold model in detail. Secondly, we focus on the greedy algorithm that is proposed by Kempe et.al. We find it is a limitation that the algorithm can’t be well suited for the influence maximization in large scale social networks because of the high time complexity. We proposed a greedy algorithm for the linear threshold model based on the local network (called LNG). Some experiments are conducted on real social networks and man-made networks to test our algorithm. All the results of the experiments demonstrate that the LNG algorithm consumes much less time (about100-2times) and gets better influence spread effect than the greedy algorithm proposed by Kempe et.al..