PaperlayerView exact revision on arXiv

Source-linked AI summary

Rewiring the Majority: Structural Median Opinion Control in the Friedkin-Johnsen Model

Elisabetta Biondi, Chiara Boldrini, Andrea Passarella, Marco Conti

arXiv:2610.21933v1cs.SI

TL;DR

Opinion control under FJ dynamics has largely targeted individual agents, leaving open whether majority outcomes can instead be steered by changing the network. This paper formulates edge-addition control of the equilibrium median and develops optimization methods and heuristics. Its results show that intervention effectiveness depends on network and opinion conditions, while structural interventions can become cost-effective against node-level control when high-reach users are costly to target.

  • Problem

    Prior FJ median-control work modifies agents, leaving open whether edge additions can shift the equilibrium median and majority outcome.

    Source: Introduction · pp. 1–2

  • Method

    The paper formulates structural median control as an edge-addition problem and proposes continuous optimization methods and lighter opinion-aware heuristics.

    Source: Introduction · p. 2, Conclusions · p. 10

  • Results

    Structural success depends jointly on topology, opinion placement, and susceptibility; under homogeneous susceptibility, structural interventions become competitive and often more cost-effective when high-reach users are costly to target.

    Source: Conclusions · p. 10

  • Takeaways & Limitations

    Structural interventions can shift majority outcomes when added edges create favorable influence pathways, and their relative appeal depends on the cost of targeting high-reach users.

    Source: Conclusions · p. 10

    Continuous optimization uses fractional edge activations and a smooth median surrogate, so rounded edge sets may be less effective, especially with small budgets or specific edge-combination requirements.

    Source: Opinion-Aware Heuristics · p. 5

Abstract

from arXiv · show

Opinion control under the Friedkin-Johnsen (FJ) model has traditionally focused on modifying individual users, for example by changing their opinions or susceptibility to social influence. We study a complementary problem: can collective outcomes be steered by modifying the interaction network instead? We formulate structural median control as an edge-addition problem aimed at moving the equilibrium median beyond a target threshold. We show that the problem is NP-hard even under highly restricted settings and propose both continuous optimization methods and computationally lighter opinion-aware heuristics for selecting edge additions. Experiments on synthetic and real-world networks reveal that intervention success depends jointly on network topology, the placement of favorable opinions, and user susceptibility. Structural interventions produce the largest shifts when opinion placement and network structure allow added edges to create useful influence pathways toward the target outcome. Finally, under a homogeneous reference setting, we compare structural and node-level interventions using normalized budgets and a degree-weighted cost model. We show that, although node interventions often appear stronger under normalized budgets, structural interventions become competitive and frequently more cost-effective once the higher cost of targeting high-reach users is taken into account.

Introduction

The paper asks whether adding edges can steer the FJ equilibrium median—and thus a majority outcome—rather than modifying individual agents. It formulates this structural control problem and studies its methods, dependencies, and comparison with node-level interventions.

Introduction

  • The FJ model incorporates susceptibility to social influence and partial anchoring to innate opinions, allowing persistent disagreement at equilibrium.The paper uses this model to study how collective outcomes depend on interaction structure.Source: Introduction · p. 1
  • The median captures which side of a threshold contains a majority, unlike the mean, which may shift without changing most agents’ positions.Its dependence on opinion ordering also makes it insensitive to a small number of extreme values.Source: Introduction · p. 1
  • Structural median control complements node-level interventions by changing the interaction network to move the equilibrium median beyond a target threshold.The proposed interventions add edges that create influence pathways from agents needing to shift toward agents already aligned with the target.Source: Introduction · pp. 1–2
  • The study asks how topology, opinion placement, and susceptibility affect whether edge additions flip the median, how they perform on real-world networks, and how they compare with node interventions under different budgets.The comparison includes normalized and cost-calibrated budgets.Source: Introduction · p. 2
  • Structural interventions reverse the equilibrium majority on real-world networks with at most 27% of the original edge count in additions; on Polblogs, a method succeeds with about 11% while no tested node-level method reaches the target.The study evaluates homogeneous and heterogeneous susceptibility regimes on synthetic and real-world networks.Source: Introduction · p. 2
  • The paper combines continuous optimization with lighter opinion-aware edge-selection heuristics and studies their dependence on topology, opinion placement, and susceptibility.It frames the task as a non-smooth median objective whose edge decisions affect the FJ equilibrium nonlinearly.Source: Introduction · p. 2

