# Generalized Opinion Dynamics Model for Social Trust Networks in Opinion
Maximization

###### Abstract

In this paper, we propose a generalized opinion dynamics model (GODM), which
can dynamically compute each person’s expressed opinion, to solve the internal
opinion maximization problem for social trust networks. In the model, we
propose a new, reasonable and interpretable confidence index, which is
determined by both person’s social status and the evaluation around him. By
using the theory of diagonally dominant, we obtain the optimal analytic
solution of the Nash equilibrium with maximum overall opinion. We design a
novel algorithm to maximize the overall with given budget by modifying the
internal opinions of people in the social trust network, and prove its
optimality both from the algorithm itself and the traditional optimization
algorithm-ADMM algorithms with $l_{1}$-regulations. A series of experiments
are conducted, and the experimental results show that our method is superior
to the state-of-the-art in four datasets. The average benefit has promoted
$67.5\%$, $83.2\%$, $31.5\%$, and $33.7\%$ on four datasets, respectively.

Index Terms—  Opinion Maximization, Confidence index, Social Trust Networks,
Optimization, Limited budget

##  1 Introduction and motivation

The study of how people form their opinions through social interactions with
others has long been the subject of research in the field of social science.
On social networks, users can express their opinions on a product or a real-
time new event. By quantifying these opinions, and forming the expressed
opinions through social interactions with others, the overall opinion of a
network on the product or event can be determined. This allows one to
quantitatively study interactions of opinions on a large scale, and to improve
them through targeted interventions. Generally speaking, for the merchant, the
overall opinion of the network on the product as high as possible is expected.
In order to realize it, if possible, the overall opinion can be adjusted
through a certain budget. For the government, when a positive real-time new
event occurs, it hopes that the overall opinion of this event as high as
possible. Conversely, when a negative one happens, the government hopes that
the overall opinion as low as possible. It is obviously that the minimization
of the overall opinion under the premise of a certain budget can be achieved
by converting the original network to a negative network.

Fig. 1: A social trust network (left) and its graph representation (right).

###  1.1 Background

Social trust network is a relatively stable network of relationships among
certain groups (people, enterprises and organizations). A social trust network
and its graph representation can be seen in Fig. 1. Many opinion formation
models have been proposed and studied based on the influence through social
interaction, and the issue of opinion or influence maximization has been
widely studied in [1] and [2]. Chen et al. [1] proposed an algorithm to find
$K$ nodes which perform the greatest common influence on the network. Kong et
al. [3] considered an issue called active opinion maximization, whose goal is
to find a subset of seed users to maximize the overall opinion dissemination
of the target product in a multi-round campaign. In addition to considering
interventions that directly modify people’s internal opinions, Abebe et al.
[4] also considered interventions that to change people’s sensitive to
persuasion. The goal was to modify individual sensitivities to maximize the
overall opinion at Nash equilibrium. And [2] proposed a new continuous-valued
opinion dynamics model for social trust networks, which was more consistent
with real scenarios and achieved good results. But there is still something
can be improved in [2], it only considered the weighted average of the
opinions of person’s internal opinions and those of the people around it.
However, in real life, everyone’s personalities is different. That is to say,
the influence of other people’s opinion is supposed to vary for different
person. Therefore, we have made some improvements on the basis of [2] and
achieved excellent results.

###  1.2 Contributions in this paper

  * •

We develop a generalized opinion dynamics model for social trust networks to
precisely calculate the opinion everyone express. And we introduce a novel
confidence index $\alpha_{i}$, which is determined by a person’s social status
and the evaluation of people around him. In the traditional dynamics model, a
person’s opinion is usually expressed as a weighted average of his internal
opinion and the opinions of those around them. For different human groups, the
range of $\alpha_{i}$ will be different. For example, when there are mostly
young people in the group, the value of $\alpha_{i}$ tends to be relatively
low, and when most people in the group are elderly, the value of $\alpha_{i}$
will be higher. From the theory and experiments, we can see that when
$\alpha_{i}=1/2$, our model GODM is the same one as the model in [2].

  * •

By using the theory of diagonally dominant and Friedkin-Johnsen model, we give
the analytic solution in GODM when the Nash equilibrium is reached.

  * •

