In the problem of influence maximization in information networks, theobjective is to choose a set of initially active nodes subject to some budgetconstraints such that the expected number of active nodes over time ismaximized. The linear threshold model has been introduced to study the opinioncascading behavior, for instance, the spread of products and innovations. Inthis paper, we we extends the classic linear threshold model [18] to capturethe non-progressive be- havior. The information maximization problem under ourmodel is proved to be NP-Hard, even for the case when the underlying networkhas no directed cycles. The first result of this paper is negative. In general,the objective function of the extended linear threshold model is no longersubmodular, and hence the hill climbing approach that is commonly used in theexisting studies is not applicable. Next, as the main result of this paper, weprove that if the underlying information network is directed acyclic, theobjective function is submodular (and monotone). Therefore, in directed acyclicnetworks with a specified budget we can achieve 1/2 -approximation onmaximizing the number of active nodes over a certain period of time by adeterministic algorithm, and achieve the (1 - 1/e )-approximation by arandomized algorithm.
展开▼