Related Work

Prior opinion-control work has mainly modified node-level quantities, while structural design has addressed other opinion-dynamics objectives. This paper combines structural edge additions with a threshold-crossing median objective.

Related Work

  • Prior FJ control studies fix expressed opinions, perturb innate opinions, modify susceptibility, or optimize under limited information, but leave the interaction structure unchanged.These studies include work on opinion optimization in directed networks.Source: Related Work · p. 2
  • Earlier FJ median-flipping work intervenes on susceptibility and develops continuous and combinatorial methods, whereas this paper adds edges to change who influences whom.Both approaches retain the median-centric objective.Source: Related Work · p. 2
  • Structural network design has targeted polarization, disagreement, conflict, or distance from consensus; this work instead optimizes a threshold-crossing median outcome.The edge-addition setting is motivated by link-recommendation systems.Source: Related Work · p. 2

Modeling Framework

The framework models directed following networks with FJ opinion dynamics and defines structural interventions as additions of missing non-self edges. It formulates median maximization and threshold crossing under an edge budget, focusing on edge addition rather than other structural changes.

Friedkin-Johnsen Opinion Dynamics

  • In the FJ model, each user’s opinion update combines an innate opinion with influence from followed users, weighted by susceptibility; under mild conditions, opinions converge to a unique equilibrium.The influence matrix is formed by row-normalizing the adjacency matrix, giving equal weight to each followed user.Source: Friedkin-Johnsen Opinion Dynamics · pp. 2–3

Structural interventions

  • Structural interventions activate a subset of missing directed edges without self-loops, then recompute the influence matrix by row-normalizing the modified binary adjacency matrix.Influence remains uniformly distributed among each user’s outgoing neighbors.Source: Structural interventions · p. 3
  • The framework focuses exclusively on edge addition; rewiring and edge removal are not included, and weighted networks would require specifying new-edge influence and weight redistribution.These extensions are left for future work.Source: Structural interventions · p. 3

Problem Formulation

  • The optimization objectives use the equilibrium median after adding edges, either maximizing it under a cardinality budget or minimizing the additions needed to reach a threshold.The threshold formulation captures majority flipping when the initial median lies below the target.Source: Problem Formulation · p. 3
  • The decision version asks whether at most k additions can cross a threshold; it is used for complexity analysis, while the paper’s optimization focus is median maximization and threshold minimization.The two optimization directions are related by complementing innate opinions and transforming the threshold.Source: Problem Formulation · p. 3

Computational Hardness

Structural median control is NP-hard even with binary innate opinions, homogeneous susceptibility, and a fixed threshold. The reduction from Vertex Cover encodes vertex selection as edge additions that move both gadget users and covered targets above the threshold.

Computational Hardness

  • Structural median threshold decision is NP-hard even when all missing non-self edges are admissible, opinions are binary, susceptibility is homogeneous, and the threshold is fixed between zero and one.The result implies NP-hardness for both edge-addition median maximization and threshold minimization.Source: Computational Hardness · pp. 3–4
  • The reduction represents each Vertex Cover vertex by a two-user gadget; adding an edge from that gadget to a positive anchor moves its users above the threshold and can also move targets for incident edges.Each target is influenced by representatives of the two endpoints, so activating either endpoint gadget covers that target.Source: Computational Hardness · p. 3
  • The construction is polynomial and succeeds exactly when the source graph has a vertex cover of size at most k.Without such a cover, the counting argument leaves the number of users above threshold one short of that needed to move the median.Source: Computational Hardness · p. 4
  • The hardness holds under binary opinions, homogeneous susceptibilities, and a fixed threshold, so it is not attributable to complex opinion spaces or heterogeneous agent parameters.The paper attributes the difficulty to the combinatorial choice of structural interventions.Source: Computational Hardness · p. 4