We introduce a novel algorithm and prove that the result is optimal. In
addition, we introduce a mature optimization algorithm named ADMM, and solve
the problem with special form derived from this algorithm-$l_{1}$ regulation
and achieve the same result as our algorithm, which further verifies the
optimality of our algorithm.

##  2  Preliminaries

###  2.1 Definition and proposition used in our model

######  Definition 1 (Strictly diagonally dominant).

Square matrix $A=(a_{ij})_{n\times n}$ is strictly diagonally dominant if the
absolute value of its main diagonal element is greater than the sum of the
absolute values of the other elements in the row, i.e.,
$|a_{ii}|>\sum_{j\not=i}|a_{ij}|$, $i=1,\ldots,n$.

######  Proposition 1.

Let $A=(a_{ij})_{n\times n}$ be a square matrix that is strictly diagonally
dominant, then $\det(A)\neq 0$.

###### Proof.

Suppose $\det(A)=0$, then the system of linear equations $Ax=0$ has non-zero
solution $x=(x_{1},x_{2},\ldots,x_{n})^{\mathrm{T}}$. Suppose the largest one
of $|x_{1}|,\ldots,|x_{n}|$ is $|x_{k}|$, then $|x_{k}|>0$. Known by
$\sum_{j=1}^{n}a_{kj}x_{j}=0$, we have

$\displaystyle\Big{|}\sum_{j\neq k}a_{kj}x_{j}\Big{|}$
$\displaystyle=|-a_{kk}x_{k}|=|a_{kk}||x_{k}|>|x_{k}|\sum_{j\neq k}|a_{kj}|$
$\displaystyle\geq\sum_{j\neq k}|a_{kj}||x_{j}|\geq\Big{|}\sum_{j\neq
k}a_{kj}x_{j}\Big{|},$

which is a contradiction. ∎

###  2.2 Friedkin-Johnsen Model

We can represent a social trust network with a directed signed weighted graph
$G=(V,E)$, where $V=\\{1,2,\ldots,n\\}$ is the set of nodes and $E$ is the set
of arcs (directed edges). Each directed edge from $i$ to $j$, $(i,j)\in E$, is
associated with the weight $\omega_{ij}$, which shows the extent of the
relationship. Let $A=(a_{ij})$ be the adjacency matrix of $G$, where
$a_{ij}=\omega_{ij}$ if $(i,j)\in E$, $a_{ij}=0$ otherwise. Let $D$ be a
diagonal matrix with diagonal entry $d_{ii}=\sum_{j=1}^{n}|a_{ij}|$, and
$L=D-A$ be the Laplacian matrix.

The Friedkin-Johnsen model [5] is a famous dynamics model of continuous-valued
opinion. In this model, each node $i\in V$ has a fixed internal opinion
$s_{i}$ that stays the same. During each iteration, the expressed opinion
$z_{i}$ of node $i$ is updated as follows:

$z_{i}=\frac{s_{i}+\sum_{j\in N^{+}(i)}\omega_{ij}z_{j}}{1+\sum_{j\in
N^{+}(i)}\omega_{ij}},$ (2.1)

where the values of $s_{i}$ and $z_{i}$ are in the interval $[-1,1]$,
$N^{+}(i)$ denotes the set of successors of node $i$, and $\omega_{ij}$
denotes the weight of the directed edge $(i,j)$. In a social game, the result
of repeated average converges to the Nash equilibrium [6].

###  2.3 Generalized Opinion Dynamics Model (GODM) For Social Trust Networks

It can be seen from the Friedkin-Johnsen model that for each node $i$, its
expressed opinions are the weighted average of its internal opinions and the
opinions of the people around it. However, in real life, people’s
personalities are different, which lead to the different degrees they are
affected by other people. So we develop a generalized opinion dynamics model
for social trust networks.

The consensus cost function of the social game is computed as follows:

$c(z_{i})\\!=\\!\alpha_{i}(z_{i}\\!-\\!s_{i})^{2}\\!+\\!(1\\!-\\!\alpha_{i})\\!\\!\sum_{j\in
N^{+}(i)}\\!\\!|\omega_{ij}|(z_{i}\\!-\\!{\rm sgn}(i,j)z_{j})^{2},$ (2.2)

