Majority Illusions in Large Random Networks
Listen
Radio episode about this paper
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 >
Maaike Venema-Los, Zoe Christoff, Serte Donderwinkel, Davide Grossi
University of Groningen · University of Amsterdam
cs.SI
Submitted: 2026-07-24
Updated: 2026-11-13
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 92/100
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…
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
Summary
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. 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. 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. in Tγ'd,π Poisson(c)) = P(o sees red maj. in Tγ'p Poisson(c)) for p < 1/2 This is derived from Lemma 4, which shows that P(X ≤ Y) < 1/2 when c < x0 The entire argument concludes that the probability of a Mm illusion converges to 0 for p < 0.5 The paper suggests that a more natural coloring choice in a social network than the ones in Section 4 would be one based on homophily
Conclusion
We investigated the fragility of majority illusions from two main perspectives In the first part, it was seen 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 In the second part, local convergence results show that on Erdos–R˝ enyi graphs where the number of nodes goes to infinity, the probability that the graph is in Mm illusion vanishes The paper concludes by pointing to a few directions of on-going and future research Such research could involve defining a coloring that lets the graph exhibit homophily, leading to convergence to a tree with Poisson offspring colored according to the same measure The paper also 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 Such conditions require in essence a degree distribution whose variance is large relative to its mean, together with a coloring rule under which high-degree vertices are more likely to be blue
References
The references listed are:
-
Adell, J., Jodra, P.: The median of the poisson distribution. p. 6 Metrika 61, 337–346 (2005)
-
Auletta, V., Caragiannis, I., Ferraioli, D., Galdi, C., Persiano, G.: Minority becomes majority in social networks. p. 3 In: Web and Internet Economics: 11th International Conference, WINE 2015, Proceedings. p. 74–88. Springer-Verlag, Berlin, Heidelberg (2015)
-
Behrens, F., Hudcova, B., Zdeborova a, L.: Dynamical phase transitions in graph cellular automata. p. 8 Phys. Rev. E 109, 044312 (2024)
-
Benjamini, I. p. 4, Schramm, O. p. 4: Recurrence of distributional limits of finite planar graphs. p. 4 Electronic Journal of Probability 6, 1–13 (2001)
-
Broersma, N.: Extending the Graph Theory of Majority Illusions. p. 1 Master’s thesis, University of Groningen (2025)
-
Dippel, J., la Tour, M.D., Niu, A., Roy, S., Vetta, A.: Eliminating majority illusion is easy. p. 0 In: Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence. AAAI Press (2025)
-
Fioravantes, F., Lahiri, A., Lauerbach, A., Sabater, L., Sieper, M.D., Wolf, S.: Eliminating majority illusion. p. 0 In: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems. p. 0 p. 749–757. IFAAMAS, Richland, SC (2025)
-
Frischknecht, S., Keller, B., Wattenhofer, R.: Convergence in (social) influence networks. p. 1 In: Afek, Y. (ed.) Distributed Computing. p. 6 pp. 433–446. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)
-
Goles, E., Olivos, J.: Periodic behaviour of generalized threshold functions. p. 5 Discrete Mathematics 30(2), 187–189 (1980)
-
Grandi, U., Kanesh, L., Lisowski, G., Ramanujan, M.S., Turrini, P.: A Complexity-Theoretic Analysis of Majority Illusion in Social Networks. p. 0 Journal of Artificial Intelligence Research 83 (2025)
-
Hazra, R.S., den Hollander, F., Parvaneh, A.: The friendship paradox for sparse random graphs. p. 5 Probability Theory and Related Fields (2025)
-
Hofstad, R. p. 3v.d.: Random Graphs and Complex Networks. p. 0 Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press (2016)
-
Huang, C.: Correlations of online social network size with well-being and distress: A metaanalysis. p. 0 Cyberpsychology: Journal of Psychosocial Research on Cyberspace 15 (2021)
-
Kang, W.: Understanding the associations between the number of close friends and life satisfaction: Considering age differences. p. 4 Frontiers in psychology 14 (2023)
-
Kernell, G., Lamberson, P.: Social networks and voter turnout. p. 1 Royal Society open science 10 (2023)
-
Lerman, K., Yan, X., Wu, X.Z.: The “majority illusion” in social networks. p. 1 PLOS ONE 1(i) 2, 1–13 (2016)
-
McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a feather: Homophily in social networks. p. 1 Annual Review of Sociology 27(1), 415–444 (2001)
-
Ramanan, K.: CRM-PIMS summer school 2021: background material for mini course on asymptotics of interacting stochastic processes on sparse graphs (2021), accessed: 29-10- 2025
-
Venema-Los, M. p. 1, Christoff, Z. p. 0, Grossi, D. p. 0: On the graph theory of majority illusions: theoretical results and computational experiments. p. 1 Autonomous Agents and Multi-Agent Systems 39 (2025)
A 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 relies on the fact that P(X ≤ Y) < 1/2 when c < x0 This inequality is used to show that the probability of a Mm illusion converges to 0 for p < 0. p. 8
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Adaptive Opinion Dynamics Modeling: AI systems can model social influence dynamics using majority updates to determine if a majority illusion persists under evolving opinions, specifically showing that
majority illusions disappear under majority updates
in asynchronous cases. -
Large Network Scalability Prediction: For sequences of large random graphs, the fragility of majority illusions can be predicted by showing
the likelihood of majority illusions goes to zero
as network size increases, enabling reliable performance assessment for massive social systems. -
Convergence Analysis for Opinion Dynamics: AI models can analyze the long-term behavior of opinion dynamics under synchronous updates, determining whether sequences will
stabilize or reach a cycle of length 2 at a time t in O(V 2),
which helps in predicting stable versus oscillating social states. -
Local Convergence for Structural Inference: AI systems can use local convergence properties to infer the structure of large random graphs, specifically showing that
the neighborhood around a random point in the nth graph Gn looks more and more like the neighborhood around the root o in the limit graph G.
-
Robustness Testing Against Network Growth: By utilizing results on Erdos-Renyi graphs converging to Poisson trees, AI systems can determine that
on large Erdos-Renyi graphs growing in size, the probability of Majority-majority illusions converges to zero,
providing a mathematical guarantee against persistent illusions in large networks. -
Degree-Dependent Coloring Strategy: AI systems can implement coloring schemes based on local properties such as degree to predict illusion persistence, leveraging results that
the probability of G gamma d, pi n being in Mm illusion goes to 0
under certain degree-based colorings.
Related papers
- When Platforms Pay Users to Correct Misinformation: Revenue Incentives and Governance Capacity in Weibo Annotations
- Linking Scalar-Intensity Language to Structural Polarization with Validated Signed-Network Measures
- Detection and Characterization of Coordinated Online Behavior: A Survey
- Omega-N: Interpretable Structural Node Descriptors and Their Applicability Domain
- Spectral clustering of time-evolving networks using spatio-temporal random walks
- Low-vocality Engagement and Participation Dynamics on Bluesky