Source-linked AI summary
Spread of Misinformation in Social Networks
Daron Acemoglu, Asuman Ozdaglar, Ali ParandehGheibi
TL;DR
The paper asks when social information exchange aggregates dispersed information and when forceful agents instead spread misinformation. It models pairwise belief updating on networks, showing that beliefs converge to a stochastic consensus whose deviation from efficient aggregation depends on network mixing, forceful-agent placement, and information bottlenecks. The paper derives general bounds, special-case exact characterizations, and graph-clustering algorithms for analyzing these effects.
Problem
The central question is which conditions make networked information exchange produce accurate aggregation rather than systematic bias and misinformation.
Method
The paper uses a non-Bayesian social-network model with pairwise averaging by regular agents and forceful agents who influence others while updating only intermittently.
Results
Beliefs converge to a stochastic consensus, and the paper characterizes its deviation from efficient aggregation through network-mixing bounds, local structural analysis, special-case exact results, and bottleneck algorithms.
Takeaways & Limitations
Fast-mixing networks constrain misinformation, whereas forceful-agent locations and information bottlenecks can generate larger excess influence and require local analysis.
Takeaways & Limitations
The framework assumes that even forceful agents update their beliefs at least occasionally; without this assumption, societies with several forceful agents may lack a stationary belief distribution.
Abstract
from arXiv · showhide
We provide a model to investigate the tension between information aggregation and spread of misinformation in large societies (conceptualized as networks of agents communicating with each other). Each individual holds a belief represented by a scalar. Individuals meet pairwise and exchange information, which is modeled as both individuals adopting the average of their pre-meeting beliefs. When all individuals engage in this type of information exchange, the society will be able to effectively aggregate the initial information held by all individuals. There is also the possibility of misinformation, however, because some of the individuals are "forceful," meaning that they influence the beliefs of (some) of the other individuals they meet, but do not change their own opinion. The paper characterizes how the presence of forceful agents interferes with information aggregation. Under the assumption that even forceful agents obtain some information (however infrequent) from some others (and additional weak regularity conditions), we first show that beliefs in this class of societies converge to a consensus among all individuals. This consensus value is a random variable, however, and we characterize its behavior. Our main results quantify the extent of misinformation in the society by either providing bounds or exact results (in some special cases) on how far the consensus value can be from the benchmark without forceful agents (where there is efficient information aggregation). The worst outcomes obtain when there are several forceful agents and forceful agents themselves update their beliefs only on the basis of information they obtain from individuals most likely to have received their own information previously.
1 Introduction
The paper develops a non-Bayesian social-network model to study when information exchange aggregates dispersed information versus spreading misinformation through forceful agents. It shows that beliefs converge to a stochastic consensus and characterizes how network structure, forceful-agent locations, and information bottlenecks affect the consensus and excess influence.
- 1 Introduction: The model represents agents exchanging scalar beliefs about a dispersed state, with regular agents averaging beliefs and forceful agents influencing others without necessarily updating their own opinions.The framework is designed to capture both purposeful influence and individuals who are unusually influential with subsets of the population.
- 1 Introduction: Under weak regularity conditions, all agents’ beliefs converge to a common stochastic value despite the presence of forceful agents.The consensus is represented as π′x(0), where π is a random vector and x(0) contains initial beliefs.
- 1 Introduction: The paper measures misinformation by the gap between the expected consensus and the efficient aggregation benchmark, with each agent’s deviation from equal weight representing excess influence.The measure is ¯π′x(0) − θ = Σ_i(¯π_i − 1/n)x_i(0).
- 1 Introduction: The analysis excludes agents who know the underlying state and intentionally promote a systematic bias, and assumes forceful agents update at least occasionally.Without updating by several forceful agents, beliefs may fail to settle into a stationary distribution and require a different mathematical approach.
- 1 Introduction: Matrix perturbation results provide general bounds linking misinformation to the social network’s spectral gap and Markov-chain mixing properties.Fast-mixing, highly connected networks limit misinformation; for expander graphs, misinformation disappears in large societies with finitely many forceful agents and no global-impact forceful agent.
- 1 Introduction: Local network structure also matters: mean first passage times and forceful-agent neighborhoods can sharpen bounds beyond global mixing measures.The location of forceful links inside a dense cluster or disconnected pockets can substantially change limiting behavior.
- 1 Introduction: For forceful essential edges, all members of the small information-source group have equal excess influence, and relative-cut algorithms quantify bottlenecks for tighter bounds.The paper presents exact characterizations for some special networks and new graph-clustering tools for information bottlenecks.
2 Belief Evolution
The model represents belief evolution on a strongly connected social network where regular agents average beliefs, while forceful agents influence others without changing their own opinions. Poisson meetings and stochastic interaction rules determine how network structure and influence patterns jointly shape updates.
- Agent types and interactions: Regular agents exchange information with neighbors, whereas forceful agents disproportionately influence others and may leave their own beliefs unchanged.When agent j influences agent i, i retains weight ϵ on its prior belief and adopts weight 1−ϵ on j’s belief; j does not update.
- Meeting process: Meetings occur asynchronously in continuous time, with each agent meeting others according to a rate-one Poisson process and prescribed probabilities.Across the society, meeting instances form a rate-n Poisson process.
- Interaction rules: The model allows pairwise consensus, one-sided influence, or disagreement, with conditional probabilities βij, αij, and γij governing these outcomes.The influence update is xi(k + 1) = ϵxi(k) + (1 −ϵ)xj(k), while xj(k + 1) = xj(k).
- Network assumptions: The social network is modeled by a stochastic meeting matrix whose directed graph is strongly connected.Strong connectivity requires a directed path between every pair of agents.
- Network assumptions: Every network link must permit averaging or influence with positive probability, ensuring that even forceful agents eventually receive information from others.This “no man is an island” condition is assumed because without it multiple forceful agents may fail to settle into a stationary distribution.
- Matrix representation: The random belief update matrices are stochastic and independently identically distributed, and their mean interaction matrix combines network connectivity with influence structure.The mean matrix is decomposed into a doubly stochastic component and a remainder representing influence, enabling matrix perturbation analysis.
3 Convergence
Despite forceful agents, the model’s beliefs converge with probability one to a common consensus. Unlike the no-forceful-agent benchmark, the consensus can be random and reflect unequal influence from initial beliefs.
- Consensus: All agents’ beliefs converge with probability one to a common scalar random variable, despite potentially different initial opinions and forceful agents.The limit depends on the initial beliefs and the random sequence of interaction matrices.
- Consensus: The consensus is a convex combination of initial beliefs, with random weights given by a stochastic vector π.Each component satisfies πj ≥ 0, and the consensus can be written as π′x(0).
- Consensus distribution: Meeting order affects the consensus value when forceful agents are present, making the consensus a random variable rather than a fixed average.The paper contrasts this with averaging models in which the consensus value does not depend on the order of meetings.
- Consensus distribution: The expected consensus weights are the components of the stationary consensus distribution associated with the mean interaction matrix.The limiting mean interaction matrices have identical rows equal to the consensus distribution ¯π.
- Benchmark: Without forceful agents, beliefs converge to the average of initial beliefs with probability one, so information is aggregated effectively and each agent receives weight 1/n.In this benchmark, interaction matrices are doubly stochastic and the limiting consensus is deterministic.
4 Global Limits on Misinformation
The paper derives global bounds on misinformation by treating forceful-agent effects as perturbations of the social-network Markov chain. These bounds connect deviations from uniform influence, and therefore expected-belief error, to network mixing properties and forceful-agent influence.
- Perturbation approach: The perturbation analysis uses stationary-distribution and fundamental-matrix results for regular Markov chains.The fundamental matrix provides the basis for the exact stationary-distribution perturbation result used in the bounds.
- Global bounds: Global bounds quantify deviations between the consensus distribution and the uniform distribution, thereby bounding expected-belief deviation from the true state θ.The analysis uses perturbation theory for finite Markov chains and applies the resulting distribution bounds to consensus beliefs.
- Global bounds: Theorem 5 bounds the l∞-norm difference between the consensus distribution and the uniform distribution using global network properties.The bound is linked to communication paths, transition probabilities, and the mixing properties of the underlying graph.
- Perturbation approach: The framework represents the mean interaction matrix as a perturbation of a doubly stochastic social-network matrix by an influence matrix.The social-network matrix has the uniform stationary distribution, while forceful-agent influence changes the stationary distribution.
- Global bounds: Theorem 6 characterizes the l2-norm difference between the consensus distribution and uniform influence, also bounding deviation between expected beliefs and θ.Its network-level characterization uses the average influence and the spectral gap of the social network.
- Asymptotic implication: In fast-mixing graphs, a constant number of locally forceful agents has vanishing influence as n grows, so consensus beliefs approach the average initial belief.The result applies when the number and impact of forceful agents do not grow with n.
5 Connectivity of Forceful Agents and Misinformation
The paper links misinformation to forceful agents’ locations and network bottlenecks, deriving exact influence characterizations and progressively tighter graph-based bounds. Essential edges can equalize excess influence within clusters, while local relative-cut methods exploit structure that global connectivity measures miss.
- Mean first passage times: Excess influence is exactly characterized through mean first passage times from each agent to forceful and influenced agents.The characterization makes an agent’s influence depend on its relative network distances to those agents.
- Essential forceful edges: A forceful link over an essential edge gives all agents in the forceful agent’s cluster equal excess influence.This holds even when the cluster lacks symmetry.
- Information bottlenecks: A minimum normalized cut captures information bottlenecks, but bounds based on maximum network-wide commute times can leave local information unused.The paper explicitly identifies this as a limitation of the tighter normalized-cut bound.
- Relative cuts: Relative cuts provide tighter bounds by focusing on commute times between forceful and influenced agents rather than all pairs of states.For the barbell graph, a balanced cut within the forceful agent’s cluster has relative cut value O(n), versus O(1) for the unbalanced minimum relative cut.
6 Conclusions
The paper models misinformation as a consequence of forceful agents disrupting otherwise effective information aggregation. It establishes consensus and characterizes how network structure, forceful-agent placement, and clustering affect excess influence.
- Main conclusions: Forceful agents can shift consensus away from the efficient information-aggregation benchmark, creating measurable excess influence.The consensus discrepancy is quantified through the expected influence weights assigned to agents.
- Network structure: Fast-mixing social networks and networks with large second eigenvalues provide tight bounds on misinformation.In expander graphs, misinformation becomes arbitrarily small as society size grows when forceful agents and their impact remain finite.
- Network structure: Forceful-agent location produces different limiting behavior, including tightly characterized effects when forceful agents connect otherwise disconnected clusters.The analysis extends this perspective to broader societies through information bottlenecks.
- Computational contribution: The paper introduces efficient graph-clustering algorithms for computing tighter bounds on excess influence.
- Scope and future work: The framework is a first attempt that relies on simplifying assumptions and leaves Bayesian learning, payoff updating, and robust-network design for future work.The authors identify these extensions as important areas of further investigation.
- Scope and future work: Consensus eventually emerges despite forceful agents, but the consensus is stochastic and convergence may be slow.Removing the assumption that forceful agents receive some information generally eliminates consensus and requires a different mathematical approach.
Appendix A Preliminary Lemmas, Sections 3 and 4
The appendix develops preliminary matrix lemmas for stochastic linear updates. These lemmas establish contraction of disagreement under uniform positivity conditions and support later convergence arguments.
- Primitivity lemma: A nonnegative matrix with positive diagonal entries and a connected positive-entry graph is primitive.The associated power has strictly positive entries with a uniform lower bound determined by matrix entries and graph distances.
- Transition products: Transition products ˜Φ(k,s) link time-varying linear updates across multiple periods.The appendix uses these products to relate z(k+1) to earlier states z(s).
- Contraction lemma: Under suitable product-entry assumptions, disagreement among components of z(k) decreases with k and admits an explicit bound.
- Contraction lemma: A sequence generated by stochastic matrices contracts its maximum–minimum disagreement when every B-step product has uniformly positive entries.The contraction factor is M(s+B) −m(s+B) ≤ (1−nθ)(M(s)−m(s)).
Appendix B Properties of the Mean Interaction and Transition Matrices, Sections 3 and 4
The appendix establishes structural and probabilistic properties of the mean interaction matrix and random transition products. Connectivity, positive self-weights, and repeated interaction conditions yield uniform positivity and convergence-relevant bounds.
- Matrix definitions: Transition matrices are products of the time-indexed interaction matrices W(k), while ˜W equals their common expectation.
- Mean interaction matrix: The mean interaction matrix ˜W has positive diagonal entries and positive entries on every social-network edge.These properties follow from the interaction assumptions and network connectivity.
- Probabilistic bounds: Independence and identical distribution of W(k) imply E[Φ(s+d−1,s)] = ˜W^d.The appendix then applies Markov’s inequality to obtain probabilistic bounds on transition entries.
- Transition matrices: The transition products retain positive diagonal weights across time, with [Φ(k,s)]ii ≥ ǫ^(k−s+1).
- Transition matrices: Repeated block-level positivity and positive diagonal weights provide lower bounds on multi-step transition probabilities.The proof combines block assumptions with diagonal persistence and matrix-product decompositions.
Appendix C Properties of the Social Network Matrix, Section 4
The appendix analyzes the social-network matrix T and shows that its connectivity and self-weight properties make it primitive and regular. In the symmetric case, repeated updates preserve averages while converging toward consensus.
- Convergence: The matrix T^k converges to a stochastic matrix with identical rows as k approaches infinity.
- Matrix structure: Positive diagonal and edge entries allow the social-network matrix T to satisfy the conditions for primitivity.The proof identifies T with the matrix conditions established in the preliminary lemmas.
- Average preservation: Because T is stochastic and symmetric, it is doubly stochastic and preserves the average of z(k) over time.
- Convergence: For any initial vector, the regular Markov-chain dynamics converge to a common value represented by π′z(0).
Appendix D Characterization of the Mean Commute Time, Section 5
This section characterizes mean commute times in weighted undirected graphs using dual variational principles and an electrical-network interpretation. It also establishes a monotonicity law that supports simpler bounds when edge resistances increase.
- Characterization: Mean commute time between two nodes is characterized using the Dirichlet principle and its dual, Thompson’s principle.The two forms are dual descriptions of the same characterization.
- Characterization: The commute-time characterization uses the total edge weight together with mean first-passage times and unit flows between distinct nodes.The notation defines w as the total edge weight and mab as the mean first-passage time from a to b.
- Electrical interpretation: The Dirichlet and Thompson formulations describe minimum energy dissipation in an equivalent electrical network.Node functions represent electrical potentials, while unit flows represent currents on edges with resistance 1/wij.
- Electrical interpretation: Mean commute time between two nodes can be interpreted as their effective resistance in the corresponding resistive network.This interpretation connects random-walk quantities to electrical-network methods.
- Monotonicity: Increasing resistances increases effective resistance between any two nodes, yielding a monotonicity law for mean commute times.The law compares graphs whose edge weights satisfy ˜wij ≤ wij and can provide simple commute-time bounds.