Opinion Maximization in Social Trust Networks

1 Introduction

On social sites, users can express their opinions on a product, a social event, or many other information items. By quantifying opinions with numerical values, the overall opinion of a network can be determined as the sum total of the opinions of all individuals. This value reflects the emotional tendency of the site toward an information item. Knowing the overall opinion is critical for many economic and academic applications, such as marketing campaigns and public voice control. For example, suppose that we are running a mobile phone company and have just released a new phone. In order to boost sales, it is vital to guide the market to react more positively (i.e., have a more positive overall opinion) to our product with a limited budget. We call this issue opinion maximization. It is the general form of influence maximization [Li

∗Corresponding authors.

0.5

Figure 1: (a) A social trust network. (b) Graph representation of (a).

et al., 2018] and the main difference is that we consider opinions in continuous-valued states rather than bipartite states, which is too strict in many real scenarios.

Different from most existing studies on opinion or influence maximization [Chen et al., 2016; Yang et al., 2016; Abebe et al., 2018; Liu et al., 2018], we argue that it is more realistic and valuable to study this issue in a social trust network (STN, see Figure 1), which models the individuals and the trust or distrust relationships between them and can be represented by a directed signed weighted graph [Kumar et al., 2016; Xu et al., 2019]. The main reason for this is the fact that the following three important network characteristics have usually not been reflected in the target networks of the existing studies simultaneously.

• A lot of normal users tend to be influenced by key opinion leaders (KOLs), but KOLs are hardly influenced by normal users. This characteristic is reflected in the directionality of STNs.
• Users can be influenced by others to varying degrees and this characteristic is reflected in the absolute weights of edges in STNs.
• Relationships between users may have opposite polarities. This characteristic is reflected in the signs of the edges' weights in STNs.

Given the target networks, we need to model how opinions of individuals form, then we can design strategies to maximize the overall opinion. Therefore, we have chosen to generalize a famed continuous-valued opinion dynamics model [Friedkin and Johnsen, 1990] for STNs for three reasons:

• Opinions cannot be accurately modeled by discrete states, such as being absolutely supportive or opposed, in many real scenarios. For example, one may give a little support or strong support to a new iPhone.

• Opinion dynamics better resembles a social game in which individuals constantly influence each other rather than a discrete cascading process [Gionis et al., 2013].
• In addition to the trust relationships, distrust relationships also play an important role in opinion dynamics [Li et al., 2013; Li et al., 2017]. But they are usually ignored in existing studies of opinion dynamics.

As an STN has several complex network characteristics and the opinion dynamics model used is more realistic and complex, opinion maximization becomes much more difficult in STNs. Therefore, existing studies are not applicable for STNs. In this study, we formalize two novel problems for solving opinion maximization in STNs. They are, with a limited budget, how to maximize the overall opinion by changing internal opinions of some people (IOP) or by fixing the expressed opinions of some people (EOP). In IOP, we observe that people play different roles in the social game, i.e., their internal opinions contribute differently to the overall opinion. This phenomenon is not observed in oversimplified networks. In addition, we define a novel contribution index to quantify the contribution ability, then design a simple but effective method for IOP. The expressed opinion problem is NP-hard, hence we design a greedy method to achieve an acceptable solution. Iteratively calculating the benefit of fixing a node's expressed opinion is time-consuming, but we integrate the calculations into a simple expression via crafty matrix operations. That makes our method efficient. We evaluate our methods on several real-world datasets and the experimental results demonstrate the practical utility of the proposed methods. The contributions of this study can be summarized as follows. 1

• This is the first study that investigates opinion maximization in STNs with a continuous-valued opinion dynamics model. We formalize two novel problems, IOP and EOP, for maximizing the overall opinion of an STN.
• We define a novel contribution index to quantify the nodes' variant contribution abilities to the overall opinion, which are unobserved in oversimplified networks. We also develop a simple method for IOP that can easily achieve optimal performance.
• We prove the hardness of EOP. By integrating the vast computation via crafty matrix operations, we develop an efficient method for EOP.

The rest of this paper is organized as follows. The preliminaries include an explanation of our notation and the opinion dynamics model is described in Section 2. The problems and the proposed methods are presented in Section 3. Section 4 details the experiments, followed by the conclusions in Section 5.

2 Preliminaries

2.1 Notation

