PaperlayerView exact revision on arXiv

Source-linked AI summary

Opinion Dynamics in Social Networks with Hostile Camps: Consensus vs. Polarization

Anton V. Proskurnikov, Alexey Matveev, Ming Cao

arXiv:1508.05034v1eess.SYmath.OC

TL;DR

Conventional consensus models assume cooperative agents, but social networks also contain antagonistic ties that can produce polarization. The paper extends Altafini’s modulus-consensus model to arbitrary time-varying signed graphs and establishes sufficient connectivity conditions, with necessary and sufficient criteria for cut-balanced graphs.

Abstract

from arXiv · show

Most of the distributed protocols for multi-agent consensus assume that the agents are mutually cooperative and "trustful," and so the couplings among the agents bring the values of their states closer. Opinion dynamics in social groups, however, require beyond these conventional models due to ubiquitous competition and distrust between some pairs of agents, which are usually characterized by repulsive couplings and may lead to clustering of the opinions. A simple yet insightful model of opinion dynamics with both attractive and repulsive couplings was proposed recently by C. Altafini, who examined first-order consensus algorithms over static signed graphs. This protocol establishes modulus consensus, where the opinions become the same in modulus but may differ in signs. In this paper, we extend the modulus consensus model to the case where the network topology is an arbitrary time-varying signed graph and prove reaching modulus consensus under mild sufficient conditions of uniform connectivity of the graph. For cut-balanced graphs, not only sufficient, but also necessary conditions for modulus consensus are given.

I. INTRODUCTION

The paper extends consensus analysis to signed networks where cooperation and antagonism coexist, focusing on time-varying interaction topologies. It develops conditions for modulus consensus beyond earlier static-graph models.

Motivation

  • Social networks include cooperative and competitive relationships, commonly modeled through attractive and repulsive couplings.Repulsion can produce clustering and polarization, motivating analysis beyond conventional cooperative consensus.Source: §I · p. 1

Prior work

Contribution

  • Earlier studies mainly considered static interaction topologies, whereas this paper treats general directed time-varying signed graphs.The broader setting accommodates relationships that can change between friendship and hostility.Source: §I · p. 2

Model and graph structure

  • The signed-graph framework uses weighted directed arcs with cooperative or antagonistic signs and excludes self-loops while imposing digon sign symmetry.Structural balance is characterized through positive oriented cycles in strongly connected digon-symmetric graphs.Source: A. Signed graphs and their properties · pp. 2–3
  • Signed Laplacians differ from unsigned Laplacians because a strongly connected structurally unbalanced graph can yield a Hurwitz matrix with no zero eigenvalue.This distinction connects structural imbalance with stabilization rather than consensus.Source: A. Signed graphs and their properties · p. 3

B. Some important types of time-varying signed graphs

The paper formalizes connectivity and consensus notions for time-varying signed graphs, then distinguishes stability, consensus, and polarization. Its results identify connectivity conditions for static, general dynamic, and cut-balanced networks.

Time-varying graph classes

  • Essential strong connectivity requires infinite accumulated absolute interaction weight along every essential interaction needed to connect the graph.Uniform strong connectivity is a stronger condition defined through strongly ε-connected integrated graphs over every time window.Source: B. Some important types of… · p. 3
  • For cut-balanced graphs, equal-direction reachability implies strong connectivity of the essential interaction graph.Cut balance includes type-symmetric and weight-balanced graphs as examples.Source: B. Some important types of… · p. 3

Opinion dynamics

  • The protocol permits cooperative or competitive influence, with the signed coupling directing opinions toward aligned or opposed neighbor values.Unlike cooperative protocols, the convex hull need not shrink; maximal modulus is the available non-increasing Lyapunov quantity.Source: §III · pp. 3–4

Consensus outcomes

  • Modulus consensus has trivial and non-trivial forms: opinions either converge to zero or share a nonzero limiting modulus.In the non-trivial case, equal signs yield consensus while differing signs yield polarization.Source: §III · p. 3

Main results

  • For static graphs, modulus consensus has necessary and sufficient criteria, including structural balance and quasi-strong connectivity for bipartite consensus.Stability occurs when structurally balanced in-isolated subgraphs are absent.Source: §III · p. 4
  • For general time-varying graphs, uniform strong connectivity suffices for modulus consensus, whereas uniform quasi-strong connectivity does not generally suffice.For cut-balanced graphs, the paper gives necessary and sufficient conditions for both bipartite modulus consensus and stabilization.Source: §III · p. 4

