Potential Based Influence Maximization Algorithm In A Social Network

Information diffusion and spreading in today's society is very important, and how to make use of connections between people to serve for wide spreading and diffusion is a hotspot in social network analysis. Domingos and Richardson abstracted influence maximization problem:In order to promote some products or concepts, how to choose k influential nodes as the initial spreading set to maximize the final scope of propagation. This optimization problem has been proved to be NP-hard. Kempe and Kleinberg proposed a natural climbing-hill greedy algorithm that chooses the node which could provide the biggest marginal influence. However, we found that climbing-hill greedy strategy is very costly, since it needs to compute the marginal influence for each node to choose the most influential one.In this paper based on the characteristic of model of spreading we propose a new concept called strategy, and based on this concept propose a novel algorithm to solve the influence maximization problem, and we use detailed experiments to verify our approach. The result shows that we can have larger scope of propagation than any other algorithm, and it is cost effetely.Then we discussed two parameters which are included in the spreading model (Linear Threshold Model). Based on the degree and closeness centrality we propose a more accurate formula for evaluating influence between two nodes, and randomize the node specific threshold.