Research map / Learning theory and algorithms / Combinatorial and search optimization
Identifying and Eliminating Majority Illusion in Social Networks
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 |
|---|---|---|---|
| Restrict verification to networks parameterized by maximum degree and tree width | q-MAJORITY ILLUSION · Networks of tree width k and maximum degree ∆ | running time: ∆O(k)nO(1) | Helped |
| Restrict verification to networks parameterized by tree width | q-MAJORITY ILLUSION · Networks of tree width k | running time: nO(k) | Helped |
| Restrict verification to networks parameterized by neighbourhood diversity | q-MAJORITY ILLUSION · Networks of neighbourhood diversity k | running time: 2O(k log k)nO(1) | Helped |
| Restrict verification to networks parameterized by vertex cover | q-MAJORITY ILLUSION · Networks with vertex cover equal to k | running time: 22O(k)nO(1) | Helped |
| Restrict verification to networks parameterized by maximum degree and cliquewidth | q-MAJORITY ILLUSION · Networks of maximum degree ∆ and cliquewidth k | running time: ∆O(∆·k)nO(1) | Helped |
| Allow arbitrary networks with q in (1/2, 1] | q-MAJORITY ILLUSION · General networks | computational complexity | Hurt |
| Restrict the network to be bipartite | q-MAJORITY ILLUSION · Bipartite networks | computational complexity | Hurt |
| Restrict the network to be planar | q-MAJORITY ILLUSION · Planar networks | computational complexity | Hurt |
| Parameterize elimination by the number of modified edges | q-ILLUSION ELIMINATION · General networks, q in (0, 1) | parameterized complexity | Hurt |
| Allow only edge additions | q-ILLUSION ELIMINATION · General networks, q in (0, 1) | parameterized complexity | Hurt |
| Allow only edge removals | q-ILLUSION ELIMINATION · General networks, q in (0, 1) | parameterized complexity | Hurt |
Closest papers by meaning
- Eliminating Majority Illusion Is Easy (AAAI 2025 · similarity 0.94)
- Temporal Triadic Closure: Finding Dense Substructures in Social Networks That Evolve over Time (AAAI 2025 · similarity 0.82)
- An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks (NeurIPS 2025 · similarity 0.81)
- Opinion Maximization in Social Networks by Modifying Internal Opinions (NeurIPS 2025 · similarity 0.81)
- Individual Fairness in Graph Decomposition (ICML 2024 · similarity 0.81)
- Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks (NeurIPS 2024 · similarity 0.81)
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.