where ${\rm sgn}(i,j)$ denotes the sign of nonzero $\omega_{ij}$, and
$\alpha_{i}$ denotes the confidence index of node $i$. The confidence index
$\alpha_{i}$ reflects how confident everyone in a social network is. In social
networks, a higher $\alpha_{i}$ indicates that a person is more likely to
listen to his or her own thoughts when expressing opinions, rather than being
easily influenced by others. In a real social network, the $\alpha_{i}$ value
is related to its importance in the network and how others evaluate it.

######  Theorem 2.1.

Let $\Lambda=\text{diag}\,(\alpha_{1},\ldots,\alpha_{n})$ be a diagonal
matrix, where $\alpha_{i}$ is the confidence index of node $i$ in a social
trust network, and let $L$ be the Laplacian matrix of the social trust
network. Then $\Lambda+(I-\Lambda)L$ is invertible.

###### Proof.

It is clear that

$(\Lambda+(I-\Lambda)L)_{ii}=\alpha_{i}+(1-\alpha_{i})\sum_{j\in
N^{+}(i)}|\omega_{ij}|.$

The sum of the absolute values of the off-diagonal elements of
$\Lambda+(I-\Lambda)L$ is equal to the sum of the absolute values of the off-
diagonal elements of $(I-\Lambda)L$, which is $(1-\alpha_{i})\sum_{j\in
N^{+}(i)}|\omega_{ij}|$. For $0<\alpha_{i}<1$, $\Lambda+(I-\Lambda)L$ is the
diagonally dominant matrix, as desired. ∎

######  Proposition 2.

Let $s$ be the internal opinion vector, whose $i$-th component is $s_{i}$, and
$z^{*}$ be the expressed opinion vector at the Nash equilibrium. We have
$z^{*}=(\Lambda+(I-\Lambda)L)^{-1}\Lambda s$.

###### Proof.

At the Nash equilibrium, we compute expressed opinion $z_{i}^{*}$ that
minimizes its cost for each node $i$, i.e., $c^{\prime}(z_{i}^{*})=0$. Hence,

$c^{\prime}(z_{i}^{*})\\!\\!=\\!2\alpha_{i}(z_{i}^{*}-s_{i})\\!+2(1-\alpha_{i})\\!\\!\\!\sum_{j\in
N^{+}(i)}\\!\\!|\omega_{ij}|(z_{i}^{*}-{\rm
sgn}(i,j)z_{j}^{*}\\!)\\!\\!=\\!\\!0.$

It follows that

$z_{i}^{*}=\frac{\alpha_{i}s_{i}+(1-\alpha_{i})\sum_{j\in
N^{+}(i)}\omega_{ij}z_{j}^{*}}{\alpha_{i}+(1-\alpha_{i})\sum_{j\in
N^{+}(i)}|\omega_{ij}|}.$ (2.3)

We rewrite Equation (2.3) as:

$\Big{(}\alpha_{i}+(1-\alpha_{i})\sum_{j\in
N^{+}(i)}|\omega_{ij}|\Big{)}z^{*}=\alpha_{i}s_{i}+(1-\alpha_{i})\sum_{j\in
N^{+}(i)}\omega_{ij}z_{j}^{*}.$

By introducing the opinion vectors $s$ and $z^{*}$, we can transform Equation
(2.3) as it’s matrix form: $(\Lambda+(I-\Lambda)L)z^{*}=\Lambda s$. According
to the Theorem 2.1, $\Lambda+(I-\Lambda)L$ is invertible. Therefore, we obtain
that $z^{*}=(\Lambda+(I-\Lambda)L)^{-1}\Lambda s$. ∎

PageRank: PageRank is a technology which is calculated by search engines based
on the hyperlinks between pages [7]. It is used to show the relevance and
importance of web pages.

For a page $v_{i}$:
$r(v_{i})=\frac{1+d}{N}+d\big{(}\frac{r(u_{1})}{c(u_{1})}+\cdots+\frac{r(u_{n})}{c(u_{n})}\big{)}$,
where $r(v_{i})$ denotes the PageRank value of page $v_{i}$, $u_{i}$ refers to
one of the pages that points to $v_{i}$, $c(u_{i})$ denotes the number of
edges that point to other pages for page $u_{i}$. $N$ is the number of nodes
in the social network. $d$ is the damping coefficient, usually $d=0.85$. In a
large network, the PageRank value for each point may be very small. So we
normalized the PageRank values of points by dividing by the maximum PageRank
value among all points.

