PaperlayerView exact revision on arXiv

Source-linked AI summary

Cluster consensus in discrete-time networks of multi-agents with inter-cluster nonidentical inputs

Yujuan Han, Wenlian Lu, Tianping Chen

arXiv:1201.2803v2math.OC

TL;DR

Cluster consensus asks when agents can synchronize within groups while remaining separated across groups. The paper uses graph and stochastic-matrix conditions with inter-cluster nonidentical inputs to study fixed and switching topologies. It derives synchronization and separation results and illustrates them with a modified non-Bayesian social learning model.

  • Problem

    Prior work mainly addressed global consensus, while cluster-consensus studies faced graph-topology restrictions and had not deeply investigated inter-cluster separation.

    Source: §I · p. 2

  • Method

    The paper extends spanning-tree, scramblingness, and Hajnal-inequality tools to clusters and introduces inter-cluster nonidentical inputs.

    Source: §I · p. 2

  • Results

    Under suitable graph and input conditions, the paper establishes intra-cluster synchronization for static and switching topologies and uses nonidentical inputs to obtain inter-cluster separation.

    Source: B. Intra-cluster synchronization · p. 5, C. Inter-cluster separation · pp. 5–6, WITH SWITCHING TOPOLOGIES · p. 7

  • Takeaways & Limitations

    In the modified social-learning model, beliefs within each cluster converge while external inputs preserve differences between groups despite interactions.

    Source: §VI · p. 10

Abstract

from arXiv · show

In this paper, cluster consensus of multi-agent systems is studied via inter-cluster nonidentical inputs. Here, we consider general graph topologies, which might be time-varying. The cluster consensus is defined by two aspects: the intra-cluster synchronization, that the state differences between each pair of agents in the same cluster converge to zero, and inter-cluster separation, that the states of the agents in different clusters are separated. For intra-cluster synchronization, the concepts and theories of consensus including the spanning trees, scramblingness, infinite stochastic matrix product and Hajnal inequality, are extended. With them, it is proved that if the graph has cluster spanning trees and all vertices self-linked, then static linear system can realize intra-cluster synchronization. For the time-varying coupling cases, it is proved that if there exists T>0 such that the union graph across any T-length time interval has cluster spanning trees and all graphs has all vertices self-linked, then the time-varying linear system can also realize intra-cluster synchronization. Under the assumption of common inter-cluster influence, a sort of inter-cluster nonidentical inputs are utilized to realize inter-cluster separation, that each agent in the same cluster receives the same inputs and agents in different clusters have different inputs. In addition, the boundedness of the infinite sum of the inputs can guarantee the boundedness of the trajectory. As an application, we employ a modified non-Bayesian social learning model to illustrate the effectiveness of our results.

I. INTRODUCTION

The paper shifts from global consensus, where all agents converge to one state, to cluster consensus, which requires synchronization within clusters and distinct trajectories across clusters. It develops graph- and matrix-based conditions for this behavior under fixed or switching topologies, using inter-cluster nonidentical inputs to obtain separation.

I. INTRODUCTION

  • Cluster consensus requires bounded trajectories, vanishing state differences within each cluster, and persistent separation between agents in different clusters.The paper contrasts this with global consensus, in which all agents converge to a common state.Source: §I · p. 2
  • Inter-cluster nonidentical inputs are introduced to separate clusters, with agents in each cluster receiving identical inputs and different clusters receiving different inputs.The system uses stochastic-matrix coupling, and the paper also considers time-varying couplings.Source: §I · p. 2
  • The paper targets limits of prior cluster-consensus work: restricted graph topologies and little investigation of inter-cluster separation.Earlier work included fixed and switching topologies, while the cited previous work studied cluster synchronization of coupled nonlinear systems.Source: §I · p. 2
  • The analysis extends spanning trees, scramblingness, and Hajnal’s inequality to cluster versions, and uses infinite matrix products and graph theory rather than the Lyapunov approach in.The paper identifies cluster-spanning trees, cluster scramblingness, and a cluster Hajnal inequality as its extensions.Source: §I · p. 2
  • The paper derives criteria for fixed and switching topologies, then applies the results to a modified non-Bayesian social learning model.The paper organization places fixed-topology analysis before switching-topology analysis and the application.Source: §I · p. 2

II. PRELIMINARIES

The preliminaries extend graph and stochastic-matrix concepts to clustered networks. These cluster notions support conditions for contraction of within-cluster differences.

