Dynamics over Signed Networks

Guodong Shi; Claudio Altafini; John S. Baras

Source-linked AI summary

Dynamics over Signed Networks

Guodong Shi, Claudio Altafini, John S. Baras

arXiv:1706.03362v3Jun 11, 2017cs.SI

TL;DR

Signed-network dynamics raises how node states evolve when positive and negative links support different interactions across diverse systems. The paper reviews convergence results for opposing and repelling rules using generalized Perron-Frobenius theory, graph theory, and elementary algebraic recursions. It concludes that node dynamics depend crucially on network sign structure across deterministic and random interactions.

Problem
Signed networks require convergence analysis for node dynamics in which positive and negative links produce different interactions across biological, social, political, and economic systems.
Method
The paper reviews opposing and repelling signed-network dynamics through a unified approach using generalized Perron-Frobenius theory, graph theory, and elementary algebraic recursions.
Results
The reviewed results show that node dynamical properties depend crucially on network link sign structure for both deterministic and random node interactions.
Takeaways & Limitations
A systematic tool for studying node-state evolution over signed networks can be obtained from the paper’s unified algebraic-graphical framework.
Takeaways & Limitations
The relationship between network sign structure and network controllability or structural controllability remains unresolved.

Abstract

from arXiv · show

A signed network is a network with each link associated with a positive or negative sign. Models for nodes interacting over such signed networks, where two different types of interactions take place along the positive and negative links, respectively, arise from various biological, social, political, and economic systems. As modifications to the conventional DeGroot dynamics for positive links, two basic types of negative interactions along negative links, namely the opposing rule and the repelling rule, have been proposed and studied in the literature. This paper reviews a few fundamental convergence results for such dynamics over deterministic or random signed networks under a unified algebraic-graphical method. We show that a systematic tool of studying node state evolution over signed networks can be obtained utilizing generalized Perron-Frobenius theory, graph theory, and elementary algebraic recursions.

1 Introduction

Signed-network dynamics model positive and negative interactions in systems with cooperative and antagonistic relationships. The paper introduces signed-graph and Laplacian concepts, structural balance, opposing and repelling rules, and reviews convergence results using a unified approach.

Signed graphs represent systems with two interaction types, such as activatory or inhibitory and cooperative or antagonistic relationships.
1.1 Signed Graphs: Each edge has a positive or negative sign, inducing positive and negative subgraphs that determine the network’s interaction structure.
1.3 Structural Balance Theory: Structural balance characterizes signed graphs through partitions with positive within-group edges and negative between-group edges, with weak balance allowing multiple groups.
1.4 Positive/Negative Interactions: The opposing rule attracts a node toward the opposite of a negative neighbor’s state, whereas the repelling rule makes the two states repel each other.
1.5 Paper Organization: The paper reviews convergence properties for signed dynamics over deterministic or random interactions using a unified algebraic-graphical method.

2 Deterministic Networks

The section characterizes asymptotic node-state behavior in deterministic signed networks under opposing and repelling negative interactions. Its convergence results depend on structural balance, connectivity, and the relative strength of positive and negative links.

Analytical framework: The unified analysis uses generalized spectral and graph-theoretic arguments, including gauge transformations, Gershgorin bounds, Perron-Frobenius structure, and algebraic recursions.The approach incorporates graphical analysis into algebraic inequalities and extends to strongly connected, weighted, and continuous-time settings.
Opposing rule: For structurally balanced opposing-rule networks, a gauge transformation converts the dynamics into standard consensus, yielding signed agreement across the two network partitions.The transformed states converge by ordinary consensus arguments.
Repelling rule: For the repelling rule, average consensus occurs when β is below a threshold β*, whereas states diverge for β above β* under the stated connectivity and step-size conditions.The threshold reflects whether positive-link convergence can overcome repulsive negative interactions.
Repelling rule: Even an arbitrarily small repulsion can cause divergence when the network contains a single negative link and the repelling threshold is exceeded.The negative interaction acts as a destabilizing perturbation unless positive links provide sufficient convergence.
Opposing rule: Under the opposing rule, connected networks contract state magnitudes; structural balance determines whether nonzero bipartite consensus exists, while imbalance drives all states to zero.The result applies under sufficiently small interaction parameters and any initial state.
Network modifications: For small parameters in undirected networks, adding links accelerates opposing-rule convergence when structural balance is preserved, whereas adding a negative repelling link can worsen convergence behavior.The comparison concerns spectral convergence rates under the respective dynamics.