A social trust network is represented by a directed signed weighted graph G = (V, E), where V is the set of nodes and E is the set of edges. Each directed edge from i to j, (i, j) ∈ E, is associated with the weight wij ∈ [-1, 1], which signifies the strength of the relationship. Let A denote the adjacency matrix of G, where aij = wij if (i, j) ∈ E, aij = 0 otherwise. Let D denote the row connectivity matrix, where dii = ∑j |aij|. Then ¯L = D - A denotes the generalized Laplacian matrix [Hu and Zheng, 2013].

1 The implementations of the methods are available at https://github.com/WHU-SNA/OpMaxInSTN

Lemma 1 Inequality 0 ≤ minsp(¯Lu) ≤ Re(sp(¯L)) ≤ max sp(¯Lu), where ¯Lu = (¯L+¯LT )/2, sp(∗) indicates the spectra and Re(∗) indicates the real parts.

Theorem 1 The term (¯L+I) is invertible, where I is identity matrix.

Proof Denote the eigenvalues of ¯L as {k1, k2, ..., k|V|} and the corresponding eigenvectors as {x1, x2, ..., x|V|}. Then, we have the following derivation:

Hence, the eigenvalues of (¯L + I) are {k1 + 1, k2 + 1, ..., k|V| + 1}. According to lemma 1, for 1 ≤ i ≤ |V|, Re(ki) ≥ 0. Therefore, the real parts of all the eigenvalues of (¯L + I) are greater than 1, det(¯L + I) ̸= 0, and (¯L + I) is invertible.

2.2 Friedkin-JohnsenModel

The Friedkin-Johnsen model [Friedkin and Johnsen, 1990] is a famed continuous-valued opinion dynamics model. In this model, each node i ∈ V holds a fixed internal opinion si, which remains constant. During each iteration, node i updates its expressed opinion zi as follows:

where N(i) denotes the successors of i. The values of si and zi are in the interval [-1, 1], where -1/1 signifies the strongest positive/negative opinion. The repeated averaging does converge to the Nash equilibrium of a social game [Bindel et al., 2015].

2.3 Generalized Opinion Dynamics Model For Social Trust Networks

As relationships with opposite polarities in STNs are now considered, we generalize the social game of the Friedkin-Johnsen model according to structural balance theory [Islam et al., 2018]. Specifically, an individual is supposed to express the opposite opinions of the people she distrusts. Hence the consensus cost function of the social game is:

where sgn(i, j) denotes the sign of nonzero wij. Accordingly, the repeated averaging process becomes:

Proposition 1 Let s denote the internal opinion vector, whose i-th component is si, and z∗ denote the expressed opinion vector at the Nash equilibrium. Equation (2) is solved by the equilibrium z∗ = (¯L + I)-1 s.

g = 2.00

Proof At the Nash equilibrium, each node i adopts an expressed opinion z∗ i that minimizes its cost, which implies that c′ (z∗ i ) = 0.

Therefore, the Nash equilibrium opinion of a node is the weighted average of its internal opinion, the Nash equilibrium opinions of the nodes it trusts, and the opposite Nash equilibrium opinions of the nodes it distrusts. We rewrite equation (3) as: 1 1 g = 0.33 (c)

g = 2.50

g = 0.33

g = 2.50

By introducing the opinion vectors s and z∗ , we can formalize equation (3)'s matrix form as:

According to Theorem 1, (¯L + I) is invertible. Therefore, we obtain that z∗ = (¯L + I)-1 s.

Given the generalized opinion dynamics model for STNs, we adopt a similar definition of overall opinion introduced in [Gionis et al., 2013].

Definition 1 (Overall opinion). The overall opinion p(z∗ ) of an STN is the sum of the expressed opinions at Nash equilibrium:

where ⃗1 is a column vector of ones.

3 OpinionMaximization in Social Trust Networks

In this section, we formalize IOP and EOP for solving opinion maximization in STNs, and we develop two methods for IOP and EOP, respectively. Figure 2 illustrates that we can increase the overall opinion by changing a node's internal opinion or by fixing a node's expressed opinion.

3.1 Internal Opinion Problem

In IOP, we seek to change the internal opinions of some nodes to specific values, such that the overall opinion is maximized. Our decision is limited by a budget µ on the total modification of internal opinions. Let ∆s denote the modification of the internal opinions and the formal problem definition is the following.

Definition 2 (Internal Opinion Problem). Given a social trust network G, the internal opinion vector s, and the budget amount µ, seek out the modification of internal opinions ∆s, such that the overall opinion p(z∗ ) is maximized:

Figure 2: Subfigure (a) illustrates the opinion dynamics in an STN. The values on the nodes indicate the expressed opinions, and the values close to the edges indicate the weights. Note that the expressed opinion of a node equals its internal opinion at the initial state. We can increase the overall opinion by (b) changing the internal opinion of a node or (c) by fixing the expressed opinion of a node. g = 0.63 g = 1.63 (f) 1 1 1 1 1 1

According to Proposition 1, the expressed opinion vector is in the column space of (¯L + I)-1 and the coordinates are stored in the vector of internal opinions. Then, we refer to g = (⃗1T (¯L + I)-1 )T as the contribution index vector. As p(z∗ ) = ⃗1T (¯L + I)-1 s = gT s, each entry gi indicates the amount by which the node i's internal opinion contributes to the overall opinion. Formally, the contribution index is defined as follows.

Definition 3 (Contribution index). The contribution index gi of node i indicates how i's internal opinion contributes to the overall opinion and is quantified by:

In Figure 3, we demonstrate some examples of the contribution index. For simplicity, the edge weight is set to +1 or -1. From (a)(b), we observe that a node, which receives more trusts from other nodes, has a larger contribution index. Subfigures (a)(c) illustrate that a KOL has more impact on the overall opinion than normal users. The target node in (d) has a negative contribution index, as it promotes the nodes who distrust it to adapt the opposite of its expressed opinion. In subfigure (e), the target node is trusted by a node and distrusted by another. The combined effects of the relationships with opposite signs result in a contribution index of

Algorithm 1: Solving internal opinion problem

Input: A social trust network G = (V, E), internal opinions s, and budget µ.

Output: The modification ∆s.

Initialize ∆s to null vector;

while µ > 0 do

Find the component gi with the largest absolute

sign = gi/|gi|; cost = 1 - sign · si;

if cost > µ then

∆si = sign · µ; break;

else∆si = sign · cost; µ = µ - cost;

1. Subfigure (f) shows the contribution indices of nodes in a hierarchical network structure.

By changing the internal opinion of the node with the largest absolute value of the contribution index, we can get the most benefit at the same budget. Our method SIOP is summarized in Algorithm 1. Further, we proof that Algorithm 1 outputs the optimal solution of IOP.

Theorem 2 Algorithm 1 outputs the optimal solution of IOP. Proof Given the output of Algorithm 1, the benefit is gT ∆s. For any intervened node i, we can adjust the corresponding modification ∆si to (∆si - ν) if ∆si > 0, or (∆si + ν) otherwise, where ν > 0 is very slight perturbation. We then have unused budget ν. By changing the internal opinion of node j, which is not intervened before, the benefit becomes gT ∆s + (|gj| - |gi|)ν. According to the procedure of Algorithm 1, |gj | ≤ |gi|, thus gT ∆s ≥ gT ∆s + (|gj | - |gi|)ν.

Remark IOP may have multiple optimal solutions.

3.2 Expressed Opinion Problem

Suppose that we can fix the expressed opinions of some nodes to their internal opinions during the opinion formation process. The chosen nodes will then never be affected by the expressed opinions of their neighbors. In EOP, we try to find a set of nodes U ∈ V. For each node i in U, we fix its expressed opinion, such that the overall opinion is maximized. Let p(z∗ |U) denote the overall opinion after fixing the expressed opinion of nodes in U and the formal problem definition is the following.

Definition 4 (Expressed opinion problem). Given a social trust network G, the internal opinion vector s, and an integer µ, seek a set U of µ nodes and fix zi to si for i ∈ U, such that p(z∗ |U) is then maximized.

Theorem 3 EOP is NP-hard.

Proof Due to lack of space, we only sketch the proof here. Our proof follows the idea in [Gionis et al., 2013]. We generalized the absorbing random walk for STNs, then constructed a reduction from the problem of vertex cover on regular graphs.

Given the hardness of EOP, we designed a greedy algorithm to achieve an acceptable solution. The algorithm starts with an empty set U 0 , and extends U (t-1) by adding a node i ∈ V \U (t-1) in the t-th iteration, such that the benefit to the overall opinion p(z∗ |U (t-1) ∪i)-p(z∗ |U (t-1) ) is maximized. In the first iteration, we successively calculate the benefit of fixing the expressed opinion of each node i in V. Note that from the view of linear algebra, fixing i's expressed opinion is equivalent to replacing the i-th row of A with a row vector of zeros. And the row connectivity changes accordingly.

