Influence Maximization

Opinion Dynamics with
Varying Susceptibility to Persuasion

In this work we study a social influence problem using a popular opinion dynamics model. Specifically, we ask the following question.

Given an opinion dynamics model, and a set of agents, each of whom has an innate opinion that reflects her core value on a topic and a susceptibility to persuasion parameter measuring her propensity for changing her opinion, how should we alter the agents’ susceptibility in order to maximize/minimize the total sum of opinions at equilibrium?

Specifically, each agent i \in V is associated with an innate opinion s_i \in [0,1], and a susceptibility to persuasion parameter \alpha_i \in (0,1].  We assume that each node i updates its opinion according to the following dynamics: x_i(t+1) = \alpha_i s_i + (1-\alpha_i) \frac{ \sum\limits_{j \in N(i)} x_j(t) }{\deg(i)}. It is well known that it converges to an equilibrium. Our goal is to optimize an objective of the equilibrium over the set of parameters \{\alpha_i\}_{i \in V}.


  • Model. We formalize and study the following questions. Given a positive integer k, find a set of nodes S \subseteq V, |S| \leq k, and set the resistance parameters \alpha_i \in [\ell, u] for each i \in S, in order to maximize /minimize the total sum of opinions at equilibrium. We refer to the case k \geq n as the unbudgeted opinion maximization problem and the case k < n as the  budgeted opinion maximization problem.
  • Algorithms. We prove that both the maximization and minimization versions of the unbudgeted opinion optimization are solvable in polynomial time using convex optimization. On the contrary, the budgeted problem is NP-hard. Furthermore, in contrast to prior work that studies opinion maximization at the innate opinion level, the objective is neither sub- nor super-modular. For this problem, we propose a greedy heuristic.
  • Experiments. We evaluate our proposed methods on several real-world datasets, including a Twitter network where users express their opinions on the Delhi legislative assembly elections.


%d bloggers like this: