Online Influence Maximization under Decreasing Cascade Model
This work addresses a gap in online influence maximization for social networks by modeling market saturation, but it is incremental as it extends existing models with a new algorithm.
The paper tackles online influence maximization under a decreasing cascade model that accounts for market saturation, where influence success probability decreases with prior failures, and demonstrates that their DC-UCB algorithm achieves a regret bound comparable to state-of-the-art methods for the independent cascade model.
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.