Dynamic Opinion Maximization in Social Networks
Qiang He, Hui Fang, Jie Zhang, Xingwei Wang
Abstract
Opinion Maximization (OM) aims at determining a small set of influential individuals, spreading the expected opinions of an object (e.g., product or individual) to their neighbors through the social relationships and eventually producing the largest opinion spread. In previous studies, once the corresponding nodes are activated, their opinions usually keep unchanged, which fails to capture the real scenarios where the opinion of each node on the object can dynamically change over time. In this view, we propose a Dynamic Opinion Maximization Framework (DOMF) to settle the OM problem, which consists of two parts: dynamic opinion formation and adaptive seeding process. Specifically, we formulate the OM problem by maximizing rational opinions, and prove that: 1) the OM problem within a constant ratio is NP-hard, and 2) the objective function does not satisfy the monotonicity and submodularity properties anymore. To model the dynamic opinion issue, we propose adaptive cooperation model based on Q-learning theory, which is proved to be capable of eventually reaching convergence. Moreover, to dynamically generate the initial seed nodes, we design the Multi-stage Heuristic Algorithm (MHA). Experimental results demonstrate that each component of our model is effective, and the proposed approach improves the rational opinion spread.