Influence Maximization In Networks

The problem of influence maximization is to select a set of K nodes from a social network so that the spread of influence(e.g., information, idea, opinion etc) is maximized over the network. Influence maximization is a fundamental research problem in social networks; it is able to promote the analysis and modeling of influence propagation. And influence maximization is useful in a large number of applications such as word-of-mouth marketing.Influence maximization has attracted significant research work. However, previous research work overlooks two important factors. One is novelty decay phenomenon in influence propagation, i.e., repeated exposures will have diminishing influence on users. Another one is influence loss due to node failure. This thesis will study the effects of the two important factors on influence maximization. The main work is as follows:(1) Analyze the effect of novelty decay on influence propagation on real-life datasets, develop a fitting function to characterize the effect, and formulate the problem of influence maximization with novelty decay. Different from the conventional influence propagation model, the influence function with novelty decay is neither monotone nor submodular; it means that the greedy algorithm and the existing methods for computing the influence of seed set are inapplicable. To this end, this thesis develops a restricted greedy algorithm and a dynamic pruning optimization, proposes two methds for computing the influence of seed set. Experiments conducted on four real-life datasets demonstrate the efficiency and effectiveness of the proposed approaches.(2) Based on the analysis of the effects of node failure on influence maximization, this thesis defines the problem of influence maximization with node failure as a constrained nonlinear optimization problem. Since the greedy algorithm can not solve the new type of influence maximization problem, this thesis proposes a constrained simulated annealing algorithm and further improve its performance through efficiently estimating the influence loss. This thesis also provides experimental results over four real-life datasets in support.