II. PRELIMINARIES

  • A cluster-spanning tree exists when each cluster has a root vertex with paths to every vertex in that cluster; roots and paths may lie outside the cluster.The root need not be shared across clusters.Source: §II · p. 3
  • A graph is cluster-scrambling when every pair of vertices in the same cluster shares an incoming neighbor; pairs in different clusters need not.The cluster ergodicity coefficient measures this property and is positive exactly when the graph is cluster-scrambling.Source: §II · p. 3
  • The cluster Hajnal diameter measures differences among rows within clusters, and its convergence to zero is equivalent to intra-cluster synchronization.The paper extends the Hajnal diameter to the clustered setting.Source: §II · p. 3
  • With cluster-spanning trees and self-links, a product of n − 1 stochastic matrices is cluster-scrambling.The stated lemma applies when each matrix in the product has cluster-spanning trees and self-links.Source: §II · p. 3
  • A stochastic matrix with positive diagonal elements has powers that converge exponentially.Source: §II · p. 4

A. Invariance of the cluster consensus subspace

The cluster-consensus subspace consists of states that are equal within each cluster. The dynamics preserve this subspace when inputs are identical within clusters and the coupling has inter-cluster common influence.

A. Invariance of the cluster consensus subspace

  • The cluster-consensus subspace comprises states whose components agree for every pair of agents in each cluster.The paper begins by considering whether this structure, once present initially, is preserved by the dynamics.Source: A. Invariance of the cluster consensus… · p. 4
  • Intra-cluster-identical inputs and inter-cluster common influence make the cluster-consensus subspace invariant under the system dynamics.Common influence means each agent in a cluster receives the same total coupling weight from every other cluster.Source: A. Invariance of the cluster consensus… · p. 4
  • The invariance result follows because each agent in a cluster receives an identical update when the state is already equal within clusters.Source: A. Invariance of the cluster consensus… · p. 4

B. Intra-cluster synchronization

The paper establishes intra-cluster synchronization for a static stochastic coupling matrix under common inter-cluster influence and suitable graph and input conditions. The proof uses cluster-diameter contraction, while bounded inputs and bounded cumulative input ensure bounded trajectories.

B. Intra-cluster synchronization

  • Common inter-cluster influence yields a cluster-Hajnal inequality that contracts the cluster diameter, strictly when the matrix is cluster-scrambling.The stated contraction is ∆C(H) ≤ (1−µC(A))∆C(B).Source: B. Intra-cluster synchronization · p. 4
  • Bounded u(t) and bounded partial sums of u, together with common inter-cluster influence, cluster-spanning trees, and positive diagonal elements, guarantee boundedness and intra-cluster synchronization.The theorem assumes the input is defined by the paper’s special intra-cluster-identical construction.Source: B. Intra-cluster synchronization · pp. 4–5
  • The proof establishes trajectory boundedness from the bounded input and bounded partial sums of the input.The theorem requires both bounds, not merely bounded instantaneous inputs.Source: B. Intra-cluster synchronization · p. 5
  • The synchronization argument uses cluster-scrambling matrix powers to drive the cluster diameter to zero.The proof obtains cluster-scrambling powers from the cluster-spanning-tree condition and positive diagonal elements.Source: B. Intra-cluster synchronization · p. 5

C. Inter-cluster separation

The paper establishes generic inter-cluster separation using periodic, cluster-specific inputs under common inter-cluster influence. Under stated graph and input conditions, the resulting system reaches cluster consensus with periodic limiting trajectories for each cluster.

C. Inter-cluster separation

  • The graph conditions require self-links, the stated uniform inter-cluster link condition, and cluster-spanning trees.These are the three listed graph requirements for the generic consensus result.Source: C. Inter-cluster separation · p. 5
  • The system generically reaches cluster consensus, with each cluster converging to a T-periodic trajectory.The result assumes the graph conditions and periodic-input condition stated for the theorem.Source: C. Inter-cluster separation · p. 5
  • The separation analysis reduces synchronized cluster states to a K-dimensional system using the common inter-cluster influence condition.One representative state per cluster gives the lower-dimensional state vector.Source: C. Inter-cluster separation · p. 6
  • Generic separation follows by showing that parameter choices yielding identical cluster components lie in measure-zero exceptional sets.The argument applies across cluster pairs to conclude that limiting cluster states are generically distinct.Source: C. Inter-cluster separation · pp. 6–7
  • Unlike, which assumed inter-cluster separation, this paper undertakes to prove it rigorously.The authors state that extending such a proof to general nonlinear coupled systems is very difficult, if not impossible.Source: C. Inter-cluster separation · p. 7

IV. CLUSTER-CONSENSUS IN DISCRETE-TIME NETWORK

For switching topologies, the paper gives conditions for intra-cluster synchronization and for full cluster consensus. The latter additionally requires bounded inputs and, for generic consensus with periodic cluster trajectories, periodic inputs whose sum over a period is zero.

WITH SWITCHING TOPOLOGIES

  • If every L-length union graph has cluster-spanning trees under the stated assumptions, the switching system cluster-synchronizes.The assumptions include a uniform lower bound on nonzero coupling weights and positive diagonal entries.Source: WITH SWITCHING TOPOLOGIES · p. 7
  • The authors say Theorem 3 does not extend to general nonlinear coupled systems because Lyapunov functions for time-varying coupled systems are generally unavailable.Source: WITH SWITCHING TOPOLOGIES · p. 7
  • With bounded input and cumulative input, the switching system is bounded; periodic zero-sum input additionally yields generic cluster consensus with T-periodic trajectories.The theorem uses the static inter-cluster common influence condition.Source: WITH SWITCHING TOPOLOGIES · p. 7