IV. MAIN RESULTS

The paper characterizes modulus consensus in static and time-varying signed networks, identifying connectivity and structural-balance conditions that govern consensus, polarization, stability, and failure.

A. Time-invariant protocols

  • For structurally balanced static graphs, quasi-strong connectivity is equivalent to modulus consensus and yields bipartite consensus.With nonnegative interactions, the result is ordinary consensus; otherwise, opinions polarize.Source: A. Time-invariant protocols · pp. 4–5
  • For static graphs, the protocol is stabilizing exactly when the graph is neither structurally balanced nor contains an in-isolated structurally balanced subgraph.Such subgraphs can evolve independently toward bipartite consensus, preventing stability.Source: A. Time-invariant protocols · p. 5
  • Static QSC alone does not guarantee modulus consensus when the graph is not structurally balanced, because an ISB subgraph can obstruct convergence.The paper gives a three-agent example with equilibria of the form (ξ, −ξ, ρξ).Source: A. Time-invariant protocols · p. 5

B. Protocols over dynamic signed graphs

  • Under bounded coupling gains, uniform strong connectivity is sufficient for modulus consensus in arbitrary time-varying signed graphs.The maximum absolute opinion is monotonically non-increasing, and all opinion moduli converge to the same limit.Source: B. Protocols over dynamic signed graphs · p. 5
  • For fixed hostile camps, UQSC suffices for bipartite consensus, while bipartite consensus necessarily requires edge- or eventual-type quasi-strong connectivity.The sufficient result assumes signs remain nonnegative within camps and nonpositive across camps.Source: B. Protocols over dynamic signed graphs · pp. 5–6
  • Uniform quasi-strong connectivity cannot generally replace uniform strong connectivity, even when the time-varying graph remains structurally balanced.A periodic UQSC example has x1(t) = −x2(t) = 1 while x3(t) remains in [−1/2, 1/2], so modulus consensus fails.Source: B. Protocols over dynamic signed graphs · pp. 5–6

C. Modulus consensus over cut-balanced graphs

For cut-balanced signed graphs, the paper derives necessary and sufficient conditions that distinguish bipartite consensus, polarization, and stability. These results extend earlier cooperative and type-symmetric analyses to broader time-varying signed networks.

Graph construction

  • The signed graph G± assigns +1 to essentially cooperative arcs and −1 to essentially competing arcs when these interaction sets do not overlap.Essential interactions are defined through divergent accumulated absolute weights.Source: C. Modulus consensus over cut-balanced… · p. 6

Connectivity implications

  • For cut-balanced graphs, quasi-strong connectivity implies essential strong connectivity, while essential strong connectivity alone is insufficient without essential structural balance.This contrasts with the cooperative case, where essential connectivity is sufficient for consensus.Source: C. Modulus consensus over cut-balanced… · p. 6

Necessary and sufficient conditions

  • Theorem 3 characterizes bipartite modulus consensus exactly through a well-defined, strongly connected, structurally balanced signed graph G±.Under cut-balance, this criterion is necessary and sufficient.Source: C. Modulus consensus over cut-balanced… · p. 6
  • Polarization occurs exactly when the structurally balanced graph G± contains essentially competing interactions; otherwise, consensus is established.If G± is structurally unbalanced or its positive and negative interaction sets overlap, the protocol is stabilizing.Source: C. Modulus consensus over cut-balanced… · p. 6

Relation to prior work

  • The paper extends prior cut-balanced results beyond type-symmetric graphs and develops an independent proof approach for general and cut-balanced signed networks.The cooperative case is recovered as a special case of Theorem 3.Source: C. Modulus consensus over cut-balanced… · pp. 6–7

Component-wise behavior

  • For disconnected graphs, each strongly connected component reaches a modulus-consensus type determined by its own structural balance and competing interactions.Balanced components yield bipartite consensus, ordinary consensus when no competing interactions remain, and polarization otherwise; unbalanced components are stable.Source: C. Modulus consensus over cut-balanced… · p. 6

