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

Introduction

In social media marketing, "influence maximization" typically involves identifying key users to shift a network's sentiment. However, traditional research often treats opinion as a binary state—either supporting or opposing a product. Real-world social dynamics are more complex: individuals hold varying degrees of support, and interactions are shaped by both trust and distrust. A recent study by Xu et al. addresses these complexities by modeling continuous-valued opinions within Social Trust Networks (STNs).

Social Trust Networks and Opinion Dynamics

Traditional models often overlook directionality, the continuous nature of opinions, and the impact of distrust. In a "signed" network, a negative edge (distrust) implies that an individual may move their opinion away from a distrusted neighbor's position.

Social Trust Network (STN) representation with directed, signed, and weighted edges.

The authors build upon the Friedkin-Johnsen (FJ) model, where an individual's expressed opinion is a weighted average of their internal belief and the opinions of their neighbors. They generalize this for STNs, represented as directed, signed, and weighted graphs.

Optimization Problems

The study formalizes two distinct optimization problems under a limited budget:

  1. Internal Opinion Problem (IOP): Identifying which individuals' private beliefs should be modified (e.g., through targeted education) to maximize the global opinion equilibrium.
  2. Expressed Opinion Problem (EOP): Selecting individuals to become "stubborn" influencers whose public opinions remain fixed, regardless of social pressure.

To solve these, the researchers introduced the Contribution Index. By utilizing matrix inversion, they can quantify how much a single node's internal belief contributes to the network's final state.

Key Insights and Results

One of the most significant findings is the concept of the "Anti-Influencer." Due to distrust, some nodes possess a negative contribution index. If a widely distrusted individual vocally supports a product, the overall network sentiment may decrease.

The Contribution Index (g) illustrates how individual nodes influence the global opinion equilibrium across different network structures.

The researchers evaluated their methods on real-world datasets, including Bitcoin trust networks (Alpha, OTC) and Wikipedia voting data (Elec, Rfa). Key results include:

  • Mathematical Optimality: The SIOP method for internal opinions was proven optimal, significantly outperforming standard heuristics.
  • Greedy Efficiency: For the ambassador problem (EOP), the SEOP method consistently outperformed heuristics. By applying the Sherman-Morrison formula, the authors reduced the computational complexity from $O(V^3)$ to $O(V^2)$, resulting in a speedup of over 10,000x on large datasets.

Conclusion

This framework provides a robust mathematical approach to opinion maximization in complex social environments. While the current model assumes uniform costs for modifying opinions, future work could incorporate variable costs based on a user's social standing or existing biases. Additionally, exploring dynamic network structures where trust evolves alongside opinions remains a promising avenue for research.

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