2022/05/04 by Umberto Grandi, Grzegorz Lisowski, Grandi, Umberto +5 · 1 citation
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #Multiagent Systems (cs.MA) #Opinion Dynamics and Social Influence #cs.MA
paper · pdf · doi:10.48550/arxiv.2205.02056
arxiv created 2022/05/04 · openalex publication_date 2022/05/04 · arxiv updated 2022/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Majority illusion occurs in a social network when the majority of the network nodes belong to a certain type but each node's neighbours mostly belong to a different type, therefore creating the wrong perception, i.e., the illusion, that the majority type is different from the actual one. From a system engineering point of view, we want to devise algorithms to detect and, crucially, correct this undesirable phenomenon. In this paper we initiate the computational study of majority illusion in social networks, providing complexity results for its occurrence and avoidance. Namely, we show that identifying whether a network can be labelled such that majority illusion is present, as well as the problem of removing an illusion by adding or deleting edges of the network, are NP-complete problems.