Source-linked AI summary
Minimizing Polarization and Disagreement in Social Networks
Cameron Musco, Christopher Musco, Charalampos E. Tsourakakis
TL;DR
The paper asks how social networks should be structured to minimize polarization and disagreement simultaneously, a trade-off relevant to recommender systems. It formalizes this objective, develops optimization procedures, and proves approximation guarantees. Experiments show substantial reductions on real-world networks, while runtime and non-convexity impose stated limitations.
Problem
The paper addresses how a network can minimize polarization and disagreement simultaneously when recommender systems may favor either similar or different opinions.
Method
The paper formulates joint optimization over graph topologies and innate opinions, using the Friedkin-Johnsen model and convex optimization for graph structure.
Results
6.2 × 10^4-fold reduction in polarization and disagreement was achieved on the Reddit dataset by optimizing graph topology.
Takeaways & Limitations
O(n/ε^2) edges suffice for a (1 + ε)-approximation, and the methods provide tools for understanding polarization-disagreement trade-offs in real networks.
Takeaways & Limitations
For ρ = 0, the objective is non-convex, and the optimization runtime remains an open efficiency question as variables grow as O(n^2).
Abstract
from arXiv · showhide
The rise of social media and online social networks has been a disruptive force in society. Opinions are increasingly shaped by interactions on online social media, and social phenomena including disagreement and polarization are now tightly woven into everyday life. In this work we initiate the study of the following question: given $n$ agents, each with its own initial opinion that reflects its core value on a topic, and an opinion dynamics model, what is the structure of a social network that minimizes {\em polarization} and {\em disagreement} simultaneously? This question is central to recommender systems: should a recommender system prefer a link suggestion between two online users with similar mindsets in order to keep disagreement low, or between two users with different opinions in order to expose each to the other's viewpoint of the world, and decrease overall levels of polarization? Our contributions include a mathematical formalization of this question as an optimization problem and an exact, time-efficient algorithm. We also prove that there always exists a network with $O(n/ε^2)$ edges that is a $(1+ε)$ approximation to the optimum. For a fixed graph, we additionally show how to optimize our objective function over the agents' innate opinions in polynomial time. We perform an empirical study of our proposed methods on synthetic and real-world data that verify their value as mining tools to better understand the trade-off between of disagreement and polarization. We find that there is a lot of space to reduce both polarization and disagreement in real-world networks; for instance, on a Reddit network where users exchange comments on politics, our methods achieve a $\sim 60\,000$-fold reduction in polarization and disagreement.
1 Introduction
The paper studies how social-network structure and innate opinions can jointly minimize polarization and disagreement under opinion dynamics. It formalizes these trade-offs for recommender systems, develops optimization methods, and evaluates them on synthetic and real networks.
- Motivation: Confirmation bias favors links between users with similar mindsets, which can create echo chambers and polarized communities.Such recommendations minimize experienced disagreement but may increase polarization between groups.
- Contributions: The paper formalizes graph-topology optimization and provides a polynomial-time algorithm based on convexity.It also studies changing innate opinions under a bounded opinion-mass budget for a fixed network.
- Research problem: The central problem is to find a connected network with fixed total edge weight that minimizes polarization and disagreement simultaneously.Each agent has an initial opinion reflecting a core value, and the paper uses the Friedkin-Johnsen model.
- Contributions: O(n/ε^2) edges suffice for a (1 + ε)-approximation, showing that sparse networks can nearly minimize the combined objective.The result applies to the graph-topology problem.
- Empirical findings: 6.2 × 10^4-fold reduction in polarization and disagreement was obtained on the Reddit dataset by optimizing graph topology.Experiments on synthetic and real data also found that existing topologies are far from optimal.
2 Related Work
The related work spans opinion-dynamics models, polarization and echo-chamber studies, opinion mining, and optimization over graph topologies. The paper positions its contribution as the first formal study of jointly minimizing polarization and disagreement through network structure.
- Positioning: The paper claims to be the first to formally define and study the optimization problems introduced for jointly minimizing polarization and disagreement.This establishes its stated novelty relative to the reviewed literature.
- Modeling opinion dynamics: Opinion-dynamics research models social learning processes relevant to voting, viral marketing, and social-media phenomena.Models include discrete mechanisms such as copying a neighbor or applying a local majority rule, alongside continuous models.
- Modeling opinion dynamics: The Friedkin-Johnsen model extends DeGroot by combining persistent innate beliefs with neighborhood averaging.Each node maintains an innate opinion while repeatedly updating its expressed opinion.
- Polarization: Prior polarization work includes tools for exposing users to opposing views, highlighting opinion extremity, and empirical studies of political echo chambers.Other work also proposes nonlinear models to represent extreme polarization.
- Closest prior work: The closest prior work minimizes a polarization-related equilibrium norm by modifying selected innate opinions, but it is NP-hard and does not consider disagreement.The present paper instead studies the joint objective over network topology and opinions.
- Optimizing over graph topologies: Related graph-topology studies optimize objectives involving Laplacians, reconstruction error, evolutionary trees, graphical models, or Markov-chain mixing.These approaches generally lie outside graph mining, which has focused more on edge recommendation than global structure.
3 Proposed Method
The method defines polarization and disagreement at equilibrium, combines them into a single graph objective, and optimizes this objective over valid connected graph Laplacians with fixed total edge weight. Convexity enables polynomial-time optimization, while spectral sparsification provides near-optimal sparse networks.
- Definitions: Polarization measures the variance of equilibrium opinions around their mean, while disagreement sums squared equilibrium-opinion differences across graph edges.The equilibrium opinion vector is generated by the Friedkin-Johnsen model.
- Trade-off: A three-agent example shows that connecting agents with different opinions can reduce the combined objective despite introducing disagreement.With innate opinions [0, 0, 1], the cross-opinion edge yields polarization 0.222 and disagreement 0.111, versus polarization 0.667 and disagreement 0 for the same-opinion edge.
- Objective: The paper minimizes the sum of polarization and disagreement, equivalent to minimizing the polarization-disagreement index over connected graphs with fixed total edge weight.The Laplacian trace equals twice the graph’s total edge weight.
- Graph-topology optimization: The objective is convex in graph edge weights, so the graph-topology optimization problem is solvable in polynomial time.The objective can be rewritten as a quadratic form involving (I + L)^−1, and the method derives a closed-form gradient for efficient gradient descent.
- Graph-topology optimization: Weighting polarization and disagreement differently can destroy convexity: for ρ = 0, the generalized objective is non-convex in the edge weights.The paper notes that additional counterexamples exist for other ρ values.
4 Experimental results
Experiments on synthetic and real-world networks evaluate graph-topology and opinion-intervention methods for reducing the polarization-disagreement index. The results show substantial reductions, with sparsification preserving objective values while greatly reducing edge counts, although optimization remains computationally costly.
- Synthetic experiments: Synthetic experiments compare optimal graph topologies, sparsified solutions, Erdős-Rényi graphs, and power-law graphs across power-law opinion distributions.The experiments average polarization-disagreement indices over five trials for opinion-distribution slopes 1.5, 2, and 2.5.
- Synthetic experiments: Erdős-Rényi graphs achieve close-to-optimal performance, whereas power-law networks generally perform worse and show increasing index values as their slope rises from 2 to 3.
- Opinion interventions: The intervention algorithm tends to reduce high innate opinions, but graph topology can redirect changes toward lower-opinion nodes, especially under the smaller budget α = 5.As the budget increases, the algorithm can reduce the highest innate opinions more consistently and becomes less constrained by topology.
- Real-world experiments: On real-world networks, optimizing graph topology sharply lowers the polarization-disagreement index, while effective-resistance sparsification preserves the reduction with far fewer edges.For Reddit, the index decreases from 199.84 to 0.0022; the sparsified solution uses 7,521 edges and differs from the optimum by less than 10^-5.
- Real-world experiments: The optimized graphs do not exhibit the expected two-block community structure and instead appear closer to random, leaving their structural explanation open.
- Limitations: Optimization takes a couple of hours per network because the number of variables grows as O(n^2).The paper identifies an efficient primal-dual procedure exploiting the convex programs and sparsification theorem as an open question.
- Opinion interventions: Increasing the intervention budget moves equilibrium opinions closer to the average and produces significantly lower objective values on Twitter and Reddit.Figure 2 compares innate opinions, uninfluenced equilibrium opinions, and equilibria after interventions with budgets 5 and 20.
5 Conclusion
The paper formulates polarization and disagreement as a joint optimization problem and develops efficient methods for graph topologies and fixed-network opinions. Empirical studies on synthetic, Twitter, and Reddit data demonstrate the tools’ usefulness, while the conclusion identifies extensions beyond the Friedkin-Johnsen model and current objectives.
- The paper introduces the polarization-disagreement index and optimizes graph topologies to minimize their combined objective.It also provides procedures for optimizing innate opinions when the network is fixed.
- The authors provide an extensive empirical study using synthetic data and Twitter and Reddit datasets.The tools are intended to reveal the importance of edges and nodes in opinion formation.
- The Friedkin-Johnsen model is a current scope boundary, leaving the same optimization questions open under other opinion dynamics models.The conclusion also raises questions about Erdős-Rényi graphs, expanders, cross-community links, weighted objectives, and other social-good objectives.