Abstract
Recent studies from social, biological, and engineering network systems have drawn attention to the dynamics over signed networks, where each link is associated with a positive/negative sign indicating trustful/mistrustful, activator/inhibitor, or secure/malicious interactions. We study asymptotic dynamical patterns that emerge among a set of nodes that interact in a dynamically evolving signed random network. Node interactions take place at random on a sequence of deterministic signed graphs. Each node receives positive or negative recommendations from its neighbors depending on the sign of the interaction arcs, and updates its state accordingly. Recommendations along a positive arc follow the standard consensus update. As in the work by Altafini, negative recommendations use an update where the sign of the neighbor state is flipped. Nodes may weight positive and negative recommendations differently, and random processes are introduced to model the time-varying attention that nodes pay to these recommendations. Conditions for almost sure convergence and divergence of the node states are established. We show that under this so-called state-flipping model, all links contribute to a consensus of the absolute values of the nodes, even under switching sign patterns and a dynamically changing environment. A no-survivor property is established, indicating that every node state diverges almost surely if the maximum network state diverges.
Introduction
In classical network theory, research has largely focused on cooperative systems where agents aim to reach a shared consensus. However, real-world systems—ranging from social networks with "enemies" to biological systems with inhibitory pathways—are often "signed," containing both positive and negative interactions. While cooperative dynamics are well-understood, the introduction of antagonistic links significantly complicates the mathematical analysis, particularly in environments where the network structure is random or time-varying.
This paper introduces a rigorous framework for studying "state-flipping" dynamics in these complex environments. By analyzing how nodes process negative recommendations, the authors identify conditions under which a network will stabilize or, conversely, undergo a total system-wide divergence.
The State-Flipping Model
The authors propose a discrete-time stochastic model where node interactions occur via a random sampling of an underlying signed graph. The core of the model is the update rule:
- Positive Links: When node $i$ interacts with a positive neighbor $j$, it performs a standard consensus update, moving its state closer to $s_j$.
- Negative Links: When the link is negative, node $i$ treats neighbor $j$ as if its state were $-s_j$. This "state-flipping" causes node $i$ to move away from the perceived state of its enemy.
To account for real-world variability, the model incorporates stochastic attention. Bernoulli random variables represent the probability that a node listens to a recommendation at any given time step. Unlike previous models that relied on fixed spectral analysis, this study utilizes sample-path analysis to prove results that hold "almost surely" even as the network structure switches randomly.
Convergence and Structural Balance
A primary insight of this research is that negative links do not necessarily lead to chaos; instead, they contribute to a consensus of absolute values. Under the state-flipping model, all links—regardless of sign—help the network reach a state where the magnitudes of node values are uniform.
The specific long-term behavior is dictated by Strong Structural Balance. If a network can be partitioned into two antagonistic factions (where friends are within factions and enemies are between them), the nodes will converge to two opposite values ($y$ and $-y$). If the network lacks this balance, the system can only reach stability if all nodes converge to zero.
The "No-Survivor" Property
The paper’s most significant contribution to instability analysis is the no-survivor property. In many dynamical systems, it is possible for a subset of the network to remain stable while another part diverges. However, the authors prove that in a sufficiently connected signed network, instability is "contagious."
Theorem 3 establishes that if the maximum state in the network diverges to infinity, then every single node in the network will eventually diverge. There are no "survivors" in a system-wide collapse. The authors also define a specific threshold for this behavior: if the weight placed on negative recommendations ($\beta$) is sufficiently large, the entire network state will diverge with probability 1.
Conclusion and Future Directions
The state-flipping model provides a robust mathematical basis for understanding how antagonistic interactions shape collective behavior. While the model currently requires a "global origin" (a shared understanding of zero), it opens doors for future research into co-evolution, where link signs change based on node states, and placement optimization, which explores how strategically placed negative links can either stabilize or disrupt a network.
By establishing the no-survivor property and the consensus of absolute values, this work offers a new lens through which to view the stability of social, biological, and engineering systems in the face of hostility or inhibition.
Summary updated