V. NUMERICAL EXAMPLES

The numerical example modifies a non-Bayesian social-learning model by adding cluster-specific inputs associated with cultural or religious backgrounds. It specifies three groups and a periodic input construction.

V. NUMERICAL EXAMPLES

  • The cited discrete-time cluster-consensus result requires the cluster count to equal the agent period, which must exceed one, unlike this paper’s self-linked setting.Source: §V · p. 8
  • The example divides nine individuals into three groups and treats cultural or religious background as cluster-specific external inputs.With observationally equivalent states, signals have no effect and the conditional-likelihood term is removed.Source: §V · pp. 8–9
  • The example uses common inter-cluster influence and alternating inputs u(2l)=1 and u(2l+1)=-1.Source: §V · p. 9

A. Static topology

In the static-topology example, the graph has cluster-spanning trees, and the belief trajectories exhibit intra-cluster synchronization while retaining separation between clusters.

A. Static topology

  • The example graph has cluster-spanning trees, with roots 3, 7, and 7 for clusters C1, C2, and C3.Source: A. Static topology · p. 9
  • Beliefs about both states converge asymptotically, indicating intra-cluster synchronization among individuals in each group.Source: A. Static topology · p. 9
  • The C2–C3 belief difference does not converge to zero, so distinct cultural or religious inputs remain consequential even for strongly connected groups.Source: A. Static topology · p. 9

B. Switching topologies

The switching-topology example satisfies the union-graph condition for cluster spanning trees and reaches cluster consensus. Comparing simulations with and without inputs illustrates the role of inter-cluster nonidentical inputs in separating groups.

B. Switching topologies

  • The periodically switching network reaches cluster consensus because the union graph has cluster spanning trees and the stated Theorem 4 assumptions hold.None of the individual topologies has cluster spanning trees; the union does, with roots 3, 7, and 7 for C1, C2, and C3.Source: B. Switching topologies · p. 9
  • Under Theorem 4’s assumptions, (22) with switching topologies can achieve cluster consensus; Fig. 3 shows beliefs µi,t(θj) (1≤i≤9) and ζ(θ1)=|µC2(θ1)−µC3(θ1)| reaching consensus, with beliefs convergent.Source: B. Switching topologies · p. 9
  • Without inter-cluster nonidentical inputs, the groups cannot separate, unlike the input-driven case shown in Fig. 2.The paper identifies the inputs as playing a key role in separating different groups.Source: B. Switching topologies · p. 9

VI. CONCLUSIONS

The paper develops cluster-consensus criteria for discrete-time systems with fixed or switching graph topologies using algebraic graph and matrix theory. A modified non-Bayesian social-learning example illustrates how external inputs support inter-cluster separation while within-cluster beliefs converge.

VI. CONCLUSIONS

  • The paper derives cluster-consensus criteria for discrete-time systems with fixed or switching topologies.Different inputs to different clusters are used to guarantee differences between clustered states.Source: §VI · p. 9
  • The analysis uses algebraic graph theory and matrix theory to study cluster consensus.The contribution passage describes this as a rigorous basis for the criteria.Source: §VI · pp. 9–10
  • In the modified social-learning example, beliefs converge within clusters while auxiliary external inputs preserve differences between groups.The auxiliary term flags differences in culture and/or region; the reported numerical results say interactions cannot eliminate the between-group difference.Source: §VI · p. 10

APPENDIX

The appendix develops matrix-based arguments for cluster synchronization, including a cluster version of the Hajnal diameter and a block transformation. Its proof passages establish contraction and exponential decay under the stated spectral conditions.

APPENDIX

  • The appendix uses cluster-root paths and neighborhoods to argue that two vertices in the same cluster acquire overlapping neighborhoods within a bounded number of steps.The proof seeks a time t ≤ n at which the neighborhoods intersect, using a cluster root with paths to both vertices.Source: APPENDIX · pp. 10–11
  • A coordinate transformation isolates a static top-left block because the cluster subspace is invariant under A(t).The selected basis includes eigenvectors associated with eigenvalue 1, while the remaining columns ensure the transformation is nonsingular.Source: APPENDIX · p. 11
  • The cluster Hajnal diameter equals the projection radius for the matrix product considered.The proof bounds each quantity by the other and concludes their equality.Source: APPENDIX · p. 12
  • Under the stated spectral-radius conditions, the transformed components w̃3(t) and w̃2(t) converge exponentially to zero.The passage ties w̃3(t) decay to ρC(A(·)) < 1 and w̃2(t) decay to ρ(Ã2,2) < 1 with bounded coupling.Source: APPENDIX · p. 12
Loading 1201.2803v2…