Opinion Dynamics with Varying Susceptibility to Persuasion
Rediet Abebe1 , Jon Kleinberg1 , David Parkes2 , and Charalampos E. Tsourakakis3
1

Cornell University
Harvard University
3
Boston University

arXiv:1801.07863v1 [cs.SI] 24 Jan 2018

2

Abstract
A long line of work in social psychology has studied variations in people’s susceptibility to
persuasion – the extent to which they are willing to modify their opinions on a topic. This body
of literature suggests an interesting perspective on theoretical models of opinion formation by
interacting parties in a network: in addition to considering interventions that directly modify
people’s intrinsic opinions, it is also natural to consider interventions that modify people’s
susceptibility to persuasion. In this work, we adopt a popular model for social opinion dynamics,
and we formalize the opinion maximization and minimization problems where interventions
happen at the level of susceptibility. Specifically, we ask:
Given an opinion dynamics model, and a set of agents, each of whom has an innate
opinion that reflects the agent’s intrinsic position on a topic and a susceptibilityto-persuasion parameter measuring the agent’s propensity for changing his or her
opinion, how should we modify the agents’ susceptibilities in order to maximize (or
minimize) the total sum of opinions at equilibrium?
We study both the version when there is not a budget on the number of agents that we can
target, and when there is. For the former, we provide a polynomial time algorithm for both the
maximization and the minimization formulations. In contrast, we show that budgeted version
is NP-hard, but unlike prior work focusing on opinion maximization, our objective function is
neither sub- nor super-modular in the target set. For this version, we propose a greedy heuristic
that we compare experimentally against natural baseline methods. On the experimental side, we
perform an empirical study of our proposed methods on several datasets, including a Twitter
network with real opinion estimates. Our experimental findings show that our proposed tools
outperform natural baselines and can achieve a multi-fold effect on the total sum of opinions in
the network.

1

Introduction

A rich line of empirical work in development and social psychology has studied people’s susceptibility
to persuasion. This property measures the extent to which individuals are willing to modify their
opinions in reaction to the opinions expressed by those around them, and it is distinct from the
opinions they express. Research in the area has ranged from adolescent susceptibility to peer
pressure related to risky and antisocial behavior [4, 17, 19, 42, 46, 45] to the role of susceptibility to
persuasion in politics [21, 36, 38]. Individuals’ susceptibility to persuasion can be affected by specific
strategies and framings aimed at increasing susceptibility [9, 10, 11, 30, 34, 43, 44]. For instance,
1

if it is known that an individual is receptive to persuasion by authority, one can adopt a strategy
that utilizes arguments from official sources and authority figures to increase that individuals’
susceptibility to persuasion with respect to a particular topic.
Modifying network opinions has far-reaching implications including product marketing, public
health campaigns, the success of political candidates, and public opinions on issues of global interest.
In recent years, there has also been work in Human Computer Interaction focusing on persuasive
technologies, which are designed with the goal of changing a person’s attitude or behavior [20, 28, 30].
This work has shown that not only do people differ in their susceptibility to persuasion, but that
persuasive technologies can also be adapted to each individual to change their susceptibility to
persuasion.
Despite the long line of empirical work emphasizing the importance of individuals’ susceptibility
to persuasion, to our knowledge theoretical studies of opinion formation models have not focused on
interventions at the level of susceptibility. Social influence studies have considered interventions
that directly act on the opinions themselves, both in discrete models (as in the work of Domingos
and Richardson [18], Kempe et al. [31], and related applications [1, 6, 27, 29]) and more recently in
a model with continuous opinions (in the work of Gionis et al. [25]).
In this work, we adopt an opinion formation model inspired by the work of DeGroot [16] and
Friedkin and Johnsen [22], and we initiate a study of the impact of interventions at the level of
susceptibility. In this model, each agent i is endowed with an innate opinion si ∈ [0, 1] and a
parameter representing susceptibility to persuasion, which we will call the resistance parameter,
αi ∈ (0, 1]. The innate opinion si reflects the intrinsic position of agent i on a certain topic, while
αi reflects the agent’s willingness, or lack thereof, to conform with the opinions of neighbors in the
social network. We term αi the agent’s “resistance” because a high value of αi corresponds to a
lower tendency to conform with neighboring opinions. According to the opinion dynamics model,
the final opinion of each agent i is a function of the social network, the set of innate opinions, and
the resistance parameters, determined by computing the equilibrium state of a dynamic process of
opinion updating. For more details on the model, see Section 2. We study the following natural
question:
Problem 1. Given an opinion dynamics model, and a set of agents, each of whom has
an innate opinion that reflects the agent’s intrinsic position on a topic, and a resistance
parameter measuring the agent’s propensity for changing his or her opinion, how should we
change the agents’ susceptibility in order to maximize (or minimize) the total sum of opinions
at equilibrium?
We call the set of agents whose susceptibility parameters we change the target-set. In most
influence maximization or opinion optimization settings, the case where there are no constraints on
the size of the target-set is generally not interesting since it often involves simple solutions that
modify a parameter to a specific value across essentially all agents. This is not the case in our
setting – the unbudgeted version remains technically interesting, and the optimal solution does
not generally involve targeting all agents. We will therefore consider both the unbudgeted and the
budgeted versions of this problem.
The Present Work. Within the opinion dynamics model we study, we formalize the problem
of optimizing the total sum of opinions at equilibrium by modifying the agents’ susceptibility to
persuasion. We formalize both the maximization and minimization versions of the problems, as well

2

as an unbudgeted, and a budgeted variation of these problems.
For the unbudgeted maximization and minimization problems we provide efficient polynomial
time algorithms. In contrast to the unbudgeted problem, the budgeted problem is NP-hard. We
show that our objective is neither sub- nor super-modular. We prove that there always exists an
optimal solution where the resistance parameters αi are set to extreme values (see Theorem 6). We
use this theorem as our guide to provide a heuristic that greedily optimizes the agents’ susceptibility
to persuasion.
We evaluate our unbudgeted and budgeted methods on real world network topologies, and on
both synthetic and real opinion values. In particular, we use a Twitter network and opinion data on
the Delhi legislative assembly elections based on work of De et al. [15] to see how our methods can
potentially modify the final outcome of opinion dynamics. Our findings indicate that intervening at
the susceptibility level can significantly affect the total sum of opinions in the network.

2

Model

Let G = (V, E) be a simple, undirected graph, where V = [n] is the set of agents and E is the set
of edges. Each agent i ∈ V is associated with an innate opinion si ∈ [0, 1], where higher values
correspond to more favorable opinions towards a given topic and a parameter measuring an agent’s
susceptibility to persuasion αi ∈ (0, 1], where higher values signify agents who are less susceptible
to changing their opinion. We call αi the resistance parameter. The opinion dynamics evolve in
discrete time according to the following model, inspired by the work of [16, 22]:
P
xj (t)
xi (t + 1) = αi si + (1 − αi )

j∈N (i)

