PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph partitions and cluster synchronization in networks of oscillators

Michael T. Schaub, Neave O'Clery, Yazan N. Billeh, Jean-Charles Delvenne, Renaud Lambiotte, Mauricio Barahona

arXiv:1608.04283v2physics.soc-phcs.SIeess.SYnlin.CD

TL;DR

The paper asks how regularities in network coupling can produce synchronization within clusters rather than across an entire network. It uses external equitable partitions and quotient graphs to identify invariant cluster dynamics, extending the framework from positive to signed networks and from consensus to nonlinear oscillator models. The results establish cluster invariance, localized Laplacian eigenvectors, and bipolar cluster synchronization in structurally balanced signed networks.

  • Problem

    Existing synchronization studies emphasize total synchronization, while networks can instead contain groups converging to distinct behaviors.

  • Method

    The paper uses external equitable partitions, quotient graphs, and invariant-subspace analysis to study linear and nonlinear synchronization in positive and signed networks.

  • Results

    The framework yields invariant cluster-synchronized dynamics for quotient graphs and extends to bipolar cluster synchronization in structurally balanced signed networks.

  • Takeaways & Limitations

    External equitable partitions provide a coarse-grained framework for cluster synchronization across consensus, MSF oscillator, Kuramoto, and signed-network settings.

Abstract

from arXiv · show

Synchronization over networks depends strongly on the structure of the coupling between the oscillators. When the coupling presents certain regularities, the dynamics can be coarse-grained into clusters by means of External Equitable Partitions of the network graph and their associated quotient graphs. We exploit this graph-theoretical concept to study the phenomenon of cluster synchronization, in which different groups of nodes converge to distinct behaviors. We derive conditions and properties of networks in which such clustered behavior emerges, and show that the ensuing dynamics is the result of the localization of the eigenvectors of the associated graph Laplacians linked to the existence of invariant subspaces. The framework is applied to both linear and non-linear models, first for the standard case of networks with positive edges, before being generalized to the case of signed networks with both positive and negative interactions. We illustrate our results with examples of both signed and unsigned graphs for consensus dynamics and for partial synchronization of oscillator networks under the master stability function as well as Kuramoto oscillators.

I. INTRODUCTION

The paper shifts from total synchronization toward cluster synchronization, using external equitable partitions (EEPs) to identify invariant cluster subspaces and quotient-graph dynamics. This graph-theoretical framework complements symmetry-based methods, applies beyond them, and extends to signed networks.

  • Cluster synchronization studies groups of nodes that converge to distinct behaviors, complementing the traditional focus on total synchronization.
  • For signed networks, signed EEPs extend the framework to structurally balanced interactions and support bipolar consensus or bipolar cluster synchronization.
  • An EEP partitions nodes into cells whose external connectivity patterns satisfy a common regularity, while ignoring internal connections.
  • The indicator matrix H spans an invariant subspace of the graph Laplacian, yielding localized eigenvectors associated with the partition.
  • The quotient graph is a coarse-grained network whose nodes represent partition cells and whose intercell weights are inherited from the original graph.
  • EEP analysis complements symmetry-based orbit partitions because some equitable partitions are not induced by graph symmetries.

III. CLUSTER SYNCHRONIZATION UNDER THE EXTERNAL EQUITABLE PARTITION

For Laplacian-coupled consensus systems, EEPs create invariant cluster states and reduce cell-averaged dynamics to a quotient graph. The same structure is linked to localized Laplacian eigenvectors and applies also to consistent bounded inputs.

  • EEP indicator matrices span invariant Laplacian subspaces, producing eigenvectors localized on the partition cells.
  • If the initial state is x = Hy, nodes within each cell remain identical and evolve according to the quotient graph.
  • Cell-averaged states follow a lower-dimensional quotient-graph model with dimensionality equal to the number of EEP cells.
  • Inputs consistent with the partition preserve equality among nodes within each cell.
  • The one-cell partition recovers global consensus as a special case of the EEP framework.

B. EEPs and nonlinear cluster synchronization within the MSF framework

The MSF formulation extends EEP analysis to identical nonlinear oscillators with Laplacian coupling. Cluster-synchronized initial conditions remain invariant and evolve through quotient-graph dynamics.

  • The MSF framework analyzes identical nonlinear oscillators with intrinsic dynamics F, coupling function G, and coupling strength γ.
  • The analysis uses Laplacian coupling and associated EEPs rather than adjacency-matrix coupling and ordinary equitable partitions.
  • A cluster-synchronized state is represented by an indicator matrix H and cell variables y_s containing one oscillator state per partition cell.

1. EEPs and invariance of cluster-synchronized states

An EEP makes the cluster-synchronized subspace invariant: when states start identical within each cell, the full nonlinear oscillator dynamics follows a lower-dimensional quotient-graph system. In the star-network example, the two-cell structure supports either global or sustained cluster synchronization depending on coupling strength.

  • EEP quotient dynamics: An EEP with indicator matrix H defines a quotient graph whose cell variables evolve according to reduced dynamics.The quotient state y has one oscillator state per cell, and the full state is reconstructed as x = (H ⊗ I_d)y.
  • EEP quotient dynamics: If the initial state is identical within each EEP cell, nodes within each cell remain identical for all time.This invariance follows from the compatibility between the full coupling and the EEP-induced quotient dynamics.
  • Rössler example: A star graph of N = 8 oscillators has two EEP cells: the central node and the seven spoke nodes.The example uses three-dimensional chaotic Rössler oscillators coupled through x1.
  • Rössler example: For γ = 0.3, the cluster-synchronized state evolves toward global synchrony, whereas for γ = 0.03 it remains clustered without converging globally.At the lower coupling, global synchronization of the quotient dynamics is no longer linearly stable.

2. EEPs and cell-averaged synchronization dynamics

EEP invariance extends to nonlinear oscillator networks, but nonlinearities generally prevent cell averages from exactly following quotient dynamics. Stability analysis separates perturbations within the cluster manifold from transversal modes that can drive divergence.

  • Cell-averaged dynamics: Nonlinear node and coupling functions generally do not commute with linear cell averaging, so averaged dynamics is not exactly quotient-graph dynamics.This differs from the linear consensus case, where cell averages are described by the quotient system.
  • Cell-averaged dynamics: Near a stable cluster-synchronized state, first-order approximations can make averaged dynamics approximately follow the quotient dynamics.The approximation uses Jacobians of the intrinsic and coupling functions around the synchronized state.
  • Rössler example: For γ = 0.3, cell-averaged and quotient Rössler dynamics converge together, whereas for γ = 0.03 they diverge at long times.The figure links this divergence to instability of the relevant perturbation around the cluster-synchronized state.
  • MSF stability: EEP-based MSF analysis maps quotient-Laplacian eigenvectors into the cluster manifold and separates them from transversal eigenmodes.The transversal modes are orthogonal to the partition matrix and are mean-free within each cell.
  • MSF stability: Damping all transversal modes establishes local stability of the cluster-synchronized manifold but does not determine convergence within that manifold.Additional stability inside the manifold governs whether trajectories approach particular cluster-synchronized states.

C. EEP cluster synchronization in Kuramoto networks

EEP structure also organizes cluster synchronization in Kuramoto networks, whose sinusoidal coupling can be expressed through Laplacian-like dynamics. Exact quotient equivalence holds on the EEP-synchronized subspace, while linear averaging is reliable only in a restricted phase configuration.

  • Kuramoto formulation: EEP methods extend to Kuramoto networks, despite their sinusoidal coupling being outside the standard diffusive MSF formulation.The Kuramoto model can be rewritten using a Laplacian with time-varying edge weights.
  • Kuramoto formulation: The Kuramoto equations use oscillator phases and intrinsic frequencies together with adjacency-defined network coupling.The vector formulation introduces W(x) = diag(sinc(x)) to express the dynamics in Laplacian form.
  • EEP cluster dynamics: For initial conditions constant within each EEP cell, the full Kuramoto system is exactly equivalent to lower-dimensional quotient-graph dynamics.This equivalence applies to the invariant cluster-synchronized state.
  • Cell averaging: Linear cell averaging closely matches quotient dynamics when phases begin near the cell-averaged state within an open semicircle, but not when phases are more widely spread.The figure contrasts the aligned and non-aligned averaging regimes.

1. Case I: equal intrinsic frequencies

With identical intrinsic frequencies, EEPs define invariant Kuramoto cluster states and a quotient-graph description of their dynamics. The quotient representation remains exact on the synchronized subspace, while cell averaging can fail for widely separated phases.

  • Equal-frequency reduction: Identical intrinsic frequencies allow the common frequency to be removed by grounding or transforming to a rotating frame.The analysis therefore sets ω_i = ω and assumes ω = 0 without loss of generality.
  • Quotient dynamics: An EEP quotient graph assigns one phase variable to each cell and uses inter-cell out-degrees to define its Laplacian dynamics.The quotient state is represented by the cell-phase vector ψ.
  • Invariant cluster states: EEP cluster-synchronized states form an invariant subspace of the full Kuramoto dynamics, so Hψ remains within the full-system dynamics.The proof uses the projection associated with H and the symmetry of the sinc coupling function.
  • EEP preservation: Rescaling inter-cell edge weights by factors depending only on the cells preserves the EEP and its associated projection structure.This preserves the partition’s relevant out-degree patterns and the commutation relation with the modified Laplacian.
  • Quotient interpretation: The full Kuramoto model follows quotient dynamics whenever it synchronizes to a particular EEP, including partitions not induced directly by graph symmetries.The paper distinguishes equitable partitions from orbit partitions generated by symmetry groups.
  • Cell averaging: Cell averages approximate quotient dynamics near the EEP-averaged state but fail to align when phases extend outside an open semicircle.The failure reflects the inadequacy of naive linear averaging on the phase torus.

2. Case II: non-equal intrinsic frequencies commensurate with an EEP

When oscillators within each EEP cell share an intrinsic frequency, the cluster-synchronized manifold remains invariant and is governed by the quotient graph. Stability is separate: decreasing coupling can destabilize these solutions.

  • Oscillators with non-equal intrinsic frequencies can retain cluster synchronization when frequencies are identical within each EEP cell.The cell frequencies act as constant inputs aligned with the partition.
  • The cluster-synchronized state is invariant under the Kuramoto dynamics and governed by the quotient graph.This is the most synchronous state available when heterogeneous frequencies prevent globally identical synchronization.
  • As coupling λ decreases and ||ϖ/λ|| increases, synchronized and cluster-synchronized solutions become unstable.The analysis establishes invariance, not stability; stability depends on frequency spread relative to coupling.
  • Figure 5 shows identical full-system and quotient dynamics for initial conditions constant within cells, followed by cluster synchronization.For suitably concentrated initial phases, quotient dynamics also remains a good descriptor over time.

IV. CLUSTER SYNCHRONIZATION IN NETWORKS WITH POSITIVE AND NEGATIVE WEIGHTS

The framework is extended from positive-weight networks to signed networks, where structural balance and signed Laplacians provide the basis for defining signed external equitable partitions. These tools support analysis of positive and negative interactions while preserving useful spectral structure.

  • Signed networks model positive and negative interactions found in social, biological, and other networked systems.Signed links can represent friendship or hostility, and trust or distrust.
  • The signed Laplacian is positive semidefinite and has a zero eigenvalue for connected, structurally balanced graphs.It is constructed using absolute degrees and signed interactions.
  • Signed external equitable partitions extend EEP analysis to structurally balanced signed graphs.The construction relies on switching equivalence and the signed Laplacian.
  • Structural balance means every closed path has positive sign product and equivalently permits a two-faction split with positive within-faction and negative between-faction interactions.A diagonal switching transformation converts the signed Laplacian into the standard Laplacian of a positive-weight graph.

3. Signed external equitable partitions

A signed external equitable partition is obtained by switching a structurally balanced signed graph to a positive equivalent graph and transforming its EEP indicator matrix. The resulting quotient description supports bipolar cluster-synchronized consensus, with signs determined by node polarization.

  • A sEEP is defined from an EEP of the positive switching-equivalent graph using the signed indicator matrix Hσ = ΣH.This signed indicator matrix spans an invariant subspace of the signed Laplacian.
  • Cells in a sEEP share the same absolute out-degree pattern, and the associated quotient graph has only positive weights.The signed partition is illustrated by a graph with four cells.
  • Structurally balanced signed consensus converges to a polarized state whose two factions have equal-magnitude values with opposite signs.The zero-eigenvalue eigenvector has entries σ_i ∈ {−1,+1}.
  • sEEP cluster-synchronized states remain invariant under signed consensus dynamics and evolve according to the quotient graph.An initial state consistent with the sEEP stays in that manifold for all times.
  • Within each sEEP cell, node values have equal magnitude but may have opposite signs according to polarization, producing bipolar cluster synchronization.A single cell can therefore contain nodes from opposite factions.
  • The final sign of each node variable is determined by σ^T x_0, while the dynamics approaches the bipolar consensus.This determines polarization-dependent outcomes in the signed network.

2. Bipolar cluster synchronization for nonlinear dynamics with Laplacian couplings

The signed-partition framework extends to nonlinear Laplacian-coupled dynamics, including signed Kuramoto networks. Numerical examples show quotient-governed bipolar synchronization, with polarization producing opposite phases within cells.

  • Nonlinear dynamics on signed networks can support bipolar cluster synchronization based on a signed external equitable partition.The signed case adds polarization-dependent behavior to the unsigned nonlinear framework.
  • Signed Kuramoto networks with positive and negative couplings remain comparatively understudied relative to standard positive-coupling networks.The cited literature contains only a handful of mean-field results for signed Kuramoto models.
  • For structurally balanced signed networks, switching adjustments recover the conclusions established for the corresponding unsigned analysis.The signed Kuramoto model and its quotient dynamics are written using the signed Laplacian.
  • For sEEP-aligned initial conditions, full signed Kuramoto dynamics is equivalent to lower-dimensional quotient dynamics up to node polarization signs.For initially concentrated phases, sign-adjusted cell averages closely track the quotient dynamics.
  • With non-identical intrinsic frequencies commensurate with the sEEP, the model converges to cell-consistent states with polarization-dependent out-of-phase behavior within cells.This extends bipolar clustering to heterogeneous-frequency signed Kuramoto networks.

V. DISCUSSION

The paper uses external equitable partitions to coarse-grain synchronization dynamics, extending the framework to signed networks and identifying invariant-subspace-based dimensional reduction. It also delineates computational, stability, and modeling boundaries while outlining extensions to broader coupling schemes.

  • Core framework: External equitable partitions coarse-grain generic synchronization processes by grouping nodes with equivalent dynamical roles into cells sharing trajectories.The resulting reduced dynamics is represented through the partition structure and its associated invariant subspace.
  • Signed networks: In structurally balanced signed networks, each partition cell can split into two out-of-phase factions with equal magnitude and opposite sign.
  • Connections with symmetry groups: EEP computation is more challenging in general than symmetry-group analysis, although efficient algorithms exist for EEPs centered around a node.These algorithms can characterize particular nodes’ dynamical influence on global network behavior.
  • Other signed coupling schemes: Alternative signed coupling matrices may preserve algebraic invariant-partition analyses while losing combinatorial equitability properties used by EEP-search algorithms.For L±, indefiniteness can also complicate the dynamical interpretation and affect stability in generic systems.
  • Relation to other synchronization notions: The analysis primarily establishes existence and invariance of cluster-synchronized states, with stability discussed in the master stability function context.The paper notes that chimera-state mechanisms and links between bipolar synchronization and structural balance remain conjectural or future-work directions.
  • Future work: Future extensions include relaxing exact EEP requirements and treating directed, time-varying, and delayed couplings.
Loading 1608.04283v2…