3 Random Networks

The paper models random signed-network interactions through a stationary gossip process and analyzes mean, mean-square, and almost sure convergence under opposing and repelling rules. It characterizes consensus, clustering, and divergence according to structural balance, connectivity, and interaction strength.

3.1 Random Interaction Model: Random interactions are modeled on an undirected signed graph using Poisson-initiated node selections, uniformly chosen neighbors, and sign-dependent state updates.Only the selected pair updates at each event; all other node states remain unchanged.
3.1 Random Interaction Model: The analysis targets mean, mean-square, and almost sure convergence of the resulting random state process.The model is presented as a random process on a product probability space induced by successive pair selections.
3.2 Convergence Results: Under opposing dynamics, structurally balanced networks cluster according to their partition, whereas non-balanced networks converge to zero in mean-square and almost surely.These conclusions hold under the stated parameter conditions for the opposing rule.
3.2 Convergence Results: Under repelling dynamics with connected positive graphs, sufficiently small negative interaction strength yields average consensus in mean-square and almost surely.The result applies for any 0 < α < 1 under the theorem's stated critical threshold for β.
3.2 Convergence and Divergence: Large negative interaction strengths can cause almost sure divergence for almost all initial states, and the No-Survivor Property extends divergence from maximum states to every node or relative state.The divergence results include both opposing and repelling models under their respective connectivity and parameter assumptions.
3.3 Bounded States for Repelling Dynamics: For bounded repelling dynamics, sufficiently large negative strength produces boundary clustering in structurally or weakly structurally balanced complete graphs, while connected positive graphs can force repeated visits to both boundaries.The clustered states take values at the two boundaries, with one boundary value assigned per structural-balance group in the multi-group case.

4 Conclusions

The paper surveys fundamental convergence results for signed-network dynamics using a unified algebraic-graphical approach. It identifies open directions including inverse problems, controllability, and feedback-dependent network signs.

The review covers fundamental convergence properties of signed dynamical networks with deterministic or random node interactions.
A unified approach combines generalized Perron-Frobenius theory, graph theory, and elementary algebraic recursions to study these dynamics.
The results show that network dynamical properties depend crucially on link sign structure for both deterministic and random interactions.
Future work includes reconstructing node values, identifying edge signs, and testing structural balance from finite measurements at subsets of nodes.
How sign structure relates to network controllability or structural controllability remains an open problem.
Feedback from evolving node states to edge signs would produce state-dependent interaction structures and highly nonlinear node updates.

A. Proof of Theorem 3

The proof establishes convergence by showing that the maximum absolute node state is nonincreasing and that every node reaches the same limiting magnitude. The resulting sign partition proves structural balance.

The maximum absolute state h(t) is nonincreasing and converges to a positive limit h* for nonzero limiting behavior.
A contradiction argument propagates any node’s lower limiting magnitude through the strongly connected graph, forcing g_i = h* for every node.
All node states asymptotically converge after excluding persistent opposite-sign limiting behavior.
The limiting partition has only negative links across its two subsets and only positive links within each subset, proving structural balance.

B. Proof of Theorem 4

The proof uses spectral continuity to extend convergence from the positive-link case to sufficiently small negative-interaction weights. It establishes a simple eigenvalue at one, a positive left eigenvector, and contraction of the remaining modes.

The matrix M_G always has eigenvalue one because the positive and negative Laplacians have zero row-sum structure.
The argument starts from r(0) < 1 and a positive q(0), then uses continuity of r(·) and q(·) in β.
For sufficiently small β < β*, one is a simple eigenvalue of M_G with r(β) < 1, while q(β) remains positive.
The proof invokes generalized Perron-Frobenius results and a gauge transformation to establish the required spectral properties.

C. Proof of Theorem 5

The proof analyzes random pairwise interactions under the opposing rule. Structurally balanced networks converge toward a signed-consensus behavior, whereas unbalanced connected networks converge to zero in mean square.

The proof models pairwise interactions with an i.i.d. random matrix process W_t and exploits the balance partition through a diagonal sign matrix K.
For structurally balanced networks, the expected disagreement converges to zero and the corresponding convergence also holds almost surely.
For the balanced case, a supermartingale argument and λ_max < 1 imply exponential decay of the expected disagreement quantity.
The unbalanced-case argument uses connectedness and the absence of structural balance to show that the relevant Lyapunov quantity tends to zero.
The weighted positive and opposing Laplacians encode the random interaction probabilities and determine the spectral bounds used in the proof.
When the network is not structurally balanced, x(t) converges to zero in mean square under the opposing rule.

D. Proof of Theorem 6

The proof analyzes repelling negative dynamics through the distribution of the random update matrices and algebraic quantities associated with the signed graph. It concludes that the relevant disagreement measure converges to zero almost surely.

Under the repelling rule, the distribution of the random update matrix W_t is characterized algebraically.
The argument uses eigenvalue-based quantities involving the signed graph Laplacian and the second moment E{W^2(t)}.
For 0 ≤ β < β*, the proof applies the same analysis used for V(t) and V*(t).
The proof establishes that the relevant state-variation quantity converges to zero and that V♭(t) tends to zero almost surely.

E. Proof of Theorem 7

The proof of Theorem 7 uses a lemma for α ≠ 1/2 and β ≥ 3 to control state magnitudes under positive and negative pair updates. It then invokes prior arguments and the strong law of large numbers to obtain the theorem’s conclusion.

For α ≠ 1/2 and β ≥ 3, Lemma 1 provides the central condition used in the proof.
When a positive-link pair is selected, the proof shows that the relevant maximum magnitude does not decrease under the stated case conditions.
For a negative-link pair, the proof transforms the two states as y_i(t) = x_i(t) and y_j(t) = −x_j(t) before analyzing the update.
The case analysis yields h(t + 1) ≥ h(t)/2 when β ≥ 3.
The remaining conclusion follows by the same argument as a cited prior proposition, using the strong law of large numbers.
A related result is attributed to Theorem 3 in reference and likewise relies on the strong law of large numbers.

F. Proof of Theorem 9

The proof of Theorem 9 constructs finite sequences of random pair selections that propagate a two-group signed-state pattern. Stopping-time arguments and the second Borel–Cantelli lemma then establish the theorem’s almost-sure conclusion for almost all initial beliefs when β > β⋄.

For almost all initial beliefs, the theorem’s conclusion holds when β > β⋄.
Lemma 3 constructs a sequence of pair realizations that produces x_i = −A on V1 and x_i = A on V2 after 3(n − 2) updates.
The construction begins from opposite states in two groups and recursively selects positive-link pairs within groups to propagate the pattern.
The proof uses Lemma 2, recursively defined stopping times, the strong Markov property, and the second Borel–Cantelli lemma to obtain the required events.
The two cases in Lemma 2 distinguish whether the selected nodes lie in different subgroups or the same subgroup, with both cases reduced to the same condition.
The proof concludes after establishing the finite-time construction and completing Theorem 9.

G. Proof of Theorem 10

The proof of Theorem 10 extends the finite pair-selection construction from two groups to weakly structurally balanced graphs with m ≥ 2 groups. The resulting state pattern assigns opposite signs to the first two groups and a common sign determined by the current state to the remaining groups.

For a weakly structurally balanced partition into m ≥ 2 groups, the construction yields x_i = −A on V1, x_i = A on V2, and x_i = I0A on V_m for m ≥ 3.
The required sequence of pair realizations has length Z = 3n − 2m − 2.
The construction first applies the two-group procedure to establish opposite states on V1 and V2.
For each additional group, the proof recursively selects pairs to extend the sign pattern to the remaining nodes.
The full process uses 3n − 2m − 2 node pairs, and the resulting lemma supports the theorem through the stopping-time and Borel–Cantelli argument used previously.

H. Proof of Theorem 11

The proof establishes that, under the stated signed-network conditions and parameter bound, suitable node-pair realizations can drive any node state arbitrarily close to both −A and A. Theorem 11 then follows from this lemma together with Lemma 2 and the second Borel–Cantelli result.

For α ∈(1/2, 1) and β ≥2/(2α −1), the lemma considers dynamics on a complete graph whose positive graph has κ(G+) ≥2.
Starting from xi1(t) = −A and xj1(t) = A, every node can be driven within ϵ of −A or A through finite sequences of node-pair realizations.The two alternatives hold for any i⋆∈V and ϵ∈[0, (2α −1)A/2α].
The proof uses paths in the connected positive graph to create opposite-sign states at neighboring nodes before applying positive and negative edges strategically.
For distinct positive neighbors, the construction yields xm∗(t + 5 + Z2) ≤(1 −2α)A/2 and xk∗(t + 5 + Z2) ≥(2α −1)A/2.