Abstract
We propose a new class of Linear Threshold Model-based information-diffusionmodel that incorporates the formation and spread of negative attitude. We callsuch models negativity-aware.. We show that in these models, the influencefunction is a monotone submodular function. Thus we can use the greedyalgorithm to construct seed sets with constant approximation guarantees, whenthe objective is to select a seed set of fixed size $K$ to maximize totalinfluence. Our models are flexible enough to account for both the features oflocal users and the features of the information being propagated in thediffusion. We analyze an online-learning setting for a multi-roundinfluence-maximization problem, where an agent is actively learning thediffusion parameters over time while trying to maximize total cumulativepositive influence. We assume that in each diffusion step, the agent can onlyobserve whether a node becomes positively or negatively influenced, or remainsinactive. In particular, he does not observe the particular edge that broughtabout the activation of a node, if any, as in the case of most models thatassume Independent Cascade (IC)-based diffusions. This model of feedback iscalled node-level feedback, as opposed to the more common \emph{edge-levelfeedback} model in which he is able to observe, for each node, the edge throughwhich that node is influenced. Under mild assumptions, we develop onlinelearning algorithms that achieve cumulative expected regrets of order$O(T^{-c})$ for any $c<1$ where $T$ is the total number of rounds. These arethe first regret guarantees for node-level feedback models of influencemaximization of any kind. Furthermore, with mild assumptions, this result alsoimproves the average regret of $O(\sqrt{\ln T / T})$ for the edge-levelfeedback models, thus providing a new performance benchmark.