A Complexity-Theoretic Analysis of Majority Illusion in Social Networks
Authors: Umberto Grandi, Lawqueen Kanesh, Grzegorz Lisowski, M.S. Ramanujan, Paolo Turrini
JAIR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this we provide a computational study of majority illusion in social networks, paying particular attention to the problem of its verification, that is, whether majority illusion can occur on social networks, and elimination, that is, how can we eliminate majority illusion by social network rewiring. While we show that the problems we consider are generally NP-complete, we also provide a parameterised complexity analysis, showing FPT-algorithms for the detection problem and W[1]-hardness for the elimination problem, using natural graph-theoretic parameters. |
| Researcher Affiliation | Academia | UMBERTO GRANDI, Université Toulouse Capitole, France LAWQUEEN KANESH, Indian Institute of Technology Indore, India GRZEGORZ LISOWSKI, AGH University, Poland M.S. RAMANUJAN, University of Warwick, United Kingdom PAOLO TURRINI, University of Warwick, United Kingdom |
| Pseudocode | No | The paper describes algorithms using dynamic programming over tree decompositions and ILP-Feasibility but does not present them in a structured pseudocode or algorithm block format. For example, it describes the dynamic programming approach in Theorem 3's proof but not as pseudocode: 'We now design a dynamic programming algorithm over this nice tree decomposition (𝑇, 𝛽), of width at most 2𝑘+ 1.' |
| Open Source Code | No | The paper does not contain any explicit statements about making code available, nor does it provide links to any code repositories in the main text, acknowledgments, or references. |
| Open Datasets | No | The paper presents a theoretical analysis of majority illusion in social networks, focusing on computational complexity. It does not conduct experiments on specific empirical datasets and therefore does not provide access information for any open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation using empirical datasets. Consequently, there is no mention of dataset splits such as training, test, or validation sets. |
| Hardware Specification | No | This paper is theoretical, focusing on computational complexity analysis, algorithms, and proofs. It does not describe any experiments that would require specific hardware, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on computational complexity and algorithm design. It mentions ILP-Feasibility as a subroutine but does not specify any software or library versions used for implementation or experimentation. No software dependencies are listed. |
| Experiment Setup | No | The paper is a theoretical work on the computational complexity of majority illusion in social networks, providing proofs and algorithm designs. It does not describe any empirical experiments, and therefore no experimental setup details, hyperparameters, or training configurations are provided. |