Abstract
We study asymptotic dynamical patterns that emerge among a set of nodes interacting in a dynamically evolving signed random network, where positive links carry out standard consensus and negative links induce relative-state flipping. A sequence of deterministic signed graphs define potential node interactions that take place independently. Each node receives a positive recommendation consistent with the standard consensus algorithm from its positive neighbors, and a negative recommendation defined by relative-state flipping from its negative neighbors. After receiving these recommendations, each node puts a deterministic weight to each recommendation, and then encodes these weighted recommendations in its state update through stochastic attentions defined by two Bernoulli random variables. We establish a number of conditions regarding almost sure convergence and divergence of the node states. We also propose a condition for almost sure state clustering for essentially weakly balanced graphs, with the help of several martingale convergence lemmas. Some fundamental differences on the impact of the deterministic weights and stochastic attentions to the node state evolution are highlighted between the current relative-state-flipping model and the state-flipping model considered in Altafini 2013 and Shi et al.
2014.
Introduction
Classical consensus research, such as the DeGroot model, typically assumes that agents in a network are collaborative, seeking to move their opinions closer to their neighbors. However, real-world social, biological, and robotic networks often contain antagonistic or competitive relationships. While previous work by Altafini (2013) introduced "state-flipping" for negative links, that model required agents to share a common "origin" or zero-point in their state space—a global reference point that is often unrealistic in social contexts.
This paper introduces the Relative-State-Flipping (RSF) model to address this limitation. In the RSF model, disagreement is purely relative: a negative link pushes two agents further apart based on their current difference, without needing a global coordinate system. The study investigates whether such a system will settle into stable patterns or diverge indefinitely.
Methodology
The researchers utilize a combination of graph theory and stochastic stability analysis to define a discrete-time dynamical system.
- The Model: Each node updates its state based on "recommendations." Positive neighbors provide a standard consensus move (moving closer), while negative neighbors provide a relative-state-flipping move (moving further away).
- Stochastic Attention: A key novelty is the use of Bernoulli random variables to model "attention." At any given time step, a node may only "listen" to its positive or negative neighbors with a certain probability.
- Mathematical Proofs: The paper relies on Martingale convergence lemmas to establish "almost sure" (a.s.) behaviors—outcomes that occur with a probability of 1.
Key Results
The analysis reveals several distinct emergent behaviors based on the network's structural and stochastic properties:
- Convergence Conditions: If the "attention" paid to negative neighbors decays over time (specifically, if the sum of the probabilities is finite), the network will eventually reach a consensus despite initial antagonism.
- Deviation Consensus: The authors identify a state where the distance between agents' opinions shrinks to zero, even if their actual opinion values drift toward infinity. They move together, but they move "off the map."
- Divergence and the "No-Survivor" Property: If negative interactions persist and the network structure is sufficiently antagonistic, the gap between opinions will grow to infinity almost surely. Under certain connectivity conditions, the system is guaranteed to diverge from almost all initial starting points.
- Opinion Silos (Clustering): In networks that are "essentially weakly balanced"—meaning they can be partitioned into groups with mostly positive links inside and negative links between—the model proves that agents will naturally form clusters. Everyone within a "silo" reaches the same opinion, but different silos may diverge.
Discussion and Future Work
The RSF model provides a more robust framework for understanding disagreement by focusing on relative differences rather than absolute states. This makes it highly applicable to systems where agents lack a centralized reference point.
Future research may explore time-varying weights, where the strength of friendship or enmity changes based on opinion proximity, or non-linear dynamics to account for "stubbornness" or "extremism." Additionally, empirical validation using real-world social media datasets could help determine if these mathematical conditions accurately predict the formation of online echo chambers.
Summary updated