What Makes Majority Illusion Easy to Detect?
For researchers studying opinion dynamics and social network analysis, this work clarifies when majority illusion detection is computationally feasible, offering guidance for algorithm design.
The paper studies the computational complexity of detecting whether a social network can exhibit majority illusion, where a minority opinion appears dominant to a fraction of agents. It provides a detailed map of how network structural properties affect tractability, identifying conditions under which the problem is easy or hard.
Majority illusion is an undesirable phenomenon in social networks in which agents incorrectly perceive a minority opinion as dominant. This can severely distort collective behavior and decision-making. We study the fundamental question of detecting whether a social network allows for a majority illusion. Formally, in the $q$-Majority Illusion problem, we ask whether there exists a binary labeling of agents in which at least a $q$-fraction of agents have the majority of neighbors with the minority label. We investigate how various structural properties of the underlying social network influence the tractability of this question, and provide a detailed map of its computational complexity.