Research map / Learning theory and algorithms / Submodular and game algorithms
Eliminating Majority Illusion Is Easy
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.
Shows that eliminating majority illusion by adding and/or removing the fewest edges is solvable in polynomial time via TDI linear programs, and that the generalized p-illusion problems are NP-hard for most p.
Problem
Majority illusion in social networks: where every node has a red-majority neighbourhood despite the global blue majority; the task is to alter the fewest edges (add and/or remove) so no node is under illusion, and to generalize this to p-fraction illusion.
Approach
Formulates edge addition/removal elimination as integer programs whose LP relaxations (with added subset-based cut constraints from b-matching theory) are totally dual integral, so polynomial-time LP solving with a separation oracle yields optimal edits; reduces the combined problem to two independent b-matching problems. Also proves NP-hardness of p-illusion variants via XSAT reductions for most
Key results
- Polynomial-time algorithms (via TDI linear programs solvable with a separation oracle in O(n^4) per separation) eliminate majority illusion completely for MIAE, MIRE and MIE.
- p-IA, p-IR and p-I are NP-hard for rational p in [0,1] except p in {0, 1/3, 1/2, 2/3, 1}.
- The LP relaxation of the naive first integer program is not integral (example gives optimum 3/2 vs integer 2), motivating the subset constraints.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use LP-1b with its added b-matching constraints | MIAE · MIAE | computational complexity: polynomial time | Helped |
| use the integral LP-2 formulation | MIRE · MIRE | computational complexity: polynomial time | Helped |
| reduce edge editing to MIAE and MIRE, or use LP-3 | MIE · MIE | computational complexity: polynomial time | Helped |
| use the b-matching separation oracle | LP-1b · MIAE separation | separation-oracle time: O(n^4) | Helped |
| use the symmetric b-matching separation oracle | LP-2 · MIRE separation | separation-oracle time: O(n^4) | Helped |
| use two independent b-matching formulations | LP-3 · MIE separation | separation-oracle time: O(n^4) | Helped |
| set the neighborhood blue-fraction threshold to p in (0, 1/2), excluding 1/3 | p-IA and p-I · p-IA, p-I | computational complexity: NP-hard | Hurt |
| set the neighborhood blue-fraction threshold to p in (1/2, 1), excluding 2/3 | p-IR and p-I · p-IR, p-I | computational complexity: NP-hard | Hurt |
| set the neighborhood blue-fraction threshold to p in (1/2, 1), excluding 2/3 | p-IA · p-IA | computational complexity: NP-hard | Hurt |
| set the neighborhood blue-fraction threshold to p in (0, 1/2), excluding 1/3 | p-IR · p-IR | computational complexity: NP-hard | Hurt |
Surprising findings
- Complete elimination of majority illusion is polynomial-time solvable even though the partial (q-fraction) elimination problem studied by Grandi et al. is NP-complete.
Limitations
- p = 1/3 and p = 2/3 remain open (neither polynomial algorithm nor hardness shown).
- Results are purely theoretical with no empirical evaluation on real networks.
Experimental setup
Baselines: Grandi et al. q-partial illusion elimination
Builds on: majority illusion (Grandi et al.) b-matching polytope TDI results XSAT for l-CNF+ hardness
Closest papers by meaning
- Identifying and Eliminating Majority Illusion in Social Networks (AAAI 2023 · similarity 0.94)
- Opinion Maximization in Social Networks by Modifying Internal Opinions (NeurIPS 2025 · similarity 0.84)
- The Surprising Effectiveness of SP Voting with Partial Preferences (NeurIPS 2024 · similarity 0.83)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.83)
- Individual Fairness in Graph Decomposition (ICML 2024 · similarity 0.83)
- Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.82)
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.