Structural Optimization Methods

Structural median control is NP-hard, so the paper combines continuous relaxations with discrete opinion-aware heuristics to select edge additions. The methods use the equilibrium opinion landscape to target the median or threshold crossing while accounting for the computational cost of selection.

Continuous Optimization

  • Continuous relaxations assign influence-allocation variables to latent edges, optimize smooth objectives, then rank candidates for discrete top-k selection.Because added edges reweight existing neighbors through row normalization, relaxed solutions can lose effectiveness when rounded, especially with small budgets or combination-dependent median changes.Source: Structural Optimization Methods · p. 4, Continuous Optimization · pp. 4–5
  • The Huber policy maximizes a smoothed median surrogate that limits the influence of extreme opinions.Its loss is quadratic near the center and has linear tails.Source: Continuous Optimization · p. 4
  • The Sigmoid policy maximizes a smooth proxy for the number of nodes above θ, emphasizing opinion changes near the threshold.The sigmoid saturates far from θ.Source: Continuous Optimization · p. 5

Opinion-Aware Edge Selection (OAES)

  • Opinion-aware heuristics rank candidate edges using the current equilibrium opinions and exposure improvement over each receiver’s neighborhood.The first heuristic prioritizes positive exposure improvement for receivers near the target threshold, where shifts may be decisive for the median.Source: Opinion-Aware Heuristics · p. 5, Opinion-Aware Edge Selection (OAES) · p. 5

Threshold-Aware Opinion-Aware Edge Selection (OAES-Aware)

  • OAES-Aware additionally favors sources strongly aligned with the target, alongside near-threshold receivers and substantial exposure improvement.Its source-awareness factor distinguishes strongly favorable sources from those only marginally above the threshold.Source: Threshold-Aware Opinion-Aware Edge… · p. 5

Computational Complexity and Scalability

  • OAES and OAES-Aware require one equilibrium computation, while Huber and Sigmoid require two linear-system solves per iteration.Under the dense implementation, the heuristics incur roughly one equilibrium computation rather than 2T dominant O(n^3) costs for continuous methods.Source: Computational Complexity and Scalability · p. 5, Table 1 · p. 6

Experimental Setup

The evaluation combines controlled opinion configurations with real-world datasets to examine how topology, opinion placement, and susceptibility shape structural intervention outcomes. It compares structural and node-level interventions under normalized fractions and a degree-weighted cost sensitivity analysis.

Experimental Setup

  • Controlled configurations isolate opinion-placement and topology effects, while observed-opinion datasets test whether the same mechanisms arise in real-world settings.The experiments use θ = 0.5 and target the opposite side of the threshold from the median innate opinion.Source: Experimental Setup · p. 6

Datasets and Opinion Configurations

  • The evaluation covers Karate Club, Facebook, and a two-community SBM, plus Reddit-Chitra, Twitter-Chitra, and Polblogs with observed ideological or political scores.Controlled settings vary favorable-opinion strength and placement; the observed scores serve as innate opinions in the FJ model.Source: Datasets and Opinion Configurations · p. 6

Common Settings and Comparison Methods

  • Experiments use homogeneous susceptibility λi = 0.8 or heterogeneous PageRank-based susceptibility, and compare structural and node-level policies with shared Random, Degree, PageRank, and Opinion-PR baselines.A greedy exact-marginal baseline is used only on Karate Club because recomputing equilibrium for every remaining candidate is prohibitively expensive on larger networks.Source: Common Settings and Comparison Methods · p. 6

Evaluation Protocols

  • Structural and node-level interventions are compared by their natural intervention fractions and by a degree-weighted cost sensitivity analysis.The latter treats edge additions as unit cost and scales node-manipulation costs by users’ reach; it is a stylized model, not an empirically calibrated monetary cost.Source: Evaluation Protocols · p. 7

Performance evaluation