V. APPLICATIONS: NONLINEAR PROTOCOLS

The paper applies its signed-graph results to nonlinear consensus protocols by replacing nonlinear interactions with solution-dependent gains. Under monotonicity and connectivity conditions, these protocols establish modulus consensus, although the theorem supplies only sufficient conditions.

Assumptions and transformation

  • The nonlinearities h_ij are assumed continuously differentiable, strictly increasing, and zero at zero.Their secant gains H_ij[y,z] are positive and continuous, converting nonlinear differences into gain-weighted state differences.Source: A. Additive Laplacian protocols · p. 7
  • The solution-dependent matrix A(t) preserves the relevant connectivity, cut-balance, and boundedness properties of the original interaction matrix.The construction uses H_ij evaluated along the solution trajectory.Source: A. Additive Laplacian protocols · p. 7

Theorem 5

  • Under Assumption 1, the nonlinear systems have unique, infinitely prolongable solutions and achieve modulus consensus when the transformed graph is USC with bounded gains or ESC and cut-balanced.These conditions are sufficient for both protocols (9) and (10).Source: A. Additive Laplacian protocols · p. 7

Relation to prior work

  • Unlike the earlier comparison, the nonlinearities may be heterogeneous and non-odd, while the graph may be time-varying.The assumptions differ from, which requires monotonicity with an integral constraint but not smoothness.Source: A. Additive Laplacian protocols · p. 7

Limitation

  • Theorem 5 provides only sufficient conditions because the available necessary-condition lemmas assume a common matrix across all solutions.Necessary conditions for the nonlinear case are identified as beyond the paper’s scope.Source: A. Additive Laplacian protocols · p. 7

B. Nonlinear Laplacian Flow

For a nonlinear Laplacian flow with state-dependent interaction gains, the paper establishes global solution existence and modulus consensus under uniform or essential strong connectivity with cut-balance alternatives.

Protocol assumptions

  • The nonlinear protocol uses Carathéodory interaction maps F_ij(t,x) that are continuous in x almost everywhere and measurable in t.A local boundedness condition is imposed uniformly over compact sets.Source: B. Nonlinear Laplacian Flow · p. 7

Theorem 6

  • For every initial condition, a solution exists for all t ≥ 0, and the induced matrix A(t) has bounded entries.The transformed interaction matrix is formed from the nonlinear gains along the solution.Source: B. Nonlinear Laplacian Flow · p. 7
  • The protocol establishes modulus consensus if the induced graph is USC, or if it is ESC and cut-balanced.These are sufficient connectivity conditions for the nonlinear flow.Source: B. Nonlinear Laplacian Flow · p. 7

Extensions

  • Theorem 6 extends earlier nonlinear results to time-varying gains without requiring constant signs, weight balance, or order-preserving flow.For ESC graphs, weight balance is replaced by the weaker cut-balance condition.Source: B. Nonlinear Laplacian Flow · p. 7

Verification

  • Verifying connectivity of the induced graph can be difficult because its entries depend on the concrete solution, although global strong ε-connectivity implies the needed property in special cases.This provides a route for checking the assumption in particular nonlinear systems.Source: B. Nonlinear Laplacian Flow · p. 7

A. Proofs of Lemmas 2, 4 and Theorem 1

The proofs connect signed opinion dynamics to cooperative consensus through gauge transformations and characterize stability using the signed Laplacian’s zero eigenvalue. Structural balance determines whether limiting opinions can polarize.

Gauge transformation

  • A gauge transformation based on two hostile camps converts a structurally balanced signed system into a cooperative one.The diagonal transformation assigns opposite signs to the two camps.Source: A. Proofs of Lemmas 2, 4 and Theorem 1 · p. 8
  • For a structurally balanced graph whose absolute-value graph is UQSC, the transformed cooperative protocol reaches consensus, yielding polarization in the original opinions.The two camps converge in magnitude with opposite signs.Source: A. Proofs of Lemmas 2, 4 and Theorem 1 · p. 8

Stability criterion

  • For a strongly connected signed graph, stability is equivalent to the absence of zero as an eigenvalue of its signed Laplacian.All other Laplacian eigenvalues have positive real parts by the cited Gershgorin argument.Source: A. Proofs of Lemmas 2, 4 and Theorem 1 · p. 8

