Research map / Graph learning / Graph algorithms and clustering
Majority Opinion Diffusion in Social Networks: An Adversarial Approach
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require regularity and sufficiently strong expansion | Strong attacker on a d-regular graph · d-regular graph | attacker win probability: cannot win for any number of rounds if σ≤ ε√(α (1-α)) | Helped |
| Bound maximum degree | Moderate attacker · graph, t rounds | attacker win probability: Δ≤ (Cn/log (1/μ))^{1/(2t)}; cannot win w.p. at least 1-μ | Helped |
| Bound maximum degree in the one-round setting | Moderate attacker · graph, one round | attacker win probability: Δ≤ C''n/log^2 (1/μ); cannot win w.p. at least 1-μ | Helped |
| Bound maximum degree or require at least half the nodes to have sufficiently large degree | Weak attacker · graph, any t | attacker win probability: Δ≤ Cn/((log n)^{C′}log (4/μ)) or half of the nodes ... degree at least d*_1; cannot win w.p. at least 1-μ | Helped |
| Select seeds independently with probability α | Opinion diffusion process · connected graph | stabilization time: Ω(log_Δ log n^{1/α}) a.a.s.; 𝒪((1/αδ)log n) a.a.s. | Mixed |
| Require the seed set to have a given size | Stabilization-time decision problem · graph with fixed-size seed set | computational complexity: NP-hard | Hurt |
| Optimize the choice of black and white seeds to minimize white nodes after t rounds | Minimum Influence problem · general graph | approximation hardness: β>n^{1-ζ} for any ζ>0 unless P=NP | Hurt |
| Use a regular graph without expansion | Strong attacker · regular disconnected graph construction | attacker win probability | Hurt |
| Use an irregular expander graph | Strong attacker · irregular expander construction | attacker win probability: b1≃ 2db0 and w1≃ dw0 | Hurt |
| Allow maximum degree Δ=(C′n/log(1/μ))^{1/t} | Moderate attacker · constructed graph, t rounds | attacker win probability: Δ=(C′n/log(1/μ))^{1/t}; ... win ... w.p. larger than μ | Hurt |
Closest papers by meaning
- Sample Complexity of Linear Regression Models for Opinion Formation in Networks (AAAI 2025 · similarity 0.87)
- Eliminating Majority Illusion Is Easy (AAAI 2025 · similarity 0.86)
- Opinion Maximization in Social Networks by Modifying Internal Opinions (NeurIPS 2025 · similarity 0.85)
- Enhancing Robustness of Graph Neural Networks on Social Media with Explainable Inverse Reinforcement Learning (NeurIPS 2024 · similarity 0.85)
- Fairness in Social Influence Maximization via Optimal Transport (NeurIPS 2024 · similarity 0.85)
- Enhancing Multi-Scale Diffusion Prediction via Sequential Hypergraphs and Adversarial Learning (AAAI 2024 · 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.