# opinion_maximization_in_social_trust_networks__2992fd63.pdf

Opinion Maximization in Social Trust Networks

Pinghua Xu1,2 , Wenbin Hu1,2 , Jia Wu3 , Weiwei Liu1

1School of Computer Science, National Engineering Research Center for Multimedia Software and Institute of Artificial Intelligence, Wuhan University 2Shenzhen Research Institute, Wuhan University 3Department of Computing, Macquarie University {xupinghua, hwb}@whu.edu.cn, jia.wu@mq.edu.au, liuweiwei863@gmail.com

Social media sites are now becoming very important platforms for product promotion or marketing campaigns. Therefore, there is broad interest in determining ways to guide a site to react more positively to a product with a limited budget. However, the practical significance of the existing studies on this subject is limited for two reasons. First, most studies have investigated the issue in oversimplified networks in which several important network characteristics are ignored. Second, the opinions of individuals are modeled as bipartite states (e.g., support or not) in numerous studies, however, this setting is too strict for many real scenarios. In this study, we focus on social trust networks (STNs), which have the significant characteristics ignored in the previous studies. We generalized a famed continuous-valued opinion dynamics model for STNs, which is more consistent with real scenarios. We subsequently formalized two novel problems for solving the issue in STNs. Moreover, we developed two matrix-based methods for these two problems and experiments on real-world datasets to demonstrate the practical utility of our methods.

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.

trust, strength 0.8

directed, signed,

(a) (b) 0.8

trust, strength

0.4 distrust, strength

0.4 trust, strength

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 i Phone.

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

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

1The implementations of the methods are available at https://github.com/WHU-SNA/Op Max In STN

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 = P j |aij|. Then L = D A denotes the generalized Laplacian matrix [Hu and Zheng, 2013]. Lemma 1 Inequality 0 min sp( 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:

( L + I)xi = Lxi + xi = (ki + 1)xi 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-Johnsen Model 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:

zi = si+P j N (i) wijzj

1+P j N (i) wij (1)

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:

c(zi) = (zi si)2 + P j N (i) |wij|(zi sgn(i, j)zj)2

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

zi = si+P j N (i) wijzj

1+P j N (i) |wij| (2)

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) 1s.

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

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.

c (z i ) = 2(z i si) + 2 P j N (i) |wij|(z i sgn(i, j)z j ) = 0

z i = si+P j N (i) wijz j

1+P j N (i) |wij| (3) 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 + P j N (i) |wij|)z i = si + P j N (i) wijz j

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

(D + I)z = s + Az (D A + I)z = s

( L + I)z = s

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

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: p(z ) = P i z i = 1 T ( L + I) 1s

where 1 is a column vector of ones.

3 Opinion Maximization 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:

max s 1 T ( L + I) 1(s + s)

s.t. 1 si + si 1 (i = 1, 2, 3, , |V|) s 1 µ

0.507 Modify the internal

After the first

Nash equilibrium

p( )=1.986 z*

0.395 0.310

0.395 0.310 Fix the expressed p( )=1.047 z*

opinion to 1

Initial state opinion exchange

0.303 0.388

p( )=1.016 z*

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.50 g = 0.63 g = 1.63 1

Figure 3: Example of the contribution index.

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 = ( 1 T ( L + I) 1)T as the contribution index vector. As

p(z ) = 1 T ( L + I) 1s = g T 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:

gi = ( 1 T ( L + I) 1)T i

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

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

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 value; if gi = 0 then

break; 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 g T 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 g T s + (|gj| |gi|)ν. According to the procedure of Algorithm 1, |gj| |gi|, thus g T s g T 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 U0, 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, QU0 = Q. According to Theorem 4, we compute QU0 i (equals to Q{i}) using the Sherman Morrison formula:

Q{i} = (( L + I) + ( eili:)) 1 = Q + Qeili:Q 1 li:Qei 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:

QUt 1 i = QUt 1 + QUt 1eili:QUt 1

