Opinion Maximization in Social Trust Networks

Pinghua Xu, Wenbin Hu, Jia Wu, Weiwei Liu

Abstract

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. In addition, we developed two matrix-based methods for these two problems and experiments on real-world datasets to demonstrate the practical utility of our methods.

Introduction

Traditional models of influence maximization often simplify social dynamics by treating opinions as binary states—either an individual supports a product or they do not. However, real-world opinions are more nuanced and continuous, often represented by scales such as 5-star ratings. Furthermore, existing research frequently overlooks the complexities of Social Trust Networks (STNs), which are characterized by directionality (influence flows from key leaders to followers), varying weights of influence, and the presence of both trust and distrust (signed edges).

This paper addresses these gaps by generalizing the Friedkin-Johnsen (FJ) model to STNs, allowing for the study of continuous opinion dynamics in environments where distrust can lead individuals to adopt opposing views, a concept rooted in structural balance theory.

Modeling Opinion Dynamics and Optimization Problems

In the generalized FJ model, an individual's expressed opinion is a weighted equilibrium between their internal belief and the opinions of those they trust or distrust. The researchers formalize two distinct optimization challenges under a limited budget:

  1. Internal Opinion Problem (IOP): Identifying which individuals' internal beliefs should be modified to maximize the network's aggregate opinion.
  2. Expressed Opinion Problem (EOP): Identifying which users' public stances should be "fixed" or immunized from outside influence to achieve the same goal.
Figure 4: Illustration of opinion evolution from initial state to Nash equilibrium under different optimization scenarios: (a) baseline evolution, (b) the Internal Opinion Problem (IOP) where an internal belief is modified, and (c) the Expressed Opinion Problem (EOP) where a public stance is fixed.

The Contribution Index and Key Insights

A central contribution of this work is the Contribution Index (CI), a metric derived from the generalized Laplacian matrix. The CI quantifies the exact impact a single node's internal opinion has on the entire network's equilibrium.

A striking finding is the existence of the "Negative Influencer." In signed networks, nodes that are widely distrusted can have a negative contribution index. In such cases, making that individual's internal opinion more positive actually drives the rest of the network toward a more negative collective stance. Conversely, Key Opinion Leaders (KOLs) act as sources of influence that do not dissipate through feedback loops, mathematically confirming their disproportionate impact.

Figure 5: The Contribution Index (g) across various network topologies. Subfigure (d) demonstrates the 'negative influencer' phenomenon, where negative trust edges result in a negative contribution index (g = -2.50).

Methodology and Results

The researchers developed two matrix-based algorithms: SIOP for the internal opinion problem and SEOP for the expressed opinion problem. While SIOP provides an optimal greedy solution, SEOP addresses an NP-hard problem using the Sherman-Morrison formula for rapid matrix updates.

Experimental evaluations on real-world datasets (Alpha, OTC, Elec, and Rfa) demonstrated that these methods significantly outperform traditional heuristics like "Trust Sum." Notably, the optimized SEOP algorithm achieved speedups of up to 10,000x compared to non-optimized versions, enabling the processing of large-scale networks in milliseconds.

Conclusion

By moving beyond binary influence models and incorporating the realities of trust and distrust, this framework provides a more accurate tool for opinion maximization in social networks. Future work may expand this model to account for non-linear costs of influence and dynamic network topologies where trust relationships evolve alongside opinions.

Summary updated

Abstract

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. In addition, we developed two matrix-based methods for these two problems and experiments on realworld datasets to demonstrate the practical utility of our methods.
BibTeX
@inproceedings{xu2020opinion,
  author = {Pinghua Xu and Wenbin Hu and Jia Wu and Weiwei Liu},
  title = {{Opinion Maximization in Social Trust Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=OzWrrnv7vfA},
}
Figure