.
(1)
deg(i)
Here, N (i) = {j : (i, j) ∈ E} is the set of neighbors of i, and deg(i) = |N (i)|. It is known that this
dynamics converges to a unique equilibrium if αi > 0 for all i ∈ V [14]. The equilibrium opinion
vector z is the solution to a linear system of equations:
z = (I − (I − A)P )−1 As,

(2)

where A = Diag (α)) is a diagonal matrix where entry Ai,i corresponds to αi and P is the random
1
walk matrix, i.e., Pi,j = deg(i)
for each edge (i, j) ∈ E(G), and zero otherwise. We call zi the
expressed opinion of agent i.
Definition 2. Given the opinion dynamics model (1), a social network G = (V, E), and the set of
parameters {si }i∈V , {αi }i∈V , we define the total sum of opinions at the equilibrium as
def
f (s, α) = ~1T z = ~1T (I − (I − A)P )−1 As.

Our goal is to optimize the objective f (s, α), by choosing certain αi parameters in a range [`, u],
where 0 < ` ≤ u. We consider the following problems:
Problem 3 (Opinion Maximization). Given a positive integer k, find a set of nodes S ⊆
V, |S| ≤ k, and set the resistance parameters αi ∈ [`, u] for each i ∈ S, in order to maximize
the total sum of opinions f (s, α). We refer to the case k ≥ n as the unbudgeted opinion
maximization problem and the case k < n as the budgeted opinion maximization problem.

3

Similarly, we define the minimization version.
Problem 4 (Opinion Minimization). Given a positive integer k > 0, find a set of nodes
S ⊆ V, |S| ≤ k, and set the resistance parametes αi ∈ [`, u] for each i ∈ S, in order to
minimize the total sum of opinions f (s, α). The unbudgeted and budgeted versions are
defined as above.
Previous work has focused on modifying the agents’ innate or expressed opinions rather than
their resistance parameters. We observe that targeting agents at the level of susceptibility versus at
the level of innate opinions can lead to very different results, as the next example shows.
Example 5. Consider the following network on n nodes, where each node is annotated with
the values (si , αi ), and consider interventions at the level of either innate opinions or resistance
parameters with the goal of maximizing the sum of expressed opinions.
(1, c )

(0,)

(0,)

(0,)

(0,)

Suppose  is a value arbitrarily close to 0. As we increase c, the total sum of opinions in the
network tends to 0. If we can target a single agent, then an optimal intervention at the level of
innate opinions changes the innate opinions of one of the leaves to 1. At equilibrium, the total sum
n
≈ 1. However, if we can target at the level of
of opinions (for small  and large c) is close to n−1
susceptibility, then we change the central node’s αi from c to 1. Then, at equilibrium the total sum
of opinions becomes f (s, α) = n(1 − φ(, c)) for a function φ() going to 0 as  goes to 0 and c goes
to infinity. The improvement is O(n), and hence very large compared to the intervention at the
level of innate opinions.
We can construct an instance on the same graph structure to show the contrast in the opposite
direction as well, where targeting at the level of innate opinions cause a very large improvement
compared to targeting at the level of susceptibility. Starting with the example in the figure, change
the innate opinion of the center node to be 0 and the resistance parameter to be 1. In equilibrium,
the sum of expressed opinions is 0. If we can target agents at the level of innate opinions, then
changing the innate opinion of the center node to be 1 will lead to a sum of expressed opinions of n,
whereas we cannot obtain a sum of expressed opinions greater than 0 by targeting at the level of
susceptibility.
As a first general result about our model, we prove that there always exists an optimal solution
that involves extreme values for the resistance parameters αi .
Theorem 6. There always exists an optimal solution for the opinion optimization problems where
αi = ` or αi = u.
Proof. Our proof relies on a random-walk interpretation of opinion dynamics [24, 26]. Before we
give our proof, we describe this connection between absorbing random walks and opinion dynamics
for completeness. Gionis et al. [26] consider a random walk with absorbing states on an augmented
graph H = (X, R) that is constructed as follows:
4

(i) The set of vertices X of H is defined as X = V ∪ V , where V is a set of n new nodes such
that for each node i ∈ V there is a copy σ(i) ∈ V ;
(ii) The set of edges R of H includes all the edges E of G, plus a new set of edges between each
node i ∈ V and its copy σ(i) ∈ V . That is, R = E ∪ E, and E = {(i, σ(i)) | i ∈ V };
(iii) Finally, the weights of all edges in R are set to 1, assuming that G is unweighted.
A key observation in [26] is that the opinion vector at the equilibrium can be computed by performing
the following absorbing random walk on the graph H. To determine the expressed opinion of node
i ∈ V , we start a random walk from i; with probability 1 − αi we follow an incident edge chosen
uniformly at random from E, and with probability αi we follow the edge from i to σ(i), ending the
walk. If the walk continues to a node j, we perform the same type of step — chosing an edge of E
incident to j with probability 1 − αj , and moving to σ(j) with probability αj — and iterate. It is
shown in [26] that this walk represents the opinion dynamics process in the following sense: the
expressed opinion zi∗ of node i in the equilibrium of the process is equal to the expected value of the
innate opinion sj over all endpoints σ(j) of the walk starting from i.
This implies that the equilibrium opinion zi∗ of node i is given by the following general form:
zi∗ = αi si + (1 − αi )pii zi∗ + (1 − αi )(1 − pii )yi ,

(3)

where pii is the probability that the random walk that starts at i returns again to i before absorption,
and yi is the expected opinion if the random walk gets absorbed to a node σ(j) 6= σ(i).
We assume, without loss of generality, that the opinion optimization problem at hand is the
opinion maximization problem, although the proof can easily be adopted to the opinion minimization
case. Suppose we have a solution for the opinion maximization problem such that αi lies strictly
between `i and ui . We wish to show that setting αi to be either `i or ui will yield a sum of expressed
opinions that is at least as large. Proceeding in this way one node at a time, we will get a solution
in which all αi are either `i or ui .
By solving Equation (3) for zi∗ we obtain,
zi∗ =

(1 − αi )(1 − pii )
αi
si +
yi .
1 − (1 − αi )pii
1 − (1 − αi )pii

(4)

Therefore zi∗ is the convex combination of two probabilities si , yi . Since we wish to maximize zi∗ , if
αi
(1 − αi )(1 − pii )
si ≤ yi we need to minimize
; otherwise we will minimize
. Note that
1 − (1 − αi )pii
1 − (1 − αi )pii
x
the function g(x) =
for x ∈ [`i , ui ] is monotone increasing, and therefore maximized
1 − (1 − x)pii
at x = ui and minimized at x = `i . Therefore, optimality is obtained by setting αi to be either `i or
ui . This yields a sum of expressed opinions that is at least as large as the original solution.

3

Unbudgeted Opinion Optimization

In this section, we show that when there are no constraints on the size of the target-set, both the
opinion maximization and minimization problems can be solved in polynomial time.

5

3.1

Unbudgeted Opinion Minimization

Recall from Section 2, A = Diag (α)) is a diagonal matrix where entry Ai,i corresponds to αi and P
is the random walk matrix.
We formalize the unbudgeted opinion minimization problem as follows.
minimize ~1T z
subject to z = (I − (I − A)P )−1 As
A  `I
A  uI

(5)

We show that this problem can be solved in polynomial time.
Theorem 7. The Opinion Minimization formulation (5) is solvable in polynomial time.
Before we proceed with the proof of Theorem 7, we rewrite the objective of formulation (5) in a
way that is convenient for algebraic manipulation. Define X = A−1 . Then,
(I − (I − A)P )−1 A = (I − (I − A)P )−1 (A−1 )−1 = (I − (I − A)P )−1 X −1
= (X − (X − XA)P )−1 = (X − (X − I)P )−1 .
Therefore, we rewrite our original formulation to optimize over the set of diagonal matrices X
whose entries lie in [ u1 , 1` ].
minimize ~1T (X − (X − I)P )−1 s
subject to X  u1 I
X  1` I
X diagonal

(6)

Lemma 8. The following set is convex:
K = {X ∈ Rn×n : X diagonal,

1
1
≤ xii ≤ for all i ∈ [n]}.
u
`

Proof. Let X1 , X2 ∈ K, λ ∈ (0, 1). Matrix Y = λX1 + (1 − λ)X2 is clearly diagonal, and any
diagonal entry yii = λx1ii + (1 − λ)x2ii satisfies,
1
1
≤ yii ≤ .
u
`
Therefore, Y ∈ K, which implies the claim.
Lemma 9. All eigenvalues of matrix Z = (X − (X − I)P ), X ∈ K are strictly positive reals (in
general Z is not symmetric). Furthermore, Z is positive definite, i.e., for any y ∈ Rn the quadratic
form y T Zy is non-negative.
Notice that the above two statements are not simultaneously true for non-symmetric matrices: a
non-symmetric matrix with all eigenvalues positive is not necessarily positive definite. On the other
hand, if a non-symmetric matrix is positive definite, all its eigenvalues have to be positive.
6

Proof. First we prove that all eigenvalues are real. We provide a sequence of similarity transformations that prove Z = (X − (X − I)P ) is similar to a symmetric matrix. To simplify notation, when
U = R−1 AR, where R is a diagonal matrix, we write U ≡ A.
1

1
X − (X − I)P ≡ X − D+ 2 (X − I)D−1 A D− 2
1

1

= X − (X − I)D− 2 AD− 2
1

1

1

1

≡ X − (X − I)− 2 (X − I)D− 2 AD− 2 (X − I)+ 2
1

1

1

1

= X − (X − I)+ 2 D− 2 AD− 2 (X − I)+ 2
Since the adjacency matrix A is symmetric, the latter matrix is also symmetric, and therefore has
real eigenvalues.
To show all eigenvalues are positive, we invoke the Gershgorin circle theorem. Notice that
Zii = xii (under our assumption that the graph is simple) and the sum of non-diagonal entries in
row i is −(xii − 1). Therefore, every eigenvalue of Z lies in at least one of the Gershgorin discs:
|λ − xii | ≤ (xii − 1) ⇔ 1 ≤ λ ≤ 2xi − 1.
We now show that the quadratic form associated with Z is non-negative. Recall first that xii ≥ 1
and deg(i) ≥ 1, therefore
1
1
+
≥ 2.
deg(i) deg(j)
For any y ∈ Rn ,
y T Zy = y T (X − (X − I)P )y = y T Xy − y T (X − I)y
n
n
X
X
yi X
2
=
xii yi −
(xii − 1)
yj
deg(i)
i=1
i=1
j∼i


n
n
X
X
X
y
i
=
yi2 +
(xii − 1) yi2 −
yj 
deg(i)
i=1
i=1
j∼i


n
X
X
yi yj
yi yj
2
2
2
+
)
=
yi +
(xii − 1) yi + yj − (
deg(i) deg(j)
i=1

≥

n
X

(i,j)∈E(G)

X

yi2 +

i=1

(xii − 1)(yi2 + yj2 − 2yi yj ) +

(i,j)∈E(G),yi yj ≥0

X


(xii − 1)

yi2

+

yj2

(i,j)∈E(G),yi yj <0

=

n
X
i=1

X

yi2 +


|yi yj |
|yi yj |
+(
+
)
deg(i) deg(j)

(xii − 1)(yi − yj )2 +

(i,j)∈E(G),yi yj ≥0

X


(xii − 1)

(i,j)∈E(G),yi yj <0

≥ 0
7

yi2

+

yj2


|yi yj |
|yi yj |
+(
+
)
deg(i) deg(j)

We proceed to prove that the objective is convex.
Theorem 10. The matrix (X − (X − I)P )−1 is a convex function of X ∈ K.
Proof. Let X1 , X2 ∈ K, and let Zi := (Xi − (Xi − I)P ) for i = 1, 2. Also, fix λ ∈ (0, 1), and let
Z(λ) = λZ1 + (1 − λ)Z2 . We prove the following statement, that implies that (X − (X − I)P )−1 :
λZ1−1 + (1 − λ)Z2−1  (λZ1 + (1 − λ)Z2 )−1 .
Since Z1 , Z2 are positive definite, we obtain that for any y ∈ Rn
y T Z(λ)y = λy T Z1 y + (1 − λ)y T Z2 y ≥ 0,
so Z(λ) is positive definite, and so is Z(λ)−1 ,
ZZ −1 = I ⇒

dZ −1
dZ −1
dZ −1
dZ
Z +Z
=0⇒
= −Z −1 Z −1 .
dλ
dλ
dλ
dλ

By differentiating twice Z(λ) with respect to λ, we also obtain
derivative of the inverse is given by,

d2 Z
dλ2

= 0. Therefore, the second

−1
d2 Z −1
dZ −1 dZ −1
dZ
dZ
−1 dZ dZ
=
−
Z
−
Z
= 2Z −1 Z −1 Z −1 .
2
dλ
dλ dλ
dλ dλ
dλ
dλ
Pick any non-zero vector u and consider following pair of vector/matrix valued functions:

dZ dZ −1
u
and
ϕ(λ) = uT Z −1 (λ)u.
dλ dλ
The second derivative of ϕ(λ) satisfies the following inequality:
v(λ) =

d2 Z −1
u = 2v T (λ)Z −1 (λ)v(λ) ≥ 0,
dλ2
is positive definite. Therefore ϕ(λ) is a convex function of λ for λ ∈ (0, 1). Thus, for any
ϕ(λ) = uT

since Z −1
such λ

(1 − λ)ϕ(0) + λϕ(1) − ϕ(λ) ≥ 0


⇐⇒ uT (1 − λ)X −1 + λY −1 − ((1 − λ)X + λY )−1 u ≥ 0.

(7)
(8)

This implies that λZ1−1 + (1 − λ)Z2−1 − (λZ1 + (1 − λ)Z2 )−1 is positive semidefinite, and thus our
claim that (X − (X − I)P )−1 is a convex function holds.

T
We can prove that (X − (X − I)P )−1
is also a convex function in a similar way. We therefore
obtain the following corollary:
Corollary 11. For any fixed y ∈ Rn , we can optimize the quadratic forms,


T 
y
y T (X − (X − I)P )−1 y, y T (X − (X − I)P )−1 + y T (X − (X − I)P )−1
over all diagonal matrices X ∈ K in polynomial time.
8

We can use off-the-shelf interior point methods for convex optimization, see [8, Chapter 11]. To
conclude the proof of Theorem 7, we need to prove that our objective can be brought in the quadratic
form of Corollary 11.
Proof of Theorem 7. For simplicity, let Z = (X − (X − I)P ). We consider the quadratic,
(s + ~1)T Z −1 (s + ~1) = sT Z −1 s + ~1T Z −1~1 + ~1T Z −1 s + sT Z −1~1
= sT Z −1 s + n + ~1T Z −1 s + sT ~1 ⇔
~1T Z −1 s = (s + ~1)T Z −1 (s + ~1) − sT Z −1 s − C
= h(s + ~1)(s + ~1)T − ssT , Z −1 i − C,
|
{z
}
Q

n
P

si is a constant that does not depend on the variable diagonal matrix X.
P
Furthermore, Q is symmetric, i.e., Q = QT . Let Q = ni=1 νi qi qiT be the eigendecompositon of Q.
We observe that
where C = n +

i=1

trace(Z

−1

Q) = trace Z

−1

n
X

!!
νi qi qiT

= trace

i=1

=

n
X

=

!
νi Z

−1

qi qiT

i=1

νi trace Z −1 qi qi


T

=

i=1
n
X

n
X

n
X

νi trace qiT Z −1 qi



i=1

i=1

1
= trace
2

n
X




1
νi qiT Z −1 + (Z −1 )T qi
2
i=1
 
Z −1 + (Z −1 )T Q

νi qiT Z −1 qi =


(*)

In (*), we used the fact that for any square matrix A
1
xT Ax = xT (A + AT )x.
2
Therefore, we conclude that our objective is equivalent to minimizing
1
h(s + ~1)(s + ~1)T − ssT , Z −1 + (Z −1 )T i,
2
subject to X ∈ K. By Corollary 11, we conclude that the opinion minimization problem is convex,
and thus solvable in polynomial time.

3.2

Unbudgeted Opinion Maximization

We also prove that the opinion maximization problem can also be solved in polynomial time using
machinery that we have already developed. We state the problem as:

9

maximize ~1T (X − (X − I)P )−1 s
subject to X  u1 I
X  1` I
X diagonal
Theorem 12. We can solve the opinion maximization problem by invoking our opinion minimization
algorithm using as our vector of initial opinions 1 − s.
Proof. By Lemma 9 and since P ~1 = ~1, for any X ∈ K,
(X − (X − I)P )~1 = X~1 − (X − I)~1 = I~1 = ~1
⇔ (X − (X − I)P )−1~1 = ~1.
Therefore, the opinion minimization objective that uses as an initial opinions the vector ~1 − s
becomes
~1T (X − (X − I)P )−1 (~1 − s) = ~1T (X − (X − I)P )−1~1−
~1T (X − (X − I)P )−1 s = n − ~1T (X − (X − I)P )−1 s.
Therefore, minimizing this objective is equivalent to maximizing ~1T ∗ (X − (X − I)P )−1 s subject to
X ∈ K.
We close this section by answering the following question: how much can our intervention
increase the total sum of opinions in a network? As we have seen, Example 5 shows a way of
modifying resistance parameters to create an unbounded increase in the sum of expressed opinions.
Thus, the optimal modification to the resistance parameters can produce arbitrarily large increases
to this sum.

4

Budgeted Opinion Optimization

We now consider the setting where there is a constraint on the size of the target-set. That is, we
want to identify a set T ⊆ V of size k such that changing the resistance parameters of agents in T
optimally maximizes (resp. minimizes) the sum of expressed opinions in equilibrium. Recall from
Section 2 that we denote by f (s, α) the sum of expressed opinions under the given vector of innate
values and resistance parameters. We denote by f (s, α, T ) the sum of expressed opinions where
we can set the αi of the agents i ∈ T optimally. We simply refer to this by f (T ) when there is no
ambiguity.
The objective function for finding the optimal target-set for opinion maximization is therefore
max|T |=k f (T ), and, respectively, min|T |=k f (T ) for opinion minimization. Note, the objective
function is monotone in the target-set since we can always set the choice of αi to be the original
αi for any node i ∈ T . But, can we use submodular optimization tools for our budgeted opinion
optimization problems (Problems 3, and 4)? We show that, unlike in the case in other standard
opinion optimization or influence maximization settings, neither submodularity nor supermodularity
holds. We prove this result for the case of opinion maximization, but similar claims can be made for
the minimization problem too by setting s = 1 − s.
10

Example 13. Consider the complete graph on three nodes where s = (1, 0, 0) and α = (0.1, 0.1, 0.1).
The total sum of opinions in equilibrium is 1. Suppose we are allowed to set resistance values in
[0.001, 1]. Given target-sets T 0 ⊆ T and x ∈
/ T 0 , submodularity would give that,
f (T ∪ {x}) − f (T ) ≤ f (T 0 ∪ {x}) − f (T 0 ).
Set T = {1, 2}, T 0 = {1}, and x = {3}. For each of these sets, the optimal solution would set α1 = 1,
α2 = 0.001 and α3 = 0.001. Submodularity would require
f (1, 2, 3) − f (1, 2) ≤ f (1, 3) − f (1),
but with these numbers, the left-hand side of the inequality is 0.191 and the right-hand is 0.168;
this submodularity does not hold.
To show that supermodularity does not hold, set T = {1}, T 0 = ∅, and x = {3}. Then,
supermodularity would require that
f (3) − f (∅) ≤ f (1, 3) − f (1),
the left-hand side of the inequality is 1.493 and the right-hand side is 0.168.
Hence, our objective function is neither submodular nor supermodular in the target set.
Highlighting a difference with the unbudgeted version, we show that Problems 3, and 4 are
NP-hard by a reduction from the vertex cover problem on d-regular graphs. To prove this, we adapt
a construction for a different opinion maximization problem given by [26] in the context of their
model. We only present the proof for the opinion maximization problem; as the example above, the
proof can easily be adapted for opinion minimization as well.
Theorem 14. The budgeted opinion maximization (and similarily opinion minimization) problem
is NP-hard.
Proof. Given a d-regular graph G = (V, E) and an integer K, the vertex cover problem asks whether
there exists a set of nodes S of size at most K such that S is a vertex cover. An instance of the
decision version of opinion maximization consists of a graph G0 , where each agent i has an internal
opinion si and resistance parameter αi , an integer k and a threshold θ. The solution to this decision
version is “yes” if and only if there exists a set T of size at most k whose resistance values we can
optimally set such that ` ≤ α ≤ u and f (T ) ≥ θ. We first prove this hardness result by letting the
αi of the target-set be anywhere in [0, 1]. We then prove that the reduction continues to hold for
the case where αi ∈ (0, 1].
Suppose we are given an instance of the vertex cover problem for regular graphs. We construct
an instance of the decision version of√the opinion maximization problem as follows: set G0 =
(V ∪ V 0 , E ∪ E 0 ) where V 0 consists of 2 d nodes for each node i ∈ V (called duplicate nodes). The
set E 0 is the edges of the form (i, i0 ) joining nodes in V to their corresponding duplicate nodes. We
set si = 1 and αi = 0 for all i ∈ V . We also set√si0 = 0 for all i0 ∈ V 0 . For the set of duplicate
nodes, we set the resistance value of half (that is, d nodes) to be 1 and the other half to be 0. We
call the former the
√ stubborn√duplicate nodes, and the latter the flexible duplicate nodes. We set
k = K and θ = ( d + 1)k + d(n − k) d+d√d . This gives us a decision version of each of the opinion
maximization problem.

11

We now want to show that a set T of at most k nodes in V is a vertex cover of G if and only if
we can set the resistance values of the nodes in T (as a subset of G0 ) to satisfy the decision version
of the opinion maximization problem.
Suppose that T is a vertex cover of G. Then, it satisfies the decision problem above by setting
the αi of the agents in T to be 1. Indeed, the agents i ∈ T will have expressed opinions of 1, as will
all the flexible duplicate nodes neighboring the agents in T . All other nodes j ∈ V will have all d of
their neighbors in V having opinion
√ 1 since T is a vertex cover. Therefore, they will have a final
expressed opinion d+d√d . Their d flexible duplicate nodes will take on this value as well, while
their stubborn
duplicate
nodes will maintain their innate opinion of 0. Therefore, we get a final
√
√
sum of ( d + 1)k + d(n − k) d+d√d . Therefore, T corresponds to a target-set whose resistance we
can set optimally such that f (T ) ≥ θ.
To see the reverse direction, we want to show that if T is not a vertex cover of G, then we
cannot set the resistance values of agents in T such that f (T ) ≥ θ. If T is not a vertex cover, then
there exists an edge (i, j) ∈ E such that i, j ∈
/ T . Therefore, the expressed opinion of both i and j
d−1
√ . All the agents in T will maintain their high opinion of 1, and all other nodes
will be at most d+
d
` 6= i, j will have an expressed opinion of at most
into account the duplicate nodes, we have,

d√
,
d+ d

√
√
f (T ) ≤ ( d + 1)k + d(n − k − 2)

by the same argument as above. Taking

√ d−1
d
√ +2 d
√ < θ.
d+ d
d+ d

Let θ0 denote the middle term in this chain of inequalities; we have thus shown that if G does not
have a k-node vertex cover, then for any set T of at most k nodes, we have f (T ) ≤ θ0 < θ.
What remains to show is there exists an optimal target-set that consists of only nodes in V and
not in V 0 , where we assume that this target-set is at most of size k ≤ n for n = |V |. Denote the
optimal target-set in by T ∗ . Suppose there is a node i0 ∈ T which is a node in V 0 . Let i0 be adjacent
to a node i ∈ V . If i0 is a flexible duplicate node, then it is clear that the expressed opinions of both
i0 and i will be 1, if we include i in the target-set instead. (Or simply remove i0 from the target-set
if i is already in T .) Suppose i0 is a stubborn duplicate node. First, assume that i ∈ T . Consider
T = T \{i0 } ∪ {j}, where j ∈
/ T . The expressed opinion of j, and therefore of all its corresponding
flexible duplicate nodes, with T as the target-set is at most d+d√d . With j in the target-set, the
expressed opinion goes to 1. We therefore need to show that the loss in opinion from removing i0
from the target-set,
gainby adding j to the target-set. Indeed, it is straightforward
 is at most
 the
√
d√
to verify that 1 ≤ 1 − d+ d
d+1 .

Now, consider i0 is a stubborn duplicate node and i ∈
/ T . We compare T to T 0 = T \{i0√
} ∪ {i}.
0
Suppose there are h nodes adjacent to i in V with resistance parameter 0. (In particular, h ≥ d+1.)
The expressed opinion of i with T as the target-set is at most d+2√d d−h , and is shared by all h of
the duplicate nodes. Under T 0 , i will have an expressed opinion of 1, as will all h of the nodes with
α = 0, except for node i0 which will now have resistance value of 1. Thus, we need to show that


d
d
√
√
1−
≤h 1−
.
d+2 d−h
d+ d−h
This holds since h ≥ 1.
We now show how to modify the proof for the case in which the stubbornness values belong to
the interval [ε, 1] rather than [0, 1], for some ε > 0. The key point is that when we view f (T ) as
12

a function of the stubbornness parameters in the network G0 constructed in the reduction, it is a
continuous function. Thus, if we let γ = θ − θ0 > 0, we can choose ε > 0 small enough that the
following holds. If we take all nodes i in the previous reduction with αi = 0, and we push their
stubbornness values up to αi = ε, then (i) if T is a k-node vertex cover in G, we have f (T ) ≥ θ − γ/3,
and (ii) if G does not have a k-node vertex cover, for any set T of at most k nodes, we have
f (T ) ≤ θ0 + γ/3. Since θ − γ/2 lies between these two bounds, it follows that with stubbornness
values in the interval [ε, 1], there is a k-node vertex cover T in the original instance if and only if
there is a set T in the reduction to opinion maximization with f (T ) ≥ θ − γ/2. This completes the
proof with stubbornness values in the interval [ε, 1].
In light of this hardness result, and inspired by Theorem 6, we propose a greedy heuristic for
the budgeted opinion optimization problems. The version shown below is for opinion maximization,
but can be converted to the opinion minimization problem by setting s = 1 − s. In each round, the
heuristic chooses the node that gives the largest marginal gain f (T ∪ {v}) − f (T ). The algorithm
requires O(n3 ) time to compute f (∅) using standard Gauss-Jordan elimination for matrix inversion,
and then it performs O(nk) loops, that each requires O(n2 ) time. To see why O(n2 ) time suffices
instead of the straightforward O(n3 ) time of matrix inversion, suppose that we know (I −(I −A)P )−1
and we wish to change the stubbornness of node i from αi to be 1. The new stubbornness
matrix
√
is A0 = A + xi xTi , where xi ∈ Rn has xi (j) = 0 for all j 6= i, and xi (i) = 1 − αi . Instead of
computing the inverse (I − (I − A0 )P )−1 , we can use the Sherman-Morrison formula for the rank-1
update (I − (I − A)P + xi (xTi P ))−1 , which leads to a run-time of O(kn3 ) instead of O(kn4 ).
Greedy Heuristic
Require: k ≥ 1
1: S ← ∅
2: Compute f (∅) = (I − (I − A)P )−1 As
3: for i ← 1 to k do
4:
max ← −∞
5:
for v ∈ V \T do
6:
Compute f (T ∪ {v})
7:
if f (T ∪ {v}) − f (T ) ≥ max then
8:
winner← v
9:
max ← f (T ∪ {v}) − f (T )
10:
end if
11:
end for
12:
T ← T ∪ winner
13: end for
14: Return T .
In the next section, we implement this heuristic and compare its performance against some
natural baselines on real and synthetic values on real-world networks.

5

Experimental results

Experimental setup. Table 1 shows the datasets we used in our experiments. We use several
datasets as sources of real network topologies. The Twitter dataset is associated with real-world
13

opinions obtained as described by De et al. [15]. For our purposes, we take the first expressed
opinion by each agent to be the innate opinion, and we normalize these values, which fall in [−1, 1]
in the original dataset, to fall in [0, 1]. The sum of the innate opinions is 347.042 with a mean of
0.633, while the sum of the final expressed opinions observed in the network during this period is
367.149 with a mean of 0.670, suggesting that the sentiment shifted in a positive manner. For a
detailed description of the dataset collection, see [15].
Name
Monks
Karate
LesMiserables
NetScience
Email Network
Twitter

n
18
33
77
379
986
548

m
41
78
254
914
16064
3638

Description
Social
Social
Co-occurance
Collaboration
Social
Social Media

Source
[41]
[48]
[32]
[39]
[33, 47]
[15]

Table 1: Description of datasets.
For the remaining networks, we set the innate opinions uniformly at random in [0, 1] for the
budgeted experiments and uniformly at random as well as power law for the unbudgeted experiments.
We set the slope for the power law distribution to be 2. For all graphs, we select each resistance
parameter αi uniformly at random in [0.001, 1].
For the budgeted version of our problem, we present the performance of the heuristics for the
three largest networks (i.e., Twitter, Email Network, and NetScience). The results are qualitatively
similar for the rest of the networks. We compare the performance of our greedy heuristic with two
baselines that output a set of k nodes whose resistance parameter is set to 1. Baseline I chooses k
agents with the highest innate opinions (ties broken arbitrarily). Baseline II assigns to each node i
P si
a score score(i) = deg(i)
2m ×
sj and chooses the k agents with the highest score. The intuition
j∈N (i)

for this baseline is that we would like to pick a node that has a high centrality and relatively high
opinion compared to their neighbors and fix this agent to have an α of 1. We consider budget values
k in {1, 2, · · · , 100}. We compare the sum of expressed opinions without intervention as well as the
outputs of the greedy heuristic and the two baselines. All simulations run on a laptop with 1.7 GHz
Intel Core i7 processor and 8GB of main memory.1
Baseline I
Require: k ≥ 1
1: Let s1 ≥ s2 ≥ . . . ≥ sn .
2: Return T ← {1, . . . , k}
1
The code for the budgeted and unbudgeted experiments can be found in https://github.com/redabebe/
opinion-optimization and https://github.com/tsourolampis/opdyn-social-influence, respectively.

14

Baseline II
Require: k ≥ 1
1: Let score(i) ←
2:
3:

deg(i)
2m

×

P

si
j∈N (i) sj

for all i ∈ V .

Sort the nodes such that score(1) ≥ score(2) ≥ . . . ≥ score(n)
Return T ← {1, . . . , k}

Experimental findings. Figures 1(a), (b), (c) show the results obtained by our greedy heuristic,
and the two baseline methods for the Twitter, Email, and NetScience networks respectively. All
methods achieve a significant improvement compared to having no interventions even for small
values of k. Recall that for the Twitter network, we use estimates of real opinions for the agents.
Homophily by opinions is observed and impacts the relatively higher performance of these baselines
compared to the Email and NetScience networks where the opinion values are randomly generated.
Baseline I and Baseline II show similar performance for the Twitter and NetScience networks. One
underlying explanation for the relative under-performance of Baseline II compared to Baseline I
in the Email network is that this network has skewed degree distribution which might inflate the
scores of higher degree nodes. We note that the run times for the Twitter, Email, and NetScience
networks are 12.0, 3.4, and 111.5 seconds per k, respectively.

Figure 1: Total sum of opinions at equilibrium vs. budget k for the budgeted opinion maximization
problem using no intervention, Baseline I, Baseline II, and our greedy heuristic for (a) Twitter, (b)
Email, and (c) NetScience networks respectively.
Table 2 shows our experimental findings for the unbudgeted opinion minimization, and maximization problems. We report the total sum ~1T s of innate opinions, the total sum ~1T z of opinions
at equilibrium (no intervention), the total sum ~1T zmin of opinions produced by our minimization
algorithm, and the total sum ~1T zmax of opinions produced by our maximization algorithm. The
resistance parameters for each of the networks are chosen uniformly at random from [0, 1]. We then
let ` = 0.001 and u = 1, which serve as an upper and lower bound for the resistance parameters.
Note that the reported values are the average of 5 trials. In addition to the synthetically generated
opinion values reported above, we also run the opinion optimization algorithms on the Twitter
dataset using the opinions from [15] and get a sum of opinions 117.31 for the opinion minimization
problem and 363.87 for the opinion maximization problem. The main observation for here is that
the effect of our intervention can be significant for both the opinion maximization and opinion
minimization problems. Indeed, the sum of opinions in the case of the former is over an order of
magnitude larger than the case of the latter for many of these networks.

15

G
Monks
Karate
LesMis
NetScience
Email
Twitter

~1T s
9.34
16.70
38.81
188.39
414.62
289.29

s ∼ U [0, 1]
~1T z
~1T zmin
8.12
1.22
17.83
1.97
40.5
4.21
191.79 17.19
440.96 388.39
260.96 241.86

~1T zmax
16.38
32.47
74.00
319.59
495.44
270.21

~1T s
11.88
22.29
48.68
257.58
283.62
193.09

s ∼Power Law(α)
~1T z
~1T zmin
11.29
5.62
21.07
5.27
52.11
8.44
249.88 64.43
565.86 91.18
359.85 62.00

~1T zmax
16.68
33.56
75.84
340. 54
610.72
379.00

Table 2: Results for unbudgeted algorithm for two different distributions (uniform, and power law
with slope α equal to 2) of innate opinions s: the total sum ~1T s of innate opinions , the total sum
~1T z of opinions at equilibrium (no intervention), the total sum ~1T zmin of opinions produced by
our minimization algorithm, and the total sum ~1T zmax of opinions produced by our maximization
algorithm.

6

Related Work

To our knowledge, we are the first to consider an optimization framework based on opinion dynamics
with varying susceptibility to persuasion. In the following we review briefly some work that lies
close to ours.
Susceptibility to Persuasion. Asch’s conformity experiments are perhaps the most famous study
on the impact of agents’ susceptibility to change their opinions [5]. This study shows how agents
have different propensities for conforming with others. These propensities are modeled in our context
by the set of parameters α. Since the work of Asch, there have been various theories on peoples’
susceptibility to persuasion and how these can be affected. A notable example is Cialdini’s Six
Principles of Persuasion, which highlight reciprocity, commitment and consistency, social proof,
authority, liking, and scarcity, as key principles which can be utilized to alter peoples’ susceptibility
to persuasion [9, 10]. This framework, and others, have been discussed in the context of altering
susceptibility to persuasion in a variety of contexts. Crowley and Hoyer [11], and McGuire [34]
discuss the ‘optimal arousal theory’, i.e., how novel stimuli can be utilized for persuasion when
discussing arguments.
Opinion Dynamics Models. Opinion dynamics model social learning processes. DeGroot
introduced a continuous opinion dynamics model in his seminal work on consensus formation [16].
A set of n individuals in society start with initial opinions on a subject. Individual opinions are
updated using the average of the neighborhood of a fixed social network. Friedkin and Johnsen
[22] extended the DeGroot model to include both disagreement and consensus by mixing each
individual’s innate belief with some weight into the averaging process. This has inspired a lot of
follow up work, including [2, 3, 7, 13, 23, 25].
Optimization and Opinion Dynamics. Bindel et al. use the Friedkin-Johnsen model as a
framework for understanding the price of anarchy in society when individuals selfishly update their
opinions in order to minimize the stress they experience [7]. They also consider network design
questions: given a budget of k edges, and a node u, how should we add those k edges to u to
optimize an objective related to the stress? Gionis et al. [25] use the same model to identify a set
of target nodes whose innate opinions can be modified to optimize the sum of expressed opinions.
16

Finally, in work concurrent with ours, Musco et al. adopt the same model to understand which
graph topologies minimize the sum of disagreement and polarization [37] .
Inferring opinions and conformity parameters. While the expressed opinion of an agent is
readily observable in a social network, both the agent’s innate opinion and conformity parameter are
hidden, and this leads to the question of inferring them. Such inference problems have been studied
by Das et al. [12, 14]. Specifically, Das et al. give a near-optimal sampling algorithm for estimating
the true average innate opinion of the social network and justify the algorithm both analytically and
experimentally [14]. Das et al. view the problem of susceptibility parameter estimation as a problem
in constrained optimization and give efficient algorithms, which they validate on real-world data
[12]. There are also several studies that perform experiments to study what phenomena influence
opinion formation and how well these are captured by existing models [13, 35].
Social Influence. The problem we focus on is related to influence maximization, a question that
draws on work of Domingos and Richardson [18, 40] and Kempe et al. [31]. Recent work by Abebe
et al. considers the problem of influence maximization where agents who reject a behavior contribute
to a negative reputational effect against it [1]. There is also a rich line of empirical work at the
intersection of opinion dynamics and influence maximization including [27, 29, 6] that argues that
agents adopt products to boost their status.

7

Conclusion

Inspired by a long line of empirical work on modifying agents’ propensity for changing their opinions,
we initiate the study of social influence by considering interventions at the level of susceptibility to
persuasion. For this purpose, we adopt a popular opinion dynamics model, and seek to optimize the
total sum of opinions at equilibrium in a social network. We consider both opinion maximization and
minimization, and focus on two variations: a budgeted and an unbudgeted version. We prove that
the unbudgeted problem is solvable in polynomial time (in both its maximization and minimization
version). For the budgeted version, on the other hand, in contrast to a number of other opinion or
influence maximization formalisms, the objective function is neither submodular nor supermodular.
Computationally, we find that it is NP-hard. In light of this, we introduce a greedy heuristic for the
budgeted setting, which we show has desirable performance on various real and synthetic datasets.
There are various open directions suggested by this framework. The first is whether we can
provide any approximation algorithms for the budgeted setting. Through simulations, we also
note that while not giving optimal results, local search algorithms yield satisfactory results in
finding target-sets in the unbudgeted setting. Exploring this connection might yield insights into
the opinion formation process. The interface of influence maximization and opinion maximization
is also under-explored, and yet another interesting line of work is to note equivalences for models
under the two frameworks, and when they depart from one another. Many of the questions explored
in Section 6 can also be posed in this setting including budgeted edge-addition and removal with
susceptibility to persuasion, and understanding the influence of opinions in speed of convergence to
equilibrium. Finally, we can also pose the question of opinion optimization when there is a budget
on the total sum of changes we can make to the resistance values of nodes, rather than on the
number of agents who can be in a target set.

17

Acknowledgements
Rediet Abebe was supported in part by a Google scholarship, a Facebook scholarship, and a Simons
Investigator Award, and Jon Kleinberg was supported in part by a Simons Investigator Award, an
ARO MURI grant, a Google Research Grant, and a Facebook Faculty Research Grant.
We thank the authors of [15] for sharing the Twitter dataset in Section 5.
Charalampos Tsourakakis would like to thank his newborn son Eftychios for the happiness he
brought to his family.

References
[1] Rediet Abebe, Lada Adamic, and Jon Kleinberg. Mitigating overexposure in viral marketing.
In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence. AAAI, 2018.
[2] Daron Acemoglu and Asuman Ozdaglar. Opinion dynamics and learning in social networks.
Dynamic Games and Applications, 1(1):3 – 49, 2011.
[3] Daron Acemoglu and Asuman Ozdaglar. Opinion dynamics and learning in social networks.
Dynamic Games and Applications, 1(1):3 – 49, Mar 2011.
[4] Porter allen, Joseph P., Mary Frances R., and F. Christy McFarland. Leaders and followers in
adolescent close friendships: Susceptibility to peer influence as a predictor of risky behavior,
friendship instability, and depression. Development and Psychopathology, 18(1):155 – 172, 2006.
[5] Solomon E. Asch. Opinions and social pressure. Scientific American, 193(5):31 – 35, November
1955.
[6] Jonah Berger and Chip Heath. Where consumers diverge from others: Identity signaling and
product domains. Journal of Consumer Research, 34(2):121 – 134, 2007.
[7] David Bindel, Jon Kleinberg, and Sigal Oren. How bad is forming your own opinion? In
Proceedings of the 2011 IEEE 52Nd Annual Symposium on Foundations of Computer Science,
FOCS ’11, pages 57 – 66, Washington, DC, USA, 2011. IEEE Computer Society.
[8] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press,
2004.
[9] Robert B. Cialdini. Influence, Science and Practice. Allyn and Bacon, 2001.
[10] Robert B. Cialdini. The science of persuasion. Scientific American Mind, 2004.
[11] Ayn E. Crowley and Wayne D. Hoyer. An integrative framework for understanding two-sided
persuasion. Journal of Consumer Research, 20(4):561 – 574, 1994.
[12] Abhimanyu Das, Sreenivas Gollapudi, Arindham Khan, and Renato Paes Leme. Role of
conformity in opinion dynamics in social networks. In Proceedings of the Second ACM Conference
on Online Social Networks, COSN ’14, pages 25 – 36, New York, NY, USA, 2014. ACM.

18

[13] Abhimanyu Das, Sreenivas Gollapudi, and Kamesh Munagala. Modeling opinion dynamics in
social networks. In Proceedings of the 7th ACM International Conference on Web Search and
Data Mining, WSDM ’14, pages 403 – 412, New York, NY, USA, 2014. ACM.
[14] Abhimanyu Das, Sreenivas Gollapudi, Rina Panigrahy, and Mahyar Salek. Debiasing social
wisdom. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, KDD ’13, pages 500 – 508, New York, NY, USA, 2013. ACM.
[15] Abir De, Sourangshu Bhattacharya, Parantapa Bhattacharya, Niloy Ganguly, and Soumen
Chakrabarti. Learning a linear influence model from transient opinion dynamics. In Proceedings
of the 23rd ACM International Conference on Conference on Information and Knowledge
Management, pages 401–410. ACM, 2014.
[16] Morris H. DeGroot. Reaching a consensus. Journal of American Statistical Association, 1974.
[17] T. E. Dielman, Deborah D. Kloska, Sharon L. Leech, John E. Schulenberg, and Jean T. Shope.
Susceptibility to peer pressure as an explanatory variable for the differential effectiveness of an
alcohol misuse prevention program in elementary schools. Journal of School Health, 62(6):233 –
237, 1992.
[18] Pedro Domingos and Matt Richardson. Mining the network value of customers. In Proceedings
of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining, KDD ’01, pages 57 – 66, New York, NY, USA, 2001. ACM.
[19] William N Evans, Wallace E Oates, and Robert M Schwab. Measuring peer group effects: A
study of teenage behavior. Journal of Political Economy, 100(5):966–991, 1992.
[20] B. J. Fogg. Persuasive technology: Using computers to change what we think and do. Ubiquity,
2002(December), December 2002.
[21] Marieke L. Fransen, Edith G. Smit, and Peeter W. J. Verlegh. Strategies and motives for
resistance to persuasion: an integrative framework, 2015.
[22] Noah E.. Friedkin and Eugene C. Johnsen. Social influence networks and opinion change.
Advances in Group Processes, 16:1–29, 1999.
[23] J. Ghaderi and R. Srikant. Opinion dynamics in social networks: A local interaction game with
stubborn agents. In 2013 American Control Conference, pages 1982 – 1987, June 2013.
[24] Javad Ghaderi and R Srikant. Opinion dynamics in social networks: A local interaction game
with stubborn agents. In American Control Conference (ACC), 2013, pages 1982–1987. IEEE,
2013.
[25] Aristides Gionis, Evimaria Terzi, and Panayiotis Tsaparas. Opinion maximization in social
networks. In The 13th SIAM International Conference on Data Mining (SDM), May 2-4, 2013.
Austin, Texas, USA, pages 387 – 395, 2013.
[26] Aristides Gionis, Evimaria Terzi, and Panayiotis Tsaparas. Opinion maximization in social
networks. In Proceedings of the 2013 SIAM International Conference on Data Mining, pages
387–395. SIAM, 2013.
19

[27] Yansong Hu and Christophe Van den Bulte. Nonmonotonic status effects in new product
adoption. Marketing Science, 33(4):509 – 533, 2014.
[28] Wijnand IJsselsteijn, Yvonne de Kort, Cees Midden, Berry Eggen, and Elise van den Hoven.
Persuasive Technology for Human Well-Being: Setting the Scene, pages 1 – 5. Springer Berlin
Heidelberg, Berlin, Heidelberg, 2006.
[29] Yogesh V. Joshi, David J. Reibstein, and Z. John Zhang. Turf wars: Product line strategies in
competitive markets. Marketing Science, 35(1):128 – 141, 2016.
[30] Maurits Kaptein, Panos Markopoulos, Boris de Ruyter, and Emile Aarts. Can You Be
Persuaded? Individual Differences in Susceptibility to Persuasion, pages 115 – 118. Springer
Berlin Heidelberg, Berlin, Heidelberg, 2009.
[31] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through
a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, KDD ’03, pages 137 – 146, New York, NY, USA, 2003.
ACM.
[32] D.E. Knuth. The Stanford GraphBase: A Platform for Combinatorial Computing.
[33] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and
shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1), March 2007.
[34] William J. McGuire. Inducing resistance to persuasion: Some contemporary approaches.
Advanced in Experimental Social Psychology, 1:191 – 229, 1964.
[35] Mehdi Moussad, Juliane E. Kmmer, Pantelis P. Analytis, and Hansjrg Neth. Social influence
and the collective dynamics of opinion formation. PLOS ONE, 8(11):1–8, 11 2013.
[36] Kevin M. Murphy and Andrei Shleifer. Persuasion in politics. American Economic Review,
94(2):435 – 439, May 2004.
[37] Cameron Musco, Christopher Musco, and Charalampos E Tsourakakis. Minimizing polarization
and disagreement in social networks. arXiv preprint arXiv:1712.09948, 2017.
[38] Jacob R. Neiheisel and Sarah Niebler. On the limits of persuasion: Campaign ads and the
structure of voters interpersonal discussion networks. Political Communication, 32(3):434 –
452, 2015.
[39] M. E. J. Newman. Finding community structure in networks using the eigenvectors of matrices.
Phys. Rev. E, 74, Sep 2006.
[40] Matthew Richardson and Pedro Domingos. Mining knowledge-sharing sites for viral marketing.
In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining, KDD ’02, pages 61 – 70, New York, NY, USA, 2002. ACM.
[41] Samuel Sampson. Crisis in a Cloister. PhD thesis, Cornell University, 1978. Unpublished
doctoral dissertation.

20

[42] Laurence Steinberg and Kathryn C. Monahan. Age differences in resistance to peer influence.
Developmental Psychology, 43(6):1531–1543, 2007.
[43] Zakary L. Tormala and Richard E. Petty. Source credibility and attitude certainty: A metacognitive analysis of resistance to persuasion. Journal of Consumer Psychology, 14(4):427 – 442,
2004.
[44] Zakary L. Tormela and Richard E. Petty. What doesnt kill me makes me stronger: The effect
of resisting persuasion on attitude certainty. Journal of Personality and Social Psychology,
83(6):1298 1313, 2002.
[45] Melanie Wakefield, Brian Flay, Mark Nichter, and Gary Giovino. Effects of anti-smoking
advertising on youth smoking: A review. Journal of Health Communication, 8:229 – 247, 2003.
[46] Julie A. Wall, Thomas G. Power, and Consuelo Arbona. Susceptibility to antisocial peer
pressure and its relation to acculturation in mexican-american adolescents. Journal of Adolescent
Research, 8(4):403 – 418, 1993.
[47] Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. Local higher-order graph
clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, KDD ’17, pages 555 – 564, New York, NY, USA, 2017. ACM.
[48] Wayne W. Zachary. An information flow model for conflict and fission in small groups. Journal
of Anthropological Research, 33(4):452 – 473, 1977.

21