Let Q = (¯L+I)-1 denote the fundamental matrix, QU denote the fundamental matrix after fixing the expressed opinions of nodes in U. Obviously, QU 0 = Q. According to Theorem 4, we compute QU 0∪i (equals to Q{i} ) using the Sherman-Morrison formula:

where ei is the unit vector, whose i-th component is 1, and li: is the i-th row of ¯L. In the t-th iteration, the fundamental matrix after fixing the expressed opinion of i ∈ V \ U (t-1) is the following:

Theorem 4 The term X = (¯L+ I) + (-eili:) is invertible. Proof Expand X along the i-th row and we find:

where Mij is the minor of X. Denote the Laplacian matrix of sub-graph without node i as ¯L′ , then we have:

where C ∈ R(|V|-1)×(|V|-1) is a diagonal matrix, and cjj = |aji| for j < i and c(j-1)(j-1) = |a(j-1)i| for j > i. Like the proof of Theorem 1, we find Re(sp(¯L′ + I + C)) ≥ 1. Therefore, det(¯L′ +I+C) ̸= 0. As det(X) = Mii = det(¯L′ + I +C), the term X is invertible.

Thus, the benefit of fixing the expressed opinion of i in the t-th iteration is:

We first calculate the term eili:QU t-1 through:

This result illustrates that eili:QU t-1 is the matrix whose only non-negative row is the i-th row. And its i-th row is the negative QU t-1 i: with the addition of one in the i-th entry.

Then, we calculate the term li:QU t-1 ei through:

Input: A social trust network G = (V, E), internal opinions s, and budget µ. Output: The node set U, in which the node's expressed opinion will be fixed. Initialize U to empty set; t = 0; while t < µ do t = t + 1; Calculate the benefits b of fixing nodes' expressed opinions via equation (7); for i in V -U t-1 do if i == 1 then candidate = i; else if bi > bcandidate then candidate = i; U t = U t-1 ∪ candidate; Update QU t via equation (4);

Thus, we rewrite equation (5) as:

where we denote gU t-1 = (⃗1T QU t-1 )T as the contribution index vector after fixing the expressed opinions of nodes in

U t-1 . For convenience, we denote that zU t-1 ∗ = (z∗ |U t-1 ).

Based on equation (6), we integrate the calculation for each node into a simple expression:

where the i-th component of b indicates the benefit of fixing the expressed opinion of the i-th node and the operation diag(∗) expands a vector to a diagonal matrix or reverses the diagonal entries of a matrix. By using equation (7), we reduce the computational cost from O(|V|3 ) to O(|V|2 ), and this makes our SEOP method (see Algorithm 2) efficient. Equation (7) also constructs the relations between EOP, the fundamental matrix, and internal conflict [Chen et al., 2018], which may help to enable the analysis of simultaneous opinion maximization and conflict reduction in future works.

4 Experiments

In this section, we describe a series of experiments that were conducted to evaluate the proposed methods. We first introduce the datasets, the experimental setup, and then the experimental results for IOP and EOP, respectively.

4.1 Datasets

The real-world social trust networks used in the experiments are the following: (i) Alpha and (ii) OTC [Kumar et al., 2016; Kumar et al., 2018]. We normalized the trust values (i.e., edge weights) to the interval [-1, 1]. Moreover, we also tested our methods on Elec [Leskovec et al., 2010b; Leskovec et al., 2010a] and Rfa [West et al., 2014], as the relationships in these two networks are closely related to trust. The statistical details of these networks can be found in SNAP. 2

4.2 Experimental Setup

To simulate different situations, we randomly sampled values, which obey specific distributions, to initialize the internal opinion vector s. More precisely, for each network, we used five sets of internal opinions. (i) The internal opinions follow a uniform distribution (i.e., s ∼ U(-1, 1)). (ii) The internal opinions follow a standard normal distribution (i.e., s ∼ N(0, 1)). (iii) The absolute values of the internal opinions follow power-law distributions with α = 1 and α = 2 (i.e., |s| ∼ Pow(1) and |s| ∼ Pow(2)), and each entry of s is negated with a probability of 0.5. (iv) The internal opinion of a node positively correlates to that node's column connectivity (i.e., si ∝ ∑j |aji|), and each entry of s is negated with a probability of 0.5.

4.3 Comparative Methods

To the best of our knowledge, existing methods cannot solve IOP and EOP in STNs. For comparison, we modified the heuristics used in the existing studies.