Structural balance

  • A normalized zero eigenvector partitions nodes into hostile camps and cannot have nonzero edges from those camps to nodes outside the partition.This identifies the structural organization associated with a zero Laplacian eigenvalue.Source: A. Proofs of Lemmas 2, 4 and Theorem 1 · p. 8

B. Ordering permutations

This section constructs measurable ordering permutations for locally Lipschitz scalar functions, preserving local Lipschitz regularity and almost-everywhere derivatives. The proof proceeds inductively by inserting each new function into an existing ordering.

Ordering definition

  • An ordering permutation sorts scalar functions in ascending order, with measurable choices resolving ties.The ordering satisfies f_k1(t)(t) ≤ ... ≤ f_kN(t)(t).Source: B. Ordering permutations · p. 8

Regularity

  • Lemma 8 guarantees a measurable ordering whose ordered functions are locally Lipschitz.For almost every t, each ordered derivative equals the derivative of the selected original function.Source: B. Ordering permutations · p. 8

Extremal selection

  • Lemma 9 selects a measurable maximizer or minimizer whose derivative matches the extremal function almost everywhere.The result follows from generalized Danskin and measurable-selector arguments.Source: B. Ordering permutations · p. 8

Inductive construction

  • The proof of Lemma 8 uses induction, repeatedly inserting the next function into the ordered first N functions.Each insertion preserves local Lipschitzness and is represented by a measurable permutation.Source: B. Ordering permutations · pp. 8–9
  • Composing the insertion permutations produces a final permutation relating the ordered functions and their derivatives almost everywhere.This completes the induction step.Source: B. Ordering permutations · p. 9

C. Some Technical Lemmas and Proofs of Lemmas 3, 5

These lemmas transform signed opinion dynamics into dynamics of opinion moduli, establish boundedness and asymptotic equivalence tools, and derive structural conditions for bipartite consensus. The maximal modulus is non-increasing, while essentially equivalent protocols share limit-set properties.

Modulus dynamics

  • The modulus χ_k(t)=|x_k(t)| is locally Lipschitz and obeys a signed interaction equation almost everywhere.The sign factor θ_ki combines interaction signs with the signs of the participating opinions.Source: C. Some Technical Lemmas and Proofs of… · p. 9
  • Ordering the moduli enables analysis of the maximum M_N(t)=max_j|x_j(t)| and its derivative.The ordering permutation is measurable and compatible with the derivative calculations.Source: C. Some Technical Lemmas and Proofs of… · p. 9

Boundedness and convergence

Protocol equivalence

  • Essentially equivalent protocols remain uniformly close after a sufficiently large time and have identical Ω-sets.The comparison uses integrable coefficient differences and invariant bounded sets.Source: C. Some Technical Lemmas and Proofs of… · p. 9
  • Modulus consensus, stability, bipartite consensus, and partial modulus consensus depend only on the Ω-set and are preserved under essential equivalence.Modulus consensus occurs exactly when every limiting state has equal modulus.Source: C. Some Technical Lemmas and Proofs of… · p. 9

Bipartite consensus

  • If the interaction topology is not quasi-strongly connected, two disjoint source subsets can evolve independently, making bipartite consensus impossible.This establishes the necessity of the relevant connectivity condition.Source: C. Some Technical Lemmas and Proofs of… · p. 10

D. Proof of Theorems 3, 4 and Corollary 3

Under cut-balance, the proofs establish integrability of modulus discrepancies and convergence of individual moduli, then connect essential strong connectivity and structural balance to modulus and bipartite consensus. A gauge-transformed auxiliary protocol supplies the sufficiency argument, but cut-balance is not preserved by that transformation.

Technical lemmas

  • Cut-balance is the central assumption used to control ordered modulus discrepancies through integrability arguments.The proof repeatedly applies cut-balance to sets of agents ordered by their moduli.Source: D. Proof of Theorems 3, 4 and… · p. 10
  • Lemma 13 shows that transformed interaction terms and ordered-modulus derivatives belong to L1[0,∞].This provides the integrability needed for convergence arguments.Source: D. Proof of Theorems 3, 4 and… · p. 10
  • The proof derives integrability for successive ordered-modulus gaps, ruling out divergent decreases because the moduli remain nonnegative.This induction yields convergence of all modulus components.Source: D. Proof of Theorems 3, 4 and… · p. 10