Mean evaluation: In social networks, each node plays two roles, the output
node and the input node. As an input node, its edge weight and edge sign
represent the evaluation that other nodes on it. Here, for a node $i$, we use
mean evaluation to express the average evaluation that other nodes on it, so
for node $i$, the calculation formula of mean evaluation that others on it can
be expressed as: $m(i)=\frac{\sum_{j\in N^{-}(i)}\omega_{ij}}{d_{i}^{-}}$,
where $m(i)$ denotes the mean evaluation of node $i$, $N^{-}(i)$ is the
predecessors of node $i$, and $d_{i}^{-}$ denotes the amount of the
predecessors of node $i$.

Compute the confidence index $\alpha_{i}$: Here, let’s consider two scenarios.
First, the confidence index $\alpha_{i}$ is fixed, which doesn’t change with
the structure of the graph. Second, the confidence index $\alpha_{i}$ is
adjustable. Here we let the confidence index $\alpha_{i}$ weighted by PageRank
value and mean evaluation, which is calculated by the following formula:

$\alpha_{i}=qm(i)+(1-q)r(i),$ (2.4)

where $m(i)$ and $r(i)$ are the mean evaluation and PageRank value of node
$i$, respectively, and $0\leq q\leq 1$ is a constant. When $q=1$, the value of
$\alpha_{i}$ is completely determined by the PageRank value, and when $q=0$,
the value of $\alpha_{i}$ is determined by what other people say about it. In
this case, let’s take $q=0.5$.

In real social trust networks, such as a network of users’ reviews of a
website. Due to the trust and distrust between users, this may result in a
negative mean evaluation of a user. And the PageRank value may be very small,
which may result in the calculated $\alpha_{i}$ value, the confidence index,
being negative. This is unreasonable, so we introduce the Rectified Linear
Unit, which restricts the value of $\alpha_{i}$ to $[0,1]$. So Equation (2.4)
becomes the following:

$\alpha_{i}=RELU(qm(i)+(1-q)r(i)),$ (2.5)

where $RELU(x)=\max\\{0,x\\}$. From Equation (2.5), we can see that the more
important a person is in the network and the higher people’s evaluation of
him, the higher his confidence index will be.

######  Definition 2 (Overall opinion).

The overall opinion $p(z^{*})$ of a social trust network is the sum of the
expressed opinions at Nash equilibrium:
$p(z^{*})=\sum_{i}z^{*}_{i}=\bm{1}^{\mathrm{T}}(\Lambda+(I-\Lambda)L)^{-1}\Lambda
s$, where $\bm{1}$ is the all-ones column vector.

##  3 Internal Opinion Maximization in Social Trust Networks

######  Definition 3 (Internal opinion problem).

Given a social trust network $G$, the internal opinion vector $s$, and the
budget amount $\mu$, our goal is to find out the modification of internal
opinions $\Delta s$ to maximize the overall opinion $p(z^{*})$:

$\displaystyle\max~{}\bm{1}^{\mathrm{T}}(\Lambda+(I-\Lambda)L)^{-1}\Lambda(s+\Delta
s),$ $\displaystyle\text{s.t.}~{}\begin{cases}-1\leq s_{i}+\Delta s_{i}\leq
1,~{}(i=1,2,\ldots,n),\\\ \|\Delta s\|_{1}\leq\mu.\end{cases}$

According to the Proposition 2, the expressed opinion vector is in the column
space of $\Lambda+(I-\Lambda)L$ and the coordinates are stored in the vector
of internal opinions. Then, we name
$g=\bm{1}^{\mathrm{T}}(\Lambda+(I-\Lambda)L)^{-1}\Lambda$ the contribution
index vector. As
$p(z^{*})=\bm{1}^{\mathrm{T}}(\Lambda+(I-\Lambda)L)^{-1}\Lambda s=gs$, the
$i$-th element of $g$ represents the contribution of the internal opinion of
node $i$ to the overall opinion. Specifically, the contribution index is
defined as follows.

