Document Type



In this paper, we study the problem of targeting a set of individuals to trigger a cascade of influence in a social network such that the influence diffuses to all individuals with the minimum time, given that the cost of initially influencing each in- dividual is with randomness and the budget avail- able is limited. We adopt the incremental chance model to characterize the diffusion of influence, and propose three stochastic programming models that correspond to three different decision criteria. Modi- fied greedy algorithms are presented to solve the pro- posed models efficiently. Experiments are performed to show that the algorithms we present are effective.