Skip to content
Reducing Controversy by Connecting Opposing Views

Reducing Controversy by Connecting Opposing Views

Authors: Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, Michael Mathioudakis

Venue: WSDM 2017 — arXiv

TL;DR

This paper proposes an algorithmic approach to reduce polarization on social media by recommending social connections (edges) between opposing sides. Using an endorsement graph representation and the random-walk-based controversy metric, the authors formulate the problem as k-edge-addition and develop an efficient algorithm (ROV) that considers only high-degree nodes, outperforming naive greedy approaches while remaining orders of magnitude faster.

Contributions

  • First algorithmic approach (language- and domain-agnostic) to bridging echo chambers by identifying who to recommend opposing-view content to, rather than what to recommend.
  • Formulation of the problem as edge-recommendation on an endorsement graph, seeking edges that minimize expected controversy score under an acceptance probability model.
  • Development of user-level polarity scores to estimate the probability that a recommended edge materializes in practice.
  • Efficient algorithm (ROV) based on the observation that connecting high-degree nodes across sides reduces controversy most, with O(k₁ · k₂) complexity instead of O(n²) greedy or O(n² choose k) brute-force.
  • Incremental RWC computation using Sherman-Morrison matrix updates, yielding 5–65× speedup.
  • Extensive evaluation on 10 Twitter datasets of controversial hashtags, showing that ROV-AP (with acceptance probabilities) recommends realistic, feasible bridges.

Method

Problem Formulation. Given an endorsement graph G = (V, E) partitioned into opposing sides X and Y, find k edges to add that minimize the random-walk controversy (RWC) score. RWC is based on the probability that a random walk starting from one side stays on that side vs. crossing to the other.

Algorithmic Insight. The paper proves (via an exemplary two-star network) that edges connecting high-degree hub nodes across sides reduce controversy the most. This motivates ROV: consider only the k₁ highest in-degree nodes in X and k₂ in Y, evaluate all k₁ · k₂ candidate edges, and select the top k.

Acceptance Probabilities. In reality, not all recommended edges materialize. The paper extends ROV to ROV-AP, which estimates p(u, v) — the probability that user u endorses user v if recommended — using user polarity scores. Polarity is computed via hitting times in a random walk: users in the middle (low |polarity|) are easier to convince. Acceptance probability is estimated empirically as the fraction of exposed-to endorsements for users with polarity pair (R_u, R_v).

Optimization. To select edges maximizing expected controversy reduction E(u, v) = p(u, v) · δRWC_{u→v}, the algorithm uses Fagin's algorithm to merge two ranked lists (by RWC decrease and by acceptance probability).

Incremental Computation. Instead of recomputing RWC from scratch after each edge addition, the Sherman-Morrison formula allows updating RWC in O(k) time. The change in RWC when edge (a, b) is added depends only on vectors z_x, z_y (related to the transition matrix column for node a) and u (a unit basis vector), avoiding expensive matrix inversions.

Results

Edge-Addition Strategies. On all 10 Twitter datasets, connecting high-degree nodes across sides yields the largest controversy reduction, validating the theoretical motivation.

Algorithm Comparison. ROV matches or nearly matches the greedy baseline (which evaluates all O(n²) edges) in controversy score reduction, while being orders of magnitude faster. ROV-AP incurs slightly lower reduction but dramatically improves feasibility: recommendations involve less popular, more "persuadable" users with higher overlap in tweet content.

Case Study. On obamacare, guncontrol, and #netanyahuspeech: - ROV recommends edges between extreme users (e.g., mittromney → barackobama) which are unlikely to materialize. - ROV-AP recommends more realistic bridges: e.g., (csgv, dloesch) for guncontrol, connecting a pro-gun-control org to a conservative radio host; (farhankvirk, pamelageller) on #netanyahuspeech, linking an Islamist blogger with an anti-Islam activist.

Quantitative Metrics. ROV-AP edges involve lower-follower-count users (median 36k followers vs. 51k for ROV), higher content overlap (Jaccard similarity 0.073 vs. 0.054), and more common retweet endorsements (0.063 vs. 0.029).

Time Performance. Both ROV and ROV-AP run 1–3 orders of magnitude faster than related graph-modification methods (NetGel, MioBi, Shortcut), with incremental computation providing 5–65× speedup over non-incremental variants.

Connections

Notes

Strengths: - Novel problem formulation that directly addresses echo-chamber bridging at the user selection level. - Efficient algorithm with strong theoretical motivation (high-degree nodes as effective bridges). - Realistic acceptance-probability model grounded in user-study findings and empirical polarity estimation. - Comprehensive evaluation on real Twitter data with both quantitative metrics and qualitative case studies. - Practical applicability: ROV-AP recommendations are feasible and interpretable.

Limitations: - Limited to binary controversies (two opposing sides). Multi-faceted or fuzzy controversies not addressed. - Polarity scores computed from historical endorsements; may not generalize to entirely new users or shifting controversies. - Evaluation relies on Twitter data; generalization to other platforms assumed but not validated. - User study on acceptance probabilities (cited from prior work) is not directly validated on recommended edges—open question whether users actually adopt ROV-AP suggestions. - No long-term outcomes: does adding recommended edges actually reduce controversy and polarization over time?

Open Questions: - How sensitive are results to graph-construction choices (retweet threshold, time window, user filtering)? - Can the approach be extended to multi-way controversies (3+ sides)? - Do recommended edges, if adopted, sustainably reduce polarization or are they short-lived interventions? - How does the approach perform on controversies with evolving stances (e.g., political realignment)?