Limit structure

  • Corollary 4 gives finite limits for each modulus and constrains limiting signs when agents essentially cooperate or compete.Simultaneous essential cooperation and competition forces the corresponding limiting modulus to zero.Source: D. Proof of Theorems 3, 4 and… · p. 10

Modulus consensus

  • Essential strong connectivity is sufficient for modulus consensus, while the resulting signed graph is shown to be structurally balanced.The proof propagates equal limiting moduli along paths and excludes negative cycles.Source: D. Proof of Theorems 3, 4 and… · pp. 10–11

Bipartite consensus

  • For bipartite consensus, essential strong connectivity is necessary, while a well-defined, strongly connected, structurally balanced signed graph is sufficient.The sufficiency proof uses hostile camps and an auxiliary protocol with ±1 equilibrium values.Source: D. Proof of Theorems 3, 4 and… · p. 11

Proof limitation

  • A gauge transformation cannot directly invoke unsigned-graph results because removing inessential interactions destroys cut-balance.Cut-balance depends on the entire time-varying matrix, not only integrated interaction magnitudes.Source: D. Proof of Theorems 3, 4 and… · p. 11

E. Proof of Theorem 2 and Corollary 1

Theorem 2 proves convergence of all opinion moduli under uniform strong connectivity by inductively propagating contraction from larger to smaller ordered moduli. Corollary 1 then classifies the resulting modulus-consensus behaviors.

Uniform estimates

  • Lemma 14 provides uniform modulus bounds over finite intervals under bounded interaction weights and connectivity assumptions.Each modulus is bounded by a convex combination of its initial value and the interval maximum.Source: E. Proof of Theorem 2 and Corollary 1 · p. 11
  • Lemma 15 ensures that connectivity transfers a modulus gap from agents outside a set to at least one agent inside it.The estimate uses strong ε-connectivity over an interval of length T.Source: E. Proof of Theorem 2 and Corollary 1 · p. 11

Theorem 2

  • Theorem 2 assumes uniformly bounded interactions and strong ε-connectivity of every integrated graph over a fixed horizon.These assumptions provide constants controlling the contraction estimates.Source: E. Proof of Theorem 2 and Corollary 1 · p. 11
  • All ordered moduli converge to the maximal-modulus limit through a descending induction on their order.If a lower modulus stayed separated, Lemma 15 would force enough agents below the maximal limit to contradict the induction hypothesis.Source: E. Proof of Theorem 2 and Corollary 1 · p. 11

Corollary 1

  • Corollary 1 identifies stability, polarization, and consensus as the three possible types of modulus consensus.The proof uses the classification of modulus-consensus states and excludes alternatives under the stated initial conditions.Source: E. Proof of Theorem 2 and Corollary 1 · p. 12

F. Proof of Lemma 6 and Theorems 5, 6

The proofs establish bounded, globally defined solutions and derive modulus consensus under uniform strong connectivity, with stronger implications for cut-balanced graphs.

Proof of Lemma 6

Proof of Theorem 5

Proof of Theorem 6

  • Theorem 6 establishes infinite prolongability by combining bounded solutions with bounded derivatives and bounded interaction matrices.The derivative and matrix bounds follow from equation (13).Source: F. Proof of Lemma 6 and Theorems 5, 6 · p. 12

VII. CONCLUSIONS AND RELATED WORKS

The paper extends Altafini’s signed-network opinion model to switching directed topologies and characterizes conditions for modulus consensus, including cut-balanced cases.

Conclusions

  • The model accommodates attractive and repulsive interactions, allowing opinions to agree in modulus while differing in sign.This includes convergence of all opinions to zero.Source: §VII · p. 12
  • Sufficient conditions for modulus consensus under switching directed topologies reduce to uniform strong connectivity.Source: §VII · p. 12
  • For cut-balanced graphs, the paper gives necessary and sufficient conditions classified into stability and bipartite consensus.The latter includes consensus or polarization.Source: §VII · p. 12
  • Removing static-topology restrictions permits analysis of networks whose relationships switch between friendship and hostility.The authors are testing the theoretical results with data from human social groups.Source: §VII · p. 12

Related papers

Loading 1508.05034v1…