1 li:QUt 1ei (4)

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

det(X) = P|V| j=1( 1)i+jxij Mij = ( 1)i+i Mii = Mii

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

Mii = det( L + I + C)

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:

1 T (QUt 1 i QUt 1)s = 1 T QUt 1eili:QUt 1

1 li:QUt 1ei s (5)

We first calculate the term eili:QUt 1 through:

eili:QUt 1 = ei((li: + e T i ) e T i )QUt 1

=ei(QUt 1) 1 i: QUt 1 eie T i QUt 1 = ei(e T i QUt 1 i: )

This result illustrates that eili:QUt 1 is the matrix whose only non-negative row is the i-th row. And its i-th row is the negative QUt 1 i: with the addition of one in the i-th entry. Then, we calculate the term li:QUt 1ei through:

li:QUt 1ei = ((li: + e T i ) e T i )QUt 1ei

=(e T i QUt 1 i: )ei = 1 q Ut 1 ii

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

Algorithm 2: Solving expressed opinion problem

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 Ut 1 do

if i == 1 then

candidate = i; else if bi > bcandidate then

candidate = i; Ut = Ut 1 candidate; Update QUt via equation (4);

Thus, we rewrite equation (5) as:

1 T (QUt 1 i QUt 1)s = 1 T QUt 1ei(e T i QUt 1 i: ) 1 (1 q Ut 1 ii ) s

=(g Ut 1)T ei(si z Ut 1 i ) q Ut 1 ii = g Ut 1 i q Ut 1 ii (si z Ut 1 i )

(6) where we denote g Ut 1 = ( 1 T QUt 1)T as the contribution index vector after fixing the expressed opinions of nodes in Ut 1. For convenience, we denote that z Ut 1 = (z |Ut 1). Based on equation (6), we integrate the calculation for each node into a simple expression:

b = diag(g Ut 1)(diag(QUt 1)) 1(s z Ut 1 ) (7)

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 P 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

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

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

Dataset Avg benefit of SIOP

SIOP vs Rand

SIOP vs Trust

Alpha 273.2 1.66 2.53 3.41 2.55 OTC 307.7 1.91 3.05 3.23 2.32 Elec 589.9 3.63 > 10 2.97 2.21 Rfa 981.0 > 10 > 10 8.61 3.96

Table 1: Experimental results on IOP.

Uniform S Norm S Alpha Alpha

Pow Alpha1S OTC

Figure 4: A part of the performance curves of SIOP. The x-axis shows the budget amount, the left y-axis shows the overall opinion, and the right y-axis shows the unit benefit.

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. 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

Dataset Avg benefit of SEOP

SEOP vs Rand

SEOP vs IOTS

Alpha 192.1 > 10 4.99 1.30 OTC 220.6 > 10 5.47 1.86 Elec 65.2 > 10 4.50 2.87 Rfa 314.9 > 10 6.92 3.66

Table 2: Experimental results on EOP.

Alpha Norm S Pow Alpha1S OTC

Degree S OTC

Figure 5: A part of the performance curves of SEOP.

Alpha OTC Elec Rfa

SEOP 13.1ms 31.1ms 43.9ms 93.9ms Non-optimized SEOP 4.7k 7.3k > 10k > 10k

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.

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

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