######  Definition 4 (Contribution index).

The contribution index $g_{i}$ of node $i$ represents how $i$’s internal
opinion contributes to the overall opinion and is quantified by:

$g_{i}=(\bm{1}^{\mathrm{T}}(\Lambda+(I-\Lambda)L)^{-1}\Lambda)_{i}.$

To maximize the overall opinion, we change the internal opinion with the
largest absolute value of the contribution index of the node, then the maximum
benefit can be obtained under the same budget. Our approach is summarized in
Algorithm 1. It is further proved that Algorithm 1 outputs the optimal result
of the internal opinion problem.

Input: Social trust network $G=(V,E)$; Budget $\mu$; Randomly generate
internal opinions $s$.

Output : The modification $\Delta s$.

begin

Compute $g_{i}=(\bm{1}^{\mathrm{T}}(\Lambda+(I-\Lambda)L)^{-1}\Lambda)_{i}$;

Set $sign=\frac{g_{i}}{|g_{i}|}$;

while  _$\mu >0$_ do

Find the largest $|g_{i}|$, $cost=1-sign\cdot s_{i}$;

if  _$cost >\mu$_ then

$\Delta s=sign\cdot\mu,~{}\mu=0$;

else

$\Delta s=sign\cdot cost,~{}\mu=\mu-cost$;

end if

end while

end

Algorithm 1 Solving Internal Opinion Problem

######  Theorem 3.1.

Algorithm 1 outputs the optimal result of the internal opinion problem.

###### Proof.

According to the Algorithm 1, we know the benefit is $g\Delta s$. For any
intervened node $i$, we can adjust the corresponding modification $\Delta
s_{i}$ to $(\Delta s_{i}-v)$ if $\Delta s_{i}>0$, or $(\Delta s_{i}+v)$
otherwise, where $v>0$. Then we have an unused budget $v$ and randomly find a
node $j$ that is not intervened before. As the internal opinion of node $j$ is
changed, the benefit becomes $g\Delta s+(|g_{j}|-|g_{i}|)v$. We know from
Algorithm 1 that $|g_{j}|\leq|g_{i}|$, thus $g\Delta s\geq g\Delta
s+(|g_{j}|-|g_{i}|)v$. ∎

##  4 Solve internal opinion maximization problem with the ADMM algorithm

###  4.1 ADMM algorithm

Alternating Direction Method of Multipliers (ADMM) is a convergent algorithm
combining the factorability of dual ascending and the advantages of multiplier
method, which was proposed by Boyd [8]. When there are multiple variables in
the target of a convex optimization problem, it is difficult to solve, so we
use variable separation to divide the problem into several simple subproblems.
Then we can solve these subproblems in parallel and coordinate the subproblems
to get the global solution of original problem.

###  4.2 Steps of the ADMM algorithm

Suppose the optimization problems are as follows:

$\displaystyle\min_{x,z}~{}f(x)+g(z)$ $\displaystyle\text{s.t.}~{}Ax+Bz=c,$

where $x\in\mathbb{R}^{n}$, $z\in\mathbb{R}^{m}$, $A\in\mathbb{R}^{p\times
n}$, $B\in\mathbb{R}^{p\times m}$, $c\in\mathbb{R}^{p}$. Its augmented
Lagrangian function is as follows:

$L_{\rho}(x,z,y)=f(x)+g(z)+y^{\mathrm{T}}(Ax+Bz-c)+\frac{\rho}{2}\|Ax+By-c\|_{2}^{2}.$

The update iteration form of ADMM is as follows:

$\displaystyle x^{k+1}$ $\displaystyle:=\arg\min_{x}L_{\rho}(x,z^{k},y^{k}),$
$\displaystyle z^{k+1}$
$\displaystyle:=\arg\min_{z}L_{\rho}(x^{k+1},z,y^{k}),$ $\displaystyle
y^{k+1}$ $\displaystyle:=y^{k}+\rho(Ax+Bz-c),$

where $\rho>0$, $c\in\mathbb{R}^{p}$ is a dual variable, and this is the
original iteration form of ADMM algorithm.

###  4.3 Solve the internal opinion problem with the ADMM algorithm

