Research map / Learning theory and algorithms / Submodular and game algorithms
Opinion Maximization in Social Networks by Modifying Internal Opinions
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.
Proposes two sampling algorithms (RWB, Forest) and a deterministic asynchronous push-based algorithm (MaxInfluenceSelector / MIS) to select k nodes whose internal opinions are set to 1 to maximize overall equilibrium opinion in the FJ model.
Problem
Maximizing the overall equilibrium expressed opinion in Friedkin-Johnsen opinion dynamics on social networks by modifying the internal opinions of k nodes, which exact matrix inversion solves only at O(n^3) cost.
Approach
Interprets structural centrality via absorbing random walks and spanning converging forests for sampling, and gives a deterministic asynchronous forward/backward residual-push scheme with progressive error refinement that exactly identifies the top-k set.
Key results
- The asynchronous MIS algorithm achieves precision of exactly 1 with NDCG approaching 1 across datasets, while the matrix-inversion Exact method failed to finish on DBLP (317K nodes) within 6 hours.
- With k=64, MIS runs in roughly 0.3 to 280 seconds across datasets, versus 58 to 13,852 seconds for Forest and 100 to over 6 hours for RWB.
- MIS scales to networks with tens of millions of nodes (Twitter 41.6M, SinaWeibo 58.7M nodes) on a single thread.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MIS instead of Forest | Opinion maximization · DBLP | running time (s): 66.02 -> 0.28 | Helped |
| Use MIS instead of Forest | Opinion maximization · Google | running time (s): 162.87 -> 0.39 | Helped |
| Use MIS instead of Forest | Opinion maximization · YoutubeSnap | running time (s): 196.53 -> 1.03 | Helped |
| Use MIS instead of Forest | Opinion maximization · Pokec | running time (s): 467.81 -> 3.72 | Helped |
| Use MIS instead of Forest | Opinion maximization · Flixster | running time (s): 326.52 -> 2.59 | Helped |
| Use MIS instead of Forest | Opinion maximization · LiveJournal | running time (s): 1454.37 -> 8.61 | Helped |
| Use MIS instead of Forest | Opinion maximization · Twitter | running time (s): 12115.80 -> 279.73 | Helped |
| Use MIS instead of Forest | Opinion maximization · SinaWeibo | running time (s): 10538.27 -> 156.83 | Helped |
| Use MIS for node selection | Opinion maximization · Evaluated networks | precision | Helped |
Surprising findings
- The Exact matrix-inversion baseline could not finish even on the smallest DBLP network within the 6-hour limit.
Limitations
- Runtime grows sharply when resistance coefficients are small (alpha_min small), e.g. RWB and MIS slow under exponential distribution.
- Termination issues arise when boundary nodes contribute equally in exact optimization, per the authors.
- Sampling methods (RWB, Forest) have accuracy-efficiency tradeoffs and need many samples for precise selection.
Experimental setup
Datasets: DBLP Google YoutubeSnap Pokec Flixster LiveJournal Twitter SinaWeibo
Benchmarks: DBLP Google YoutubeSnap Pokec Flixster LiveJournal Twitter SinaWeibo
Metrics: overall opinion precision NDCG running time
Baselines: topRandom topDegree topCloseness topBetweenness topPageRank Exact matrix inversion
Builds on: DeGroot model Friedkin-Johnsen model Wilson's algorithm forward push (personalized PageRank)
Closest papers by meaning
- Sample Complexity of Linear Regression Models for Opinion Formation in Networks (AAAI 2025 · similarity 0.88)
- Opinion Optimization in Directed Social Networks (AAAI 2023 · similarity 0.88)
- Fast Computation and Optimization for Opinion-Based Quantities of Friedkin-Johnsen Model (NeurIPS 2025 · similarity 0.86)
- Optimizing Social Network Interventions via Hypergradient-Based Recommender System Design (ICML 2025 · similarity 0.86)
- Expressive and Flexible Simulation of Information Spread Strategies in Social Networks Using Planning (AAAI 2024 · similarity 0.84)
- Eliminating Majority Illusion Is Easy (AAAI 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.