  Majority Illusion is a phenomenon in social networks wherein the decision by
the majority of the network is not the same as one's personal social circle's
majority, leading to an incorrect perception of the majority in a large
network. In this paper, we present polynomial-time algorithms which can
eliminate majority illusion in a network by altering as few connections as
possible. Additionally, we prove that the more general problem of ensuring all
neighbourhoods in the network are at least a $p$-fraction of the majority is
NP-hard for most values of $p$.