The internal opinion problem we want to solve is as follows:

$\displaystyle\max~{}\bm{1}^{\mathrm{T}}(\Lambda+(I-\Lambda)L)^{-1}\Lambda(s+\Delta
s)$ $\displaystyle\text{s.t.}~{}\begin{cases}-1\leq s_{i}+\Delta s_{i}\leq
1,~{}(i=1,2,\ldots,n),\\\ \|\Delta s\|_{1}\leq\mu.\end{cases}$

Because $\bm{1}^{\mathrm{T}}(\Lambda+(I-\Lambda)L)^{-1}\Lambda s$ is a
constant, we can rewrite the problem as:

$\displaystyle\max~{}\bm{1}^{\mathrm{T}}(\Lambda+(I-\Lambda)L)^{-1}\Lambda\Delta
s,$ $\displaystyle\text{s.t.}~{}\begin{cases}-1-s_{i}\leq\Delta s_{i}\leq
1-s_{i},~{}(i=1,2,\ldots,n),\\\ \|\Delta s\|_{1}\leq\mu.\end{cases}$

We can translate the problem into the following form:

$\displaystyle\min~{}l(x)+\lambda\|x\|_{1},$ $\displaystyle\text{s.t.}~{}a\leq
x\leq b,$

where $l(x)=-\bm{1}^{\mathrm{T}}(\Lambda+(I-\Lambda)L)^{-1}\Lambda$, $x=\Delta
s$, $a_{i}=-1-s_{i}$, $b_{i}=-1+s_{i}$. We then further translate this into
the following form that can be solved by ADMM:

$\displaystyle\min~{}l(x)+\lambda\|z\|_{1},$
$\displaystyle\text{s.t.}~{}\begin{cases}a\leq x\leq b,\\\ x=z.\end{cases}$

In this case, the variables $x$, $z$ and $u$ are updated as follows:

$\displaystyle x^{k+1}$
$\displaystyle:=\arg\min_{x}\big{(}l(x)+\frac{\rho}{2}\|x-z^{k}+u^{k}\|_{2}^{2}\big{)},$
$\displaystyle z^{k+1}$ $\displaystyle:=S_{\lambda/\rho}(x^{k+1}+u^{k}),$
$\displaystyle u^{k+1}$ $\displaystyle:=u^{k}+x^{k+1}-z^{k+1}.$

From the above formula, the analytic solution of each step iteration can be
written:

$\displaystyle x_{i}^{k+1}$
$\displaystyle:=\begin{cases}a_{i},&\text{if}~{}z_{i}^{k}-u_{i}^{k}-\frac{A_{i}}{\rho}<a_{i},\\\
z_{i}^{k}-u_{i}^{k}-\frac{A_{i}}{\rho},&\text{if}~{}z_{i}^{k}-u_{i}^{k}-\frac{A_{i}}{\rho}<b_{i},\\\
b_{i},&\text{if}~{}b_{i}<z_{i}^{k}-u_{i}^{k}-\frac{A_{i}}{\rho},\end{cases}$
$\displaystyle z_{i}^{k+1}$
$\displaystyle:=\begin{cases}z_{i}^{k+1}-u_{i}^{k}-\frac{\lambda}{\rho},&\text{if}~{}z_{i}^{k+1}-u_{i}^{k}>\frac{\lambda}{\rho},\\\
0,&\text{if}~{}-\frac{\lambda}{\rho}<z_{i}^{k+1}-u_{i}^{k}<\frac{\lambda}{\rho},\\\
z_{i}^{k+1}-u_{i}^{k}+\frac{\lambda}{\rho},&\text{if}~{}z_{i}^{k+1}-u_{i}^{k}<-\frac{\lambda}{\rho},\end{cases}$
$\displaystyle u_{i}^{k+1}$
$\displaystyle:=u_{i}^{k}+x_{i}^{k+1}-z_{i}^{k+1}.$

The algorithm converges to the global optimal solution, so after a certain
number of iterations, we can get the optimal result.

##  5 Experiments

In this section, we conduct a series of experiments to evaluate the proposed
method. We carry out experiments from two aspects. First, we compare the
results obtained by our model with those in [2]. To further illustrate the
superiority of our model, our method is compared with other heuristic methods,
and the experimental results show that our method has overwhelming advantages.

