Research map / Learning theory and algorithms / Combinatorial and search optimization
Fast Computation and Optimization for Opinion-Based Quantities of Friedkin-Johnsen Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces partial rooted forest sampling via loop-erased absorbing random walks to estimate FJ opinion-based quantities and speeds up the OpMin and PDMin optimization problems, reporting sublinear-in-n cost on networks up to 41M nodes.
Problem
Computing and optimizing opinion-based quantities (polarization, disagreement, conflict, controversy, average expressed opinion) in the Friedkin-Johnsen opinion dynamics model efficiently on large graphs.
Approach
Replaces full-graph rooted spanning forest sampling with partial rooted forests built from loop-erased absorbing random walks started only from a small random node subset, giving unbiased estimates of forest-matrix entries and enabling fast OpMin and PDMin algorithms.
Key results
- PF-QE achieves mean relative error below about 1.5% for average expressed opinion and below 4% for P, I, C, DC, and runs faster than LapSolver and LazyWalk (e.g., 32.3 s on Twitter vs 160.6 s for LazyWalk).
- PF-OpMin on LiveJournal is about 37 times faster than Fast with a slightly larger opinion decline.
- PF-PDMin on Pokec achieves more than 35x speedup over FastGreedy with a greater polarization-disagreement decline; FastGreedy fails on the three largest networks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use partial rooted forest sampling instead of LazyWalk | FJ quantity estimation · six real-world networks | runtime (s): 3.1 -> 2.2; 4.1 -> 2.4; 39.5 -> 5.3; 142.2 -> 9.9; 67.6 -> 6.9; 160.6 -> 32.3 | Helped |
| Use partial rooted forest sampling instead of LapSolver | FJ quantity estimation · five networks where both methods ran | runtime (s): 7.2 -> 2.2; 9.6 -> 2.4; 49.8 -> 5.3; 291.9 -> 9.9; 186.8 -> 6.9 | Helped |
| Use PF-OpMin instead of Fast | OpMin · Livejournal | runtime (s): 296.8 -> 8.1 | Helped |
| Use PF-OpMin instead of Fast | OpMin · Livejournal | opinion decline θ: -6.44 -> -6.56 | Mixed |
| Use PF-PDMin instead of FastGreedy | PDMin · Pokec | runtime (s): 18656 -> 494.1 | Helped |
| Use PF-PDMin instead of FastGreedy | PDMin · Pokec | P-D index decline δ: -3.17 -> -3.18 | Helped |
Surprising findings
- The paper's own reported PF-QE errors for the disagreement D are higher (up to ~25% on Orkut in the exponential setting) because D depends on DC and C, amplifying errors.
Limitations
- Framework does not handle optimization objectives with nonlinear terms such as squared components (e.g., z_i^2 in marginal gain).
- Theoretical sample-size guarantees rely on random node sampling and Hoeffding bounds; the empirical r ratio is graph-dependent.
- Experiments use a single fixed setting (l=1000, p=10000) and a 2.5 GHz CPU with 8 threads.
Experimental setup
Datasets: Delicious Youtube Pokec Orkut Livejournal Twitter
Benchmarks: Delicious Youtube Pokec Orkut Livejournal Twitter
Metrics: mean relative error running time opinion decline theta P-D index decline delta
Baselines: LapSolver LazyWalk Fast Exact FastGreedy
Builds on: Friedkin-Johnsen model Wilson's algorithm forest sampling LazyWalk FastGreedy
Closest papers by meaning
- Opinion Optimization in Directed Social Networks (AAAI 2023 · similarity 0.88)
- Normalized Friedkin–Johnsen Opinion Dynamics (NeurIPS 2026 · similarity 0.87)
- Opinion Maximization in Social Networks by Modifying Internal Opinions (NeurIPS 2025 · similarity 0.86)
- Online Minimization of Polarization and Disagreement via Low-Rank Matrix Bandits (ICLR 2026 · similarity 0.86)
- Sample Complexity of Linear Regression Models for Opinion Formation in Networks (AAAI 2025 · similarity 0.85)
- Optimizing Social Network Interventions via Hypergradient-Based Recommender System Design (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.