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.

  • Problem

    Existing signed-graph opinion models mainly address static topologies, while time-varying relationships and nonlinear social dynamics require a broader analysis.

  • Method

    The paper analyzes signed opinion protocols over general time-varying graphs and applies a common framework to linear and nonlinear dynamics, including cut-balanced networks.

  • Results

    Uniform strong connectivity suffices for modulus consensus, and cut-balanced graphs admit necessary and sufficient conditions for bipartite modulus consensus and stabilization.

  • Takeaways & Limitations

    The results distinguish stabilization from consensus and polarization in signed networks whose relationships may change over time.

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.
  • Prior work: Altafini’s signed-graph model allows opinions to agree in modulus while differing in sign.For structurally balanced graphs, this behavior represents polarization between hostile camps.
  • 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.
  • 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.
  • Model and graph structure: 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.

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.
  • Time-varying graph classes: 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.
  • 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.
  • 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.
  • 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.
  • Main results: 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.

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.
  • A. Time-invariant protocols: 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.
  • A. Time-invariant protocols: 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 (ξ, −ξ, ρξ).
  • 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.
  • B. Protocols over dynamic signed graphs: 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.
  • B. Protocols over dynamic signed graphs: 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.

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.
  • 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.
  • 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.
  • Necessary and sufficient conditions: 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.
  • 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.
  • 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.

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.
  • Assumptions and transformation: 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.
  • 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).
  • 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.
  • 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.

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.
  • 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.
  • Theorem 6: 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.
  • 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.
  • 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.

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.
  • Gauge transformation: 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.
  • 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.
  • 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.

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).
  • 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.
  • 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.
  • 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.
  • Inductive construction: Composing the insertion permutations produces a final permutation relating the ordered functions and their derivatives almost everywhere.This completes the induction step.

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.
  • Modulus dynamics: 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.
  • Boundedness and convergence: The maximal modulus is non-increasing, and its total variation is integrable over [0,∞).This yields convergence of the maximal modulus to a finite limit.
  • 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.
  • Protocol equivalence: 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.
  • 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.

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.
  • Technical lemmas: Lemma 13 shows that transformed interaction terms and ordered-modulus derivatives belong to L1[0,∞].This provides the integrability needed for convergence arguments.
  • Technical lemmas: 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.
  • 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.
  • 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.
  • 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.
  • 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.

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.
  • Uniform estimates: 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.
  • 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.
  • Theorem 2: 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.
  • 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.

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: Solutions remain bounded because the infinity norm is nonincreasing under the analyzed dynamics.Lemma 6 uses |x(t)|∞≤|x(0)|∞ to establish boundedness.
  • Proof of Theorem 5: Under the USC assumption, modulus consensus follows from Theorem 2 and Lemma 6.
  • Proof of Theorem 5: For ESC and cut-balanced graphs, modulus consensus is implied by Theorem 3.
  • 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).

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.
  • Conclusions: Sufficient conditions for modulus consensus under switching directed topologies reduce to uniform strong connectivity.
  • Conclusions: For cut-balanced graphs, the paper gives necessary and sufficient conditions classified into stability and bipartite consensus.The latter includes consensus or polarization.
  • Conclusions: 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.
Loading 1508.05034v1…