###  5.1 Datasets

The datasets we used in the experiments are as follows: (i) Alpha; (ii) OTC
[9], [10]; and we normalize the trust values (i.e., edge weights) to the
interval $[-1,1]$ on Alpha and OTC. (iii) Elec; (iv) Rfa [11]; and the
relationships in the last two networks are closely related to trust.

###  5.2 Internal opinion initialization

We randomly select values that match a particular distribution to initialize
the internal opinion vector $s$ to simulate different situations. For each
network, we use three ways to initialize the internal opinions. (i) We
initiate the internal opinions to follow a uniform distribution (i.e., $s\sim
U(-1,1)$). (ii) We initiate the internal opinions to follow a standard normal
distribution (i.e., $s\sim N(0,1)$). (iii) We initiate the internal opinions
of a node to positively correlated with the column connectivity of that node
(i.e., $s_{i}\propto\sum_{j}|a_{ji}|$).

###  5.3 The value of $\alpha_{i}$

We experimented with two different ways of selecting value of $\alpha_{i}$:
(i) Fixed $\alpha_{i}$. In this case, we fixed the value of $\alpha_{i}$,
which means that everyone’s confidence index is the same in the network. (ii)
Adjusted $\alpha_{i}$. In this case, $\alpha_{i}$ changes with the internal
structure of each group. When $\alpha_{i}\in\\{2/3,1/2,1/3,1/4\\}$, we carried
out a set of tests, and the experimental results are shown in Table 1.

As can be seen from Table 1, when $\alpha_{i}=1/2$, that is, the proportion of
the opinions of everyone inside and those of the people around is the same,
and the experimental results are consistent with those in [2]. When
$\alpha_{i}>1/2$, the experimental result is lower than the result in [2], and
when $\alpha_{i}<1/2$, the experimental result is higher than the result in
[2]. This situation is also reasonable in real life. A larger $\alpha_{i}$
indicates that the opinions expressed by each person are less likely to be
influenced by those around them. The smaller $\alpha_{i}$ is, the more
susceptible the expressed influence is to those around it. Therefore, changing
the internal opinions of a small number of people will affect the overall
opinions of the whole network to change greatly.

Table 1: Average benefit compared with different $\alpha_{i}$ Alpha | $\alpha_{i}$ | $2/3$ | $1/2$ | $1/3$ | $1/4$
---|---|---|---|---|---
OMSTN [2] | 282 | 277 | 265 | 281
Fixed $\alpha_{i}$ | 254 | 277 | 293 | 343
Adjusted $\alpha_{i}$ | 481 | 461 | 429 | 479
OTC | $\alpha_{i}$ | $2/3$ | $1/2$ | $1/3$ | $1/4$
OMSTN | 306 | 318 | 316 | 304
Fixed $\alpha_{i}$ | 270 | 318 | 367 | 386
Adjusted $\alpha_{i}$ | 546 | 600 | 578 | 555
WikiElec | $\alpha_{i}$ | $2/3$ | $1/2$ | $1/3$ | $1/4$
OMSTN | 1165 | 1115 | 1144 | 1149
Fixed $\alpha_{i}$ | 974 | 1115 | 1305 | 1394
Adjusted $\alpha_{i}$ | 1538 | 1468 | 1499 | 1510
WikiRfa | $\alpha_{i}$ | $2/3$ | $1/2$ | $1/3$ | $1/4$
OMSTN | 1010 | 1000 | 1023 | 968
Fixed $\alpha_{i}$ | 906 | 1000 | 1121 | 1098
Adjusted $\alpha_{i}$ | 1340 | 1341 | 1375 | 1293

###  5.4 Comparative Methods

In order to better reflect the advantages of our results, as with [2], we
compared it to several other three heuristics. (i) Rand. We sort the nodes
randomly. (ii) Trust. We represent the trust sum of the nodes by calculating
the sum of the corresponding columns of the adjacency matrix. Nodes with a
large amount of trust may have a strong ability to influence the opinions of
other nodes. Therefore, we sort the nodes in descending order of the node
trust sum. (iii) IO. If we can persuade those negative internal opinions to
have positive internal opinions, then the overall opinion may increase.
Therefore, we take the internal opinions of the node and sort the
corresponding nodes in ascending order. In order to ensure the fairness of the
experimental results, we reproduced the other methods mentioned in [2] and
carried out the experiment on the same computer. In the experiment, we set the
parameter $\mu=200$, and the result is shown in Table 2 and Fig. 2.

