Online Influence Maximization under Decreasing Cascade Model
Fang Kong Jize Xie Baoxiang Wang Tao Yao Shuai Li
We study online influence maximization (OIM) under a new model of decreasing
cascade (DC). This model is a generalization of the independent cascade (IC)
model by considering the common phenomenon of market saturation. In DC, the
chance of an influence attempt being successful reduces with previous failures.
The effect is neglected by previous OIM works under IC and linear threshold
models. We propose the DC-UCB algorithm to solve this problem, which achieves a
regret bound of the same order as the state-of-the-art works on the IC model.
Extensive experiments on both synthetic and real datasets show the
effectiveness of our algorithm.