The Design And Analysis Of Algorithm On The Influence Maximization Problem In Social Networks

In recent years, with the growing popularity of electronic equipments and the continuous development of social networks, the relationship between people becomes more and more close and convenient. And, the message passing among people becomes more and more rapid and easy. Based on this, how to use the relationnetworks between people for information passing has been the focus of researchers.Originated from "word-of-mouth effect" and "viral marketing", it appears the influence maximization problem. This problem requiresto establish the information diffusion model and designalgorithms according to the structural characteristics of networks and the properties of information propagation, so that we can maximize the information spread in the network.Influence maximization is the problem of finding the most influential set of nodes in a social network which can maximize the spread of influence. The study is not only of theoretical significance, but also of promising applications. The influence maximization problem has important significance in many aspects, like advertising, marketing, message passing, and research cooperation.This paper begins with the introduction of the origin of the influence maximization problem and the current research situation. Then, it follows the related background theory and knowledge. In particular, we focus on the research of two kinds of the basic diffusion models, i.e., the Independent cascade(IC) model and the linear threshold(LT) model. Meanwhile, the traditional heuristic algorithm and greedy algorithm are analyzed and compared. According to the structural characteristics of networks and properties of information passing, we introduce thenotion of influence factor to reflectthe time sensitivity of information and indirect transitivity of influence. Then we use thesemi-definiteprogramming(SDP) method to design an approximation algorithm for the influence maximization problem, and propose a heuristic and a greedy algorithm based on maximum influence factor(MIF) for the problem.Finally, we conduct several experiments on real social networks. We analyze the experimental results from two aspects:the dissemination effect and the transfer efficiency.Meanwhile, we compare the MIF algorithm with several traditional heuristic algorithms(including the High-Degree heuristic, the Distance heuristic, etc) and the greedy algorithm. The experimental results show that the influence result of the MIF algorithm is better thanthat of the mentioned heuristic algorithms, and is close to that of the greedy algorithm. However, compared with the greedy algorithm, the MIF algorithm significantly reduces the computational cost. At the same time, we use Gephi to visualize the experimental results, by which we can observe the results(that is the active nodes in the network) more intuitively.