Maximizing the Expected Influence in Face of the Non-progressive Adversary

摘要

In [5], the problem of influence maximization under non-progressive linear threshold model has been considered, and it has been shown that unless the underlying network is acyclic, the direct extension of the classic linear threshold model [16] does not preserve the submodu-larity of the objective function that measures the influence effect. In this paper, we introduce a new feature called activation score to the threshold model, and relax the constraint of the threshold selection to allow the thresholds drawn independently from a distribution whose pdf is non-increasing. We proved that the influence objective function under the proposed model is monotone and submodular for any given information network. Consequently, the advertiser can achieve 1/2-approximation on maximizing the average number of active nodes over a certain period of time, and (1 - 1/e-approximation in expectation with a randomized algorithm. Furthermore, we also consider the extension of the non-progressive threshold model in the two-agents case, in which the similar approximation results can be achieved.