As can be seen from the results, our approach has an overwhelming advantage
over all datasets. A part of the performance curves are shown in Fig. 3. The
$x$-axis shows the budget amount, the left $y$-axis shows the overall opinion,
and the right $y$-axis shows the unit benefit.

Table 2: Average benefit compared with other heuristics Uniform |  | Alpha | OTC | WikiElec | WikiRfa
---|---|---|---|---|---
Ours | 463 | 532 | 1550 | 1340
Rand | 41 | 21 | 13 | 29
Trust | 225 | 83 | 275 | 298
IO | 23 | 25 | 144 | 34
Normal |  | Alpha | OTC | WikiElec | WikiRfa
Ours | 452 | 578 | 1581 | 1341
Rand | 26 | 20 | 87 | 14
Trust | 250 | 112 | 205 | 378
IO | 36 | 23 | 233 | 15
Degree |  | Alpha | OTC | WikiElec | WikiRfa
Ours | 454 | 569 | 1545 | 1375
Rand | 18 | 14 | 29 | 40
Trust | 250 | 92 | 297 | 329
IO | 260 | 120 | 8 | 174

Fig. 2: Average benefit of different methods on four datasets.

Fig. 3:  A part of the performance curves.

##  6 Conclusion

In this paper, we have proposed a generalized opinions dynamics model for
social trust networks to solve the internal opinion maximization problem.
Different from other methods, our model GODM introduces a new confidence index
and proposes a novel algorithm, which proved to be optimal. Extensive
experimental results on four datasets demonstrate the effectiveness of our
model.

## References

  * [1] Shuo Chen, Ju Fan, Guoliang Li, Jianhua Feng, Kian Lee Tan, and Jinhui Tang,  “Online topic-aware influence maximization,”  Proceedings of the VLDB Endowment, 2015.
  * [2] Pinghua Xu, Wenbin Hu, Jia Wu, and Weiwei Liu,  “Opinion maximization in social trust networks,”  Proceedings of the International Joint Conference on Artificial Intelligence, 2020.
  * [3] Xiangnan Kong Xinyue Liu and Philip S Yu,  “Active opinion maximization in social networks,”  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1840–1849, 2018.
  * [4] Rediet Abebe, Jon Kleinberg, David Parkes, and Charalampos E Tsourakakis,  “Opinion dynamics with varying susceptibility to persuasion,”  2018\.
  * [5] Noah E. Friedkin and Eugene C. Johnsen,  “Social influence and opinions,”  Journal of Mathematical Sociology, vol. 15, no. 3–4, pp. 193–206, 1990.
  * [6] David Bindel, Jon Kleinberg, and Sigal Oren,  “How bad is forming your own opinion?,”  Games & Economic Behavior, vol. 92, pp. 248–265, 2015.
  * [7] Page Lawrence, Brin Sergey, Motwani Rajeev, and Winograd Terry,  “The pagerank citation ranking:bringing order to the web,”  1998\.
  * [8] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein,  “Distributed optimization and statistical learning via the alternating direction method of multipliers,”  Foundations & Trends in Machine Learning, vol. 3, no. 1, pp. 1–122, 2010.
  * [9] Srijan Kumar, Francesca Spezzano, V.S. Subrahmanian, and Christos Faloutsos,  “Edge weight prediction in weighted signed networks,”  in IEEE International Conference on Data Mining, 2017.
  * [10] Srijan Kumar, Bryan Hooi, Disha Makhija, Mohit Kumar, and V. S. Subrahmanian,  “Rev2: Fraudulent user prediction in rating platforms,”  in the Eleventh ACM International Conference, 2018.
  * [11] Robert West, Hristo S Paskov, Jure Leskovec, and Christopher Potts,  “Exploiting social network structure for person-to-person sentiment analysis,”  Eprint Arxiv, 2014.