关键词: 社会网, 影响传播, 传播时间区间, 营销时间, 饥饿营销

Abstract: Influence maximization is the problem of finding a small set of influential users in a social network that maximizes the expected spread. However, the existing works often ignore the effective propagation time interval between uses, and also don’t take influence of the marketing time on the initial seed users into consideration. This paper uses real action log to determine the effective propagation time interval between users, and proposes an influence power allocating model based on time, called IPAT. According to the IPAT model, this paper proposes an influence maximization problem based on time (IMPT) and a seed set minimization problem in hungry marketing (SMPHM), and proves that these two problems are NP-hard. In order to solve IMPT and SMPHM, this paper proposes two effective approximation algorithms, called A-IMPT and A-SMPHM respectively, and theoretically shows that the approximation ratio of the proposed algorithms A-IMPT and A-SMPHM. The experimental results in several datasets on real social networks validate the effectiveness and efficiency of A-IMPT and A-SMPHM.

Key words: social network, influence propagation, propagation time interval, marketing time, hungry marketing