中文摘要：

在线社会网络的发展为市场营销提供了新的机遇和挑战.对于广告投放者来说,面临的问题是如何从一个有n个用户的社会网络中,

英文摘要：

The development of online social networks provides new opportunities and challenges for viral marketing. For a social network with n user-nodes, the advertisers face an important problem, i. e. , how to select k （0〈k〈〈n） influential nodes called seeds, once they become active because of the rewards or free samples, probably the number of the users who know or buy their products is the maximum at the end of diffusion through the word-of-mouth effects. This problem is also called Influence Maximization, or IM for short. Currently in the study of IM problem it is usually assumed that the k selected seeds can be activated. However, maybe there are t（0〈t≤k） seeds that cannot be activated for various reasons in practice. In this situation a new research issue is how to reselect t substitutes to replace the inactive seeds. In this paper, we name this problem as Substitutes Discovery problem in Influence Maximization, or SDIM for short. The problem of SDIM is beneficial to solve the practical problems in marketing, and help advertisers to complete the marketing target more smoothly. For this purpose, we first give a formal definition on SDIM, and propose an optimization function for the problem solving. We prove that SDIM is NP-Hard, and show that our proposed function is of approximation guarantee in developing greedy algorithms for SDIM. In the approach on SDIM, we first filter the nodes according to the scale-free property of social networks and reserve nodes with high degree as candidates. Then we propose three algorithms for SDIM respectively, i. e. , （1） the Global Static Greedy （GSG） algorithm which iust selects t substitutes; （2） the Greedy In Advance （GIA） algorithm which selects t＇（t＇≥t） substitutes in case of there are still inactivated seeds in the substitutes and （3） All Static （AS） algorithm which can improve the efficiency of GSG. As the running time of GSG is unacceptable, we optimize it with the CELF strategy and we call it GSG-CELF in the experiments.