Experiments examine when structural interventions can flip the equilibrium median, how they perform on real-world networks, and how they compare with node interventions under normalized and cost-calibrated budgets. Across settings, outcomes depend on opinion placement, network structure, and susceptibility; accounting for the cost of targeting high-reach users can make edge additions more cost-effective.

RQ1a: How effective are structural interventions in networks without explicit community structure?

  • Intervention success depends strongly on alignment between initial opinions and network topology: several methods cross the Karate Club target for central configurations, while Facebook’s 7 of 10 central bimodal configurations meet it at zero budget.On Karate Club, both random configurations remain below the target; on Facebook, 3 of 10 configurations in both random settings meet it at zero budget.Source: RQ1a: How effective are structural… · p. 7

RQ1: When can structural interventions flip the median?

RQ1b: How does community structure affect structural interventions?

  • In SBM, community-concentrated favorable opinions start from lower equilibrium medians but generally shift more after edge additions than randomly distributed favorable opinions.At the maximum tested budget, OAES-Aware reaches the target median curve in the community bimodal configuration; neither random configuration reaches the threshold.Source: RQ1b: How does community structure… · p. 8, Figure 3 · p. 10

RQ2: How effective are structural interventions on real-world networks with empirically derived opinion distributions?

  • On observed opinions, several methods flip the median at 0.05|E| on Reddit-Chitra, while the required budget and strongest method vary by dataset.On Twitter-Chitra, Opinion-PR crosses at 0.3, Huber and OAES-Aware at 0.4, and OAES at 0.5; on Polblogs, Huber crosses at approximately 11% edge additions in finer-grid evaluations.Source: RQ2: How effective are structural… · p. 8
  • With heterogeneous susceptibility on Twitter-Chitra, centrality-aligned susceptibility yields limited shifts and no target crossing, whereas centrality-complemented susceptibility lets several methods cross with smaller budgets.The illustrative case links higher susceptibility among favorable, more central nodes to weaker influence from those sources.Source: RQ2: How effective are structural… · p. 8

RQ3b: Cost-calibrated comparison

  • At ρ = 10, edge additions are the least expensive strategy on Polblogs, Reddit-Chitra, and Twitter-Chitra; the crossover occurs earlier on Twitter-Chitra than Reddit-Chitra.At ρ = 5, edge additions are preferable in Twitter-Chitra, while node interventions remain cheaper in Reddit-Chitra; on Polblogs, only structural interventions flip the median.Source: RQ3b: Cost-calibrated comparison · p. 9, Table 3 · p. 10

RQ3a: Comparison under normalized budgets

  • Under normalized modified fractions, node interventions often produce larger median shifts, but Polblogs is an exception: only structural interventions reach the target.In Reddit-Chitra and Twitter-Chitra, the best strategies from both intervention families cross the target with relatively small or moderate budgets.Source: RQ3a: Comparison under normalized… · p. 9, Figure 4 · p. 10

Conclusions

Structural median control offers a hard edge-addition problem with continuous and heuristic methods. Its effectiveness depends on network and opinion conditions, and structural interventions can be cost-effective when high-reach users are costly to target.

Conclusions

  • Structural median control is an edge-addition problem whose computational hardness is proved, with continuous optimization methods and lighter opinion-aware heuristics proposed.Source: Conclusions · p. 10
  • Effectiveness depends jointly on topology, opinion placement, and susceptibility; added edges work best when they create favorable influence pathways toward pivotal nodes.The conclusions identify these conditions as central to structural intervention success.Source: Conclusions · p. 10
  • Community structure and heterogeneous susceptibility can substantially alter effectiveness, while opinion-aware methods generally outperform purely topological baselines.Source: Conclusions · p. 10
  • Under homogeneous susceptibility, node-level interventions often appear stronger under normalized budgets, but structural interventions become competitive and frequently more cost-effective when targeting high-reach users is costly.Source: Conclusions · p. 10
  • Future work should model probabilistic edge adoption and optimize the expected equilibrium median.Source: Conclusions · p. 10

Related papers

Loading 2610.21933v1…