For IOP, we consider four heuristics. (i) Rand [Li et al., 2013]. We randomly sort the nodes. (ii) Trust. This is slightly modified from the heuristics in [Chen et al., 2015]. We define the trust sum of a node as the sum of the corresponding column of the adjacency matrix. The node with large trust sum may have a strong ability to influence other nodes with their opinions. Therefore, we sort the nodes in descending order of their trust sum. (iii) IO. This was inspired by [Musco et al., 2018]. The overall opinion may increase if we can convince the people with negative internal opinions to have positive internal opinions. Therefore, we sort the nodes in ascending order of their internal opinions. (iv) EO. This was inspired by [Chen et al., 2018]. We sort the nodes in ascending order of their expressed opinions. After sorting the nodes, we change their internal opinions to 1 in order.

For EOP, we consider three heuristics. (i) Rand. (ii) IO. We do not consider EO in EOP, as the expressed opinion of the intervened node definitely equals its internal opinion. (iii) IOTS. This is a variation of "RWR" in [Gionis et al., 2013]. We consider comprehensively the internal opinion and the trust sum. More precisely, we sort the nodes in descending order of the product of the internal opinion and trust sum. After sorting, we fix the nodes' expressed opinions in order.

4.4 Solving Internal Opinion Problem

We evaluated our method for solving IOP and the results are reported in Table 1. Our method SIOP has an overwhelming advantage compared to the heuristic methods, as SIOP can achieve the optimal solution. The benefit of Rand is supposed to be µ||g||1/|V|, therefore Rand can achieve good performance if the contribution index distribution is dense. The Trust method is not competitive with the other heuristic methods, as the trust sum is not the only determinant in contribution index. Actually, a node that has a high contribution index must not be influenced by many other nodes.

2 http://snap.stanford.edu/data/

A part of the performance curves of SIOP, which can represent the overall performance, are shown in Figure 4. We observe that different internal opinions result in very different initial overall opinions, but our method always found the best solutions in different situations. As expected, the rate of overall opinion growth decreased as the amount of modified internal opinions increased. This is because our method preferentially modifies the internal opinion of the node with the largest absolute value of contribution index in each iteration. And a greater change in the overall opinion is achieved when modifying the internal opinion of the node with a larger absolute value of contribution index.

4.5 Solving Expressed Opinion Problem

We then evaluated our method for solving EOP. From the experimental results in Table 2, we observe that our method still has an overwhelming advantage over the heuristic methods. Rand performs badly in EOP, as only a few nodes are worth intervening to get a high benefit, but it is difficult to select out these nodes by a random heuristic. Compared to IO, IOTS is a competitive heuristic method, as it considers the internal opinion and trust sum simultaneously. But there is a big gap between SEOP and IOTS, because the high-order network structure is also closely related to the benefit of fixing the expressed opinion of a node, except for the trust sum based on 1st-order structure.

A part of performance curves of SEOP, which can represent the overall performance, are shown in Figure 5. We observe that in all the datasets, we can fix the expressed opinions of a few users to get very large benefits on the overall opinion. But with increasing iterations, the benefit of fixing the expressed opinion of a user declines quickly at first, and then slowly.

We also compare the running time of SEOP and SEOP

Table 3: Comparison of running time (of each iteration).

without optimization (see Table 3). 3 Note that the number of iterations equals the number of nodes whose expressed opinions are fixed. In the largest network Rfa, the total running time of SEOP is about 19s (µ = 200). It is clear that the integration of vast calculations makes our method efficient.

5 Conclusion

In this study, we formalized two novel problems for opinion maximization in social trust networks and proposed two matrix-based methods to solve these problems. In the internal opinion problem, we observed that nodes play very different roles in the social game. We defined the contribution index, with which we could easily achieve the optimal solution. For the expressed opinion problem, we proved its hardness and designed a greedy method to achieve an acceptable solution. We were able to integrate a vast number of calculations by crafty matrix operations to create an efficient method. In real-world applications, we may have to consider numerator factors to calculate the cost of a modification, but this can be easily combined with our methods.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (No. 61976162, 61976161), the Key Projects of Guangdong Natural Science Foundation (No. 2018B030311003), ARC DECRA (No. DE200100964), MQRSG (No. 95109718), and Investigative Analytics Collaborative Research Project between Macquarie University and Data61 CSIRO.

3 On a server with an Intel i9-9820x CPU and 64 GB RAM.