Research On Influence Maximization In Social Networks

In recent years, as the rising and rapid development of social networks, more and more scholars are attracted to study social networks to mine their actual value. The study of influence maximization in social networks has become one of the hot topics. Influence maximization problem is to find a certain number of high influential individuals to maximize the number that is affected by them in social networks. It is always applied in viral marketing.The influence maximization problem is usually studied from two aspects, namely propagation model and algorithm. This paper proposed new models and algorithms. Also, extensive experiments are conducted on two real-world social network datasets, which demonstrate the effectiveness of the proposed models and algorithms. The main work of this paper is presented as follows:(1) The paper proposed the problem of maximizing the positive influence in signed social networks by studying the characteristics of signed social networks and the significance of positive influence in viral marketing. Considering the attitude of users and relationships between nodes, a new propagation model named LT-A is proposed based on LT model. Subsequently, this paper proves that the influence spread function is monotonous and submodular under the new model and the positive influence maximization problem is NP-hard, hence the greedy algorithm can be used to solve the problem. Based on the above descriptions, an algorithm named LT-A Greedy is proposed to solve the problem, and then the effectiveness of the model and algorithm is validated by conducting experiments on real-world signed social network datasets.(2) The greedy algorithm has a long execution time, so it is not suitable for the large scale social networks. In view of this problem, a new heuristic algorithm named Three Degrees of Influence heuristic Algorithm(TDIA) is present, which is based on Three Degrees of Influence Rule(TDIR). TDIR is a law followed by influence propagation in social networks, and it will be more obvious with the increase of social network scale. TDIA is a heuristic algorithm in which it selected nodes with high TDI value as seeds based on the characteristic of TDIR. Experiment results show that the TDIA has much shorter execution time than greedy algorithm and its accuracy is close to that of the greedy algorithm.