Majority Illusions in Large Random Networks
summary
The gist
A majority illusion in a social network occurs when the majority of neighbors of an agent has a certain opinion while the majority of agents in the network has another opinion We study the fragility…
In short
The study investigates majority illusions in social networks, which occur when a local majority opinion differs from the global network majority. The research shows that these illusions are fragile: sequences of updates never stabilize in a wrong majority state, and on large random networks like Erdős–Rényi graphs, the probability of such an illusion vanishes as the network size increases.
Key concepts
- Majority Illusion (Mm Illusion)
- This happens when most neighbors of a specific agent hold one opinion, but the overall network majority holds a different opinion. The paper proves that these illusions are not persistent; they do not last indefinitely under sequential updates or as networks grow large.
- Local Convergence in Benjamini–Schramm Space
- This is a mathematical tool used to define when the local structure of an unrooted finite graph stabilizes in probability. It helps the authors show that on large random graphs, the proportion of nodes seeing a specific majority opinion converges predictably, which leads to the conclusion that illusions are unlikely.
- Erdős–Rényi Graphs
- These are random graphs where every possible edge exists between pairs of nodes with a fixed probability. The paper uses these as a model for large networks, demonstrating that as the number of nodes grows infinitely in this structure, the likelihood of observing a majority illusion decreases to zero.
- Degree-Dependent Colorings
- This involves coloring nodes based on their degree (number of connections) rather than just random probability. The study shows that for certain degree-based colorings, conditions can be found where a uniform graph with a specific degree sequence is highly likely to exhibit a majority illusion.
Terminology used across episodes
This episode discusses
The paper
Majority Illusions in Large Random Networks · Read on arXiv
Maaike Venema-Los, Zoe Christoff, Serte Donderwinkel, Davide Grossi
University of Groningen · University of Amsterdam
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Majority Illusions in Large Random Networks".
Jane: Here's the gist of the paper. A majority illusion in a social network occurs when the majority of neighbors of an agent has a certain opinion while the majority of agents in the network has another opinion We study the fragility of majority illusions, that is, whether illusions persist as a result of changes in the underlying network This work investigates how fragile majority illusions are with respect to changes either in the opinions distribution or in the network structure Investigating Opinion Dynamics The first part of the paper considers sequences of graphs where agent colors evolve over time according to synchronous or asynchronous majority updates It is shown that both in the synchronous and the asynchronous cases, sequences of graph colorings never reach a point from which a majority of nodes keep seeing the same wrong majority Specifically, Corollary 1.
Tom: Let (Gγt) be a colored graph sequence of asynchronous majority updates There exists no t∗ such that for any t > t∗, Gγt is in Mm illusion Furthermore, Corollary 5 states that Mm illusions are fragile in the sense that graph sequences never converge to a situation where a majority of the nodes constantly sees the same wrong majority Analyzing Network Size Growth The second part studies the likelihood of majority illusions as networks grow large by using local convergence results The authors use the fact that on Erdos–R˝ enyi graphs, if the network size increases, the likelihood of majority illusions goes to zero This is demonstrated by showing that for independent identical random colorings where nodes are colored red with probability p < 0.5, the probability of Gγp n, c n being in Mm illusion goes to 0 as n → ∞ Examining Local Convergence Tools The paper introduces tools for defining local convergence in probability for unrooted finite graphs in the Benjamini–Schramm space This allows the authors to show that on large Erdos–R˝ enyi graphs, majority illusions are very unlikely by relating the proportion of nodes seeing a red majority to the probability that a node sees a red majority in the Poisson tree The convergence is established through Corollary 3, which links the proportion of nodes in Gγp n, c n that have l neighbors of which k are red to the probability that o has l children of which k red in Tγ'p Poisson(c) Degree-Dependent Colorings and Final Conclusions The study extends to colorings based on node degree, where the probability of being red depends on the degree of the node Using Corollary 6, it is shown that for Erdos–R˝ enyi graphs colored according to γd,π being in Mm illusion goes to 0 as n → ∞ The final conclusion emphasizes that social networks typically have degree distributions with heavier tails than the Erdos–R˝ enyi graph, and for degree-dependent colorings, conditions can be derived under which a uniform graph with a prescribed degree sequence exhibits Mm illusion with probability tending to 1 Omitted proofs and auxiliary material The proof of Proposition 5 shows that if a network Gγt under synchronous majority updates stabilizes on a cycle of length 2, then either Gγt is in Mm illusion for any t ≥ t∗, or Gγt is not in Mm illusion for any t ≥ t∗ The proof of Proposition 6 demonstrates that if MV t+1 = MV t!= tie, then Gγt is in Mw illusion with at least one node of color MV t under m illusion Lemma 4 proves that for two independent distributions X and Y that both take integer values, P(X ≤ Y) = P∞ k=0 (P(X ≤ k) · P(Y = k))<1 whenever c < x0 This inequality is used to show that the probability of a Mm illusion converges to 0 when c < x0 The proof of Proposition 8 shows that whenever c < x0, CDFPoisson(x0)(P) < 1/2, which implies (Lemma 3) that the probability of a Mm illusion converges to 0 Illustration of CDF’s of Poisson distributions Figure 2 provides examples of cumulative distribution functions of Poisson(x0) distributions with different values of x0 This figure illustrates the behavior discussed in the proof concerning the probability that o sees a red majority in Tγ'd,π Poisson(c) The analysis relies on Equation 3, which expresses P(o sees red majority) as X∞ d=1 (P(Poisson(c) = d) · X d j=ceilings d+1/2 P(Bin(d, CDFPoisson(x0)(P)) = j) The convergence of this probability to 1 if c ≥ x0 and to 0 if c < x0 is shown through the tower principle of conditional expectation This leads to the conclusion that given c < x0, the probability that a majority of nodes in the graph is red converges to 1 if c ≥ x0 and to 0 if c < x0 The final result states that P(o sees red maj.
Jane: in Tγ'd,π Poisson(c)) c, which implies (Lemma 3) that the probability of a Mm illusion converges to 0 The proof relies on the fact that P(o sees red maj.
Tom: in Tγ'd,π Poisson(c)) = P(o sees red maj.
Paper summary: Tom: Moving into what they actually claim about this paper, "Majority Illusions in Large Random Networks," it starts by defining what a majority illusion is in a social network, which is when the majority of neighbors of an agent has one opinion while the overall majority in the network has another >
Jane: And then they immediately set up two settings to study this: first, they look at networks where agents' opinions change over time and find that under these majority updates, these illusions disappear >
Lu: They show that in both synchronous and asynchronous cases, sequences of graph colorings never reach a point from which a majority of nodes keep seeing the same wrong majority >
Meng: That implies that you can't just set up an opinion dynamic system and expect it to get stuck in a persistent illusion state on these evolving networks >
Jane: Then they switch gears and study sequences of large random graphs where the size n increases every step, looking at how likely these illusions are to occur as the network grows >
Tom: They prove that for specific types of random graphs, like Erdos-R˝ enyi graphs, the probability of a majority illusion goes to zero as n goes to infinity >
Lu: This is demonstrated by showing that for independent identical random colorings where nodes are colored red with a probability less than five tenths, the probability of being in an illusion vanishes as n increases >
Jane: They use local convergence results on unrooted finite graphs in the Benjamini-Schramm space to make this analysis rigorous on these large graphs >
Tom: They relate the proportion of nodes seeing a red majority to the probability that a node sees a red majority in the Poisson tree structure, which is what makes it mathematically tractable >
Meng: So, for someone deploying models at scale, this means if you build your network based on some random graph model and let it grow large, you can be confident that persistent illusions will fade out >
Jane: They also look at degree-dependent colorings and find that for Erdos-R˝ enyi graphs colored according to gamma d pi, the illusion probability goes to zero as n increases >
Tom: The paper sets up a framework where they connect local neighborhood structures to global majority winners on large random graphs >
Lu: They use tools like the tower principle of conditional expectation and Lemma four to show that if c is less than xzero the probability of an illusion converges to zero >
Meng: So, what they're telling us is that for these standard large random network models, you don't have to worry about persistent illusions when the network gets big enough >
Jane: It sets up a strong baseline for understanding how opinion dynamics interact with the underlying topology of the graph as it scales up >
Conclusion: Tom: The paper, "Majority Illusions in Large Random Networks," by Venema-Los, Christoff, Donderwinkel, and Grossi, really focuses on showing that these illusions are fragile when you look at time evolution or network growth >
Jane: They establish that in the context of opinion dynamics and evolving networks, the illusions disappear under majority updates and as networks get larger >
Lu: The second part of their work shows that on Erdos-R˝ enyi graphs, the likelihood of these illusions goes to zero as the number of nodes n increases >
Meng: So for practical deployment at scale, this suggests that you don't need to worry about these persistent, misleading majority signals in large random architectures if they stick to these structural assumptions >
Jane: They conclude by pointing out that social networks typically have degree distributions with heavier tails than the Erdos-R˝ enyi graph >
Tom: And for degree-dependent colorings, they found conditions under which a uniform graph with a prescribed degree sequence exhibits an illusion probability tending to one >
Lu: These conditions require in essence a degree distribution whose variance is large relative to its mean, combined with a coloring rule where high-degree vertices are more likely to be blue >
Meng: That's interesting because it flips the intuition about what makes illusions possible on larger networks, suggesting structure matters beyond just uniform random graphs >
Jane: So the main implication for people listening is that we need to look at how network structure and coloring rules interact when designing large systems for influence or decision-making >
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game