References [Abebe et al., 2018] Rediet Abebe, Jon Kleinberg, David Parkes, and Charalampos E. Tsourakakis. Opinion dynamics with varying susceptibility to persuasion. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, page 1089 1098, 2018. [Bindel et al., 2015] David Bindel, Jon Kleinberg, and Sigal Oren. How bad is forming your own opinion? Games and Economic Behavior, 92:248 265, 2015. [Chen et al., 2015] Shuo Chen, Ju Fan, Guoliang Li, Jianhua Feng, Kian-lee Tan, and Jinhui Tang. Online topic-aware influence maximization. Proceedings of the VLDB Endowment, 8(6):666 677, 2015. [Chen et al., 2016] Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, and Xuren Zhou. Robust influence maximization. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 795 804. ACM, 2016. [Chen et al., 2018] Xi Chen, Jefrey Lijffijt, and Tijl De Bie. Quantifying and minimizing risk of conflict in social networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery &amp; Data Mining, pages 1197 1205. ACM, 2018. [Friedkin and Johnsen, 1990] Noah E. Friedkin and Eugene C. Johnsen. Social influence and opinions. Journal of Mathematical Sociology, 15(3-4):193 206, 1990. [Gionis et al., 2013] Aristides Gionis, Evimaria Terzi, and Panayiotis Tsaparas. Opinion maximization in social networks. Computer Science, 69(2):31 33, 2013. [Hu and Zheng, 2013] Jiangping Hu and Wei Xing Zheng. Bipartite consensus for multi-agent systems on directed signed networks. In 52nd IEEE Conference on Decision and Control, pages 3451 3456. IEEE, 2013. [Islam et al., 2018] Mohammad Raihanul Islam, B Aditya Prakash, and Naren Ramakrishnan. Signet: scalable embeddings for signed networks. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 157 169. Springer, 2018. [Kumar et al., 2016] Srijan Kumar, Francesca Spezzano, VS Subrahmanian, and Christos Faloutsos. Edge weight prediction in weighted signed networks. In Data Mining (ICDM), 2016 IEEE 16th International Conference on, pages 221 230. IEEE, 2016. [Kumar et al., 2018] Srijan Kumar, Bryan Hooi, Disha Makhija, Mohit Kumar, Christos Faloutsos, and VS Subrahmanian. Rev2: Fraudulent user prediction in rating platforms. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 333 341. ACM, 2018. [Leskovec et al., 2010a] Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Predicting positive and negative links in online social networks. In Proceedings of the 19th international conference on World wide web, pages 641 650. ACM, 2010.

[Leskovec et al., 2010b] Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Signed networks in social media. In Proceedings of the SIGCHI conference on human factors in computing systems, pages 1361 1370. ACM, 2010. [Li et al., 2013] Yanhua Li, Wei Chen, Yajun Wang, and Zhi Li Zhang. Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. In Proceedings of the sixth ACM international conference on Web search and data mining, pages 657 666. ACM, 2013. [Li et al., 2017] Dong Li, Cuihua Wang, Shengping Zhang, Guanglu Zhou, Dianhui Chu, and Chong Wu. Positive influence maximization in signed social networks based on simulated annealing. Neurocomputing, 260:69 78, 2017. [Li et al., 2018] Yuchen Li, Ju Fan, Yanhao Wang, and Kian Lee Tan. Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 30(10):1852 1872, 2018. [Liu et al., 2018] Xinyue Liu, Xiangnan Kong, and Philip S Yu. Active opinion maximization in social networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1840 1849, 2018. [Musco et al., 2018] Cameron Musco, Christopher Musco, and Charalampos E Tsourakakis. Minimizing polarization and disagreement in social networks. In Proceedings of the 2018 World Wide Web Conference, pages 369 378. International World Wide Web Conferences Steering Committee, 2018. [West et al., 2014] Robert West, Hristo S Paskov, Jure Leskovec, and Christopher Potts. Exploiting social network structure for person-to-person sentiment analysis. Transactions of the Association for Computational Linguistics, 2:297 310, 2014. [Xu et al., 2019] Pinghua Xu, Wenbin Hu, Jia Wu, Weiwei Liu, Bo Du, and Jian Yang. Social trust network embedding. In Proceedings, 19th IEEE International Conference on Data Mining, pages 678 687, 2019. [Yang et al., 2016] Yu Yang, Xiangbo Mao, Jian Pei, and Xiaofei He. Continuous influence maximization: What discounts should we offer to social network users? In Proceedings of the 2016 international conference on management of data, pages 727 741. ACM, 2016.

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)