# A Novel Clustering Method Based on Quasi-Consensus Motions of Dynamical Multiagent Systems

Authors: Ning Cai; Chen Diao; M. Junaid Khan
Journal: Complexity
 (2017)

---

## Abstract

This paper presents a novel approach for clustering, which is based on quasi-consensus of dynamical linear high-order multiagent systems. The graph topology is associated with a selected multiagent system, with each agent corresponding to one vertex. In order to reveal the cluster structure, the agents belonging to a similar cluster are expected to aggregate together. To establish the theoretical foundation, a necessary and sufficient condition is given to check the achievement of group consensus. Two numerical instances are furnished to illustrate the results of our approach.


---

## Body

## 1. Introduction

With a rapid increase in the scale of massive data and information, the probing of potential knowledge in big data, such as data structures and certain unknown correlations, has been attracting more and more scholars. As an essential technique of data mining, clustering has been widely applied in various practical fields, such as linguistics [1], bone microarchitecture analysis [2], community detection [3], wind power prediction [4], image segmentation [5, 6], and even genome expression study [7].Clustering is about assigning certain set of data points into different clusters, for the purpose of highlighting the similitude of data points being organized in the same cluster, while simultaneously reflecting the distinctions between different clusters [8]. In the past decades, diverse clustering algorithms and criteria have been developed adequately, for example, normalized cut [6] and min-max cut [9] algorithms, the graph partitioning algorithms [10], the algorithms based on optimization of modularity functions [11], and the spectral clustering algorithms [12].In addition to the abovementioned literature, some clustering algorithms have also been presented which are built on the study of certain dynamical behaviors of networks, for example, the random walk algorithms and the network synchronization algorithms. Random walk implies shifting along a random route, with each step to a new nearest vertex. By random walk algorithms [13], the clustering structure of a given network topology could be probed with the aid of generated random walk flows. Conversely, the network synchronization algorithm stands from another perspective [14], which considers coordinating different signals among vertices. Typically certain Kuramoto vibrator is employed, such that synchronization of vibrations could be achieved within the same group.In this research article, a novel method for clustering is presented, which is rooted upon observation to the motions of dynamical multiagent systems. Concretely speaking, for the purpose of discerning the different affiliations of vertices in a given network, the selected dynamical multiagent system should be linked with the concerned network topology, and there should be a one-to-one correspondence between each pair of dynamical agent and vertex. The agents keep on moving inside a common space, either physical or abstract. Those corresponding to the vertices that are affiliated with any specific cluster should aggregate as time elapses. Finally, the clustering structure would be uncovered automatically, according to the formation of agent positions.Analogical topics as discussed above are usually referred to as group consensus in the field of control theory. Yu and Wang earlier were concerned with this phenomenon in [15]. Hu et al. discussed group consensus for two classes of dynamical multiagent systems, respectively, which are systems with hybrid protocols (there is discontinuous transfer of information between nearest groups [16]) and systems with distinct groups comprising different types of agents [17]. To achieve group synchronization of the coupled vibrators, Su et al. considered both the adaptive pinning control strategy [18] and the case with multiple leaders [19]. Xie et al. [20] addressed the group consensus problem of first-order systems. Other recent relevant studies include [21–23].The novelty of the current work compared with the aforementioned results in the literature lies in several perspectives. As far as we know, in the existing researches, the expected clustering formation is prescribed in advance, paying primary attention to synthesis of specific information transfer protocol for each group, so that the agents assigned to the group could ultimately aggregate. In contrast, in the framework of the current paper, the cluster distribution should completely be determined by the topology of network itself, without the need of any prerequisite knowledge aforehand. In this regard, the advantage of the current work is explicit, especially in its potential practicability.Besides introducing a novel method for clustering, a major contribution of this paper is proposing a criterion for checking whether or not a high-order LTI (Linear Time-Invariant) multiagent system can reach group consensus, which generalizes the existing well-known necessary and sufficient condition for consensus achievement [24–28]. In fact, the existing condition on consensus is a particular instance of the condition for group consensus presented here.In addition to the above, the current paper provides an exemplification of the usage of unstable dynamical systems, whereas, in contrast, unstable systems are conventionally regarded as being insignificant in control theory.Theoretical studies on dynamical multiagent systems have already been extensive in the area of control theory, especially on the consensus problem. However, the application instances corresponding to these theories that can well support them are still scarce. Our exploration attempts to introduce a practical scenario from the field of data analysis, under a motivation to facilitate applying, verifying, or enriching certain relevant researches.The remaining part of the current paper holds the following organization. The preliminaries and model formulation are introduced in Section2. In Section 3, the clustering method is expounded in detail, based on theoretical analysis on condition for group consensus. Section 4 exemplifies the technique by two simulation cases. Finally, this paper is concluded in Section 5.


## 2. Model Formulation and Preliminaries

The topology of the network for clustering can be expressed byG=GV,E, with V being the vertex set and E the weighted edge set. The G is assumed to be a graph of mth order, being undirected and connected. The ultimate objective of clustering is to assign the m elements of V into divergent affiliations, in accordance with the topology of G.For such a purpose, a procedure rooted in observing the motions of dynamical multiagent systems is put forward, to figure out the clustering formation automatically. The procedure is composed of the following two fundamental steps.Step 1.
Define a dynamical multiagent system as follows and attach with it the network topology concerned, with each agent associated with one particular vertex.(1)x˙i=ht,xi+∑j=1mw1jft,xj,xii=1,2,…,m,where xit∈Θ(i=1,2,…,m) expresses the state of agent i which is moving in a normed state space Θ, wij∈R+ is the weight indicating the strength of communication link between vertices i and j, and the functions h(·)  and  f(·) express the self-dynamics and the dynamical interagent information transfer protocol, respectively.Step 2.
Determine appropriate initial valuesxi(0)∈Θ(i=1,2,…,m) and then let the dynamical system operate autonomously.As time elapses, group consensus or quasi-consensus would manifest, as long as the overall setup of both the structure and parameters of dynamical multiagent system (1) is feasibly configured. Finally, a clustering result can be concluded via observing the setup formed by the agent states within the state space.The definition below formulates the concept of group consensus discussed in this paper.Definition 1.
For the dynamical multiagent system (1), if(2)limt→∞⁡xit-xjt=0then agents i and j reach anagreement. For a vertex set Vl⊂V, if ∀i,j∈Vl, the agents i and j reach an agreement, and then system (1) reaches aconsensus in Vl. If consensus is reached in each V1,V2,…,Vl,…,Vβ, respectively, with(3)V1∪V2∪⋯Vl⋯∪Vβ=Vthen the entire dynamical system reaches agroup consensus.Remark 2.
The assumption that the graph is both undirected and connected is merely due to practical requirements of clustering and is not due to any technical limitations. This can be understood through later discussions.


## 3. Group Consensus of Dynamical Linear Time-Invariant Systems

In this section, the detail of the clustering process is elaborated by employing high-order LTI multiagent systems, which are described as(4)x˙i=Axi+F∑j=1mwijxj-xii=1,2,…,m,where xi(t)=xi1(t)xi2(t)⋯xin(t)T∈Rn(i=1,2,…,m) expresses the state vector of agenti and matrices A,F∈Rn×n express the LTI self-dynamics of the agents and the information transfer protocol between nearest agents, respectively. The technique for successfully acquiring a rational clustering result depends on appropriately selecting values of the pair of matrices A and F.To this end, some previous results on consensus are reviewed first.Lemma 3 (see [28]).
For the dynamical LTI high-order system (4), if it reaches consensus, then, as t→∞, the motion of any agent is regulated by the equation ξ˙=Aξ.Lemma 4 (see [29]).
The Laplacian matrixL of a directed graph G has exactly one zero eigenvalue λ1=0 iff G includes a spanning tree, with the corresponding eigenvector ϕ=11⋯1T. Besides, all the remaining eigenvalues λ2,…,λm have positive real parts.Corollary 5.
The Laplacian matrixL of an undirected graph G has exactly a single zero eigenvalue λ1=0 iff G is connected, with the associated eigenvector ϕ=11⋯1T. Besides, all the remaining eigenvalues λ2,…,λm∈R+.Lemma 6 (see [28]).
For the dynamical multiagent system (4) with λ1=0,λ2,…,λm as the eigenvalues of the Laplacian matrix of the directed graph G, if A is not Hurwitz then the system reaches consensus iff (1)
the graph topologyG includes a spanning tree;(2)
all the matricesA-λiF(i∈{1,2,…,m}λi≠0) are Hurwitz.Lemma3 implies that if a certain subset of agents reaches a consensus, then the overall motion of this subset will ultimately be dominated by the matrixA. As long asA is Hurwitz, the motions of distinct consentaneous subsets would independently converge to the origin of state space, even without any exchange of information. Consequently, in order to differentiate agents between distinct affiliations, matrixA should not be Hurwitz. Actually, it is preferable forA to be unstable to avoid the possibility of critical stability, such that distinct clusters would mutually diverge.Theorem 7.
Consider the dynamical system (4). Suppose that the spectrum of Laplacian matrix of the directed graph with spanning tree is(5)λ1=0,λ2,…,λmwith the series of matrices(6)A,A-λ2F,…,A-λα-1Fbeing not Hurwitz and(7)A-λαF,A-λα+1F,…,A-λmFbeing Hurwitz. The pair of agents i and i+1 (or m and 1, if i=m) reaches agreement iff the ith row ψiT of the product Ψ=TQ possesses the configuration:(8)ψiT=∗102⋯0α-1∗α⋯∗m,where T∈Rm×m represents any feasible solution of the matrix equation(9)TL=Φ=1-11-1⋯⋯1-1-10⋯⋯1,Q∈Rm×m represents the nonsingular matrix that transforms the Laplacian matrix into the similar Jordan canonical form(10)Q-1LQ=J=0λ2∗λ3⋱⋱∗λm,and “∗” denotes any arbitrary value.Proof.
If the stack vector of the states of agents is defined as(11)xT=x1Tx2T⋯xmTTthen the system dynamics can be described by(12)x˙=Im⊗A-L⊗Fx.Let x~=(Q-1⊗In)x; then (12) can be transformed into(13)x~˙=Im⊗A-J⊗Fx~which is equivalent to(14)x~˙1x~˙2⋮⋮x~˙α⋮x~˙m=AA-λ2FΩ⋱⋱A-λα-1FΩA-λαF⋱⋱ΩA-λmFx~1x~2⋮⋮x~α⋮x~m,where “Ω” denotes an indefinite matrix that may be either F or zero. Define the auxiliary vectors (15)ηi=∑j=1mwijxi-xji=1,2,…,mand the stacked form as(16)η=η1Tη2T⋯ηmTT.It is evident that η=(L⊗In)x and(17)T⊗Inη=TL⊗Inx.Substituting (9) into the above equation yields(18)TL⊗Inx=Φ⊗Inx.It follows that(19)Φ⊗Inx=TL⊗Inx=TL⊗InQ⊗Inx~=TQJQ-1⊗InQ⊗Inx~=TQJ⊗Inx~=TQ⊗InJ⊗Inx~.
According to (14), x~˙m=(A-λmF)x~m; thus limt→∞⁡x~m(t)=0 because A-λmF is Hurwitz. Also, x~˙m-1=(A-λm-1F)x~m-1+Ωx~m holds, leading to limt→∞⁡x~m-1(t)=0, because A-λm-1F is Hurwitz and limt→∞⁡x~m(t)=0. A similar analysis can be recursively conducted till x~α is derived. As a result, it can be concluded that(20)limt→∞⁡x~1t=∗limt→∞⁡x~2t=∗⋮limt→∞⁡x~α-1t=∗limt→∞⁡x~αt=0⋮limt→∞⁡x~mt=0.
Due to the structure ofJ and the fact that λ1=0, the limits of the firstn entries of vector (J⊗In)x~ are zero and the limits of the entries indexed by n+1 to n(α-1) are indefinite, while the limits of the remaining entries are all zero. In other words,(21)limt→∞⁡J⊗Inx~=01⋯0n∗n+1⋯∗nα-10⋯0T.
Equation (19) can be rewritten as(22)Φ⊗Inx=Ψ⊗InJ⊗Inx~.According to the structure of Φ, the fact that agents i and i+1(i=1,2,…,m-1) reach an agreement implies that the entries in the left side of (22) indexed from (i-1)n+1 to ni tend to approach zero. That is to say, (23)limt→∞⁡ψiT⊗InJ⊗Inx~=0.
IfψiT=∗(1)0(2)⋯0(α-1)∗(α)⋯∗(m), then (23) is true because of the structure of (21). Conversely, if limt→∞⁡(ψiT⊗In)(J⊗In)x~=0, by noticing the fact that agreements are independent of the initial states and concerning the structure of (21), one can conclude that (24)ψiT=∗102⋯0α-1∗α⋯∗m.Remark 8.
Theorem7 can verify the agreement between any two agents, since the index assignment is trivial for a network. With this theorem, an overall portrait of the group consensus can be easily derived.Remark 9.
For the sake of the clustering application, only the undirected graph should be concerned. However, Theorem7 is more generalized since it addresses the systems with graphs that could have directed arcs.Remark 10.
MatrixT can be figured out by solving the matrix equation (9) as(25)T=ΦL†with L† expressing a Moore-Penrose inverse [30] of the singular Laplacian matrix L. Besides, matrix Q is constituted by the generalized eigenvectors of L. Therefore, it is simple to compute the matrix product Ψ=TQ.Remark 11.
Both the matricesT and Q are derived from the Laplacian matrix. Thus, if only the value of α is definite, the clustering result merely depends on the topology of graph.Remark 12.
Theorem7 is a bridge connecting the concept of consensus with the diverse nonconsensus cases. The smaller the value of α, the higher the degree of freedom that matrix Ψ would possess, for the sake of ensuring agreement. Here are two extremes: if α=2, then the overall system reaches a consensus, whatever the value of Ψ is; oppositely, if all the matrices A-λiF(i∈{1,2,…,m}) are not Hurwitz, then there should be no agreement at all. Actually, the existing well-known criterion for checking the consensus [24–28] (summarized as Lemma 6 here) can be regarded as a particular case or corollary of Theorem 7 when α=2.


## 4. Simulations on Clustering

This section will exemplify the presented technique of clustering by two simple and typical simulation instances.Example 1.
Consider a graph in Figure1.
The weighted adjacency matrix is(26)W=01100.10101000.11100.100000.10110.10010000.10100with the associated Laplacian matrix(27)L=2.1-1-10-0.10-12.1-100-0.1-1-12.1-0.10000-0.12.1-1-1-0.100-11.100-0.10-101.1and spectrum 0,0.2,1.095,3,3.105,3.2. Set the corresponding multiagent system as (28)A=0.251-10.25,F=0-10.51.In this instance, A-λ1F and A-λ2F are unstable and A-λ3F,…,A-λ6F are Hurwitz. Therefore, α=3. It yields that(29)T=0.324-0.324000.029-0.02900.323-0.323-0.010-0.010.021.5631.5631.875-1.875-1.562-1.563-0.0200.010.0100.323-0.6170.2940.029-0.029000.912-0.912-1.895-1.542-1.5631.5661.2482.189,Q=0.408-0.4080.035-0.289-0.7060.2890.408-0.408-0.035-0.2890.7060.2890.408-0.40800.5770-0.5770.4080.40800.57700.5770.4080.4080.706-0.2890.035-0.2890.4080.408-0.706-0.289-0.035-0.289.Consequently, (30)Ψ=TQ=000.0640-0.455000-0.032-0.2890.2270.2710-4.083000-0.36100-0.6450.289-0.0110.271001.29000.023004.083-0.67700.216-0.180.Based on Theorem 7, it is explicitly known that agents 1~3 reach a consensus; meanwhile agents 4~6 reach another consensus. As a result, a clustering formation is clearly exhibited. The motions of agents in the 2-dimensional state space are illustrated in Figure 2.Figure 1
Instance with group consensus. Default edge weight is 1.Figure 2
Group consensus motions witht∈[0,5]. Thick dots denote starting positions.Example 2.
In the second example, consider the graph illustrated in Figure3.
The adjacency matrix is(31)W=0110001010001100.100000.1011000100000100and the Laplacian matrix is(32)L=2-1-1000-12-1000-1-12.1-0.10000-0.12.1-1-1000-110000-101with the spectrum {0,0.0638,1,3,3,3.1362}. Let the associated agents be LTI second-order systems with(33)A=0.252-20.25,F=0.5-140.5.In this case, A-λ1F, A-λ2F are unstable, whereas A-λ3F,…,A-λ6F are Hurwitz. Still, α=3. It can be easily derived that(34)T=0.333-0.33300000.1670.5-0.167-0.167-0.167-0.167555-5-5-5-0.167-0.167-0.167-0.167-0.833-0.16700001-1-5.667-5.333-5556,Q=0.4080.41700.2890.707-0.2760.4080.41700.289-0.707-0.2760.4080.3900-0.57700.5900.408-0.3900-0.5770-0.5900.408-0.417-0.7070.28900.2760.408-0.4170.7070.28900.276.As a result(35)Ψ=TQ=00000.471000.41700.289-0.2360.276012.2420000.37600.4170.707-0.2890-0.27600-1.4140000-13.0760.7070-0.2360.176.According to Theorem 7, only two pairs of agents can achieve agreement, respectively, which are agents 1 and 2 and agents 5 and 6. The state trajectories obtained from the experiment are shown in Figure 4.
Although not all agents could achieve a precise group consensus in this case, from Figure4, the six agents can still be differentiated as two distinct clusters, practically, because the speed of divergence between the two clusters is much faster than the speed of divergence of the agents inside any cluster, in a certain time span. The variation of difference between the states of agents 2 and 3 is illustrated in Figure 5, which is x22(t)-x32(t).Figure 3
Second graph where default edge weight is 1.Figure 4
Quasi-consentaneous state trajectories of Example2 with t∈[0,3]. Thick dots denote starting positions.Figure 5
Variation of difference between states of agents 2 and 3.From Figure5, one can clearly sense that the vicissitude of the difference between agent 3 and the other agents in the same cluster is sophisticated, including two phases: before t=3, there is a tendency of agreement; however, afterwards, the tendency turns into a departure. This can be intuitively explained via a comparison with Example 1.Let us inspect the dynamical equation of agent 3; that is,(36)x˙3=Ax3+F∑j∈V1w3jxj-x3+F∑j∈V2w3jxj-x3.The vector field is composed of three components as shown above: the autonomous force, the interactive force from the nearest neighbors of the same cluster, and the interactive force from the other cluster. During the first phase of Example 2, the effect of the third component is relatively weak, because of the small value of w43; thus the states of agents belonging to the same cluster, that is, 1, 2, and 3, tend to achieve a consensus; however, as time elapses and the distance between the two clusters increases, the effect of the third component also keeps on increasing and ultimately it overwhelms the diminished second component and tears agent 3 away from its nearest neighbors 1 and 2. By contrast, in Example 1, a precise group consensus can be reached because the interactive force from the third component is balanced upon every agent.


## 5. Conclusion

A novel method for clustering is introduced in the current paper, based on group consensus or quasi-consensus of the motions of dynamical systems. For the sake of categorizing the vertex set into disparate clusters, a specific dynamical multiagent system is attached to the graph addressed, with each vertex associated with an agent. If the dynamical system is appropriately configured, then the agents affiliated with the similar cluster should gradually assemble together in their common state space; meanwhile the different clusters diverge away mutually. In addition to the method of clustering, a primary contribution is the presentation of a criterion for checking whether or not a group consensus could be reached by high-order linear multiagent systems, which is a necessary and sufficient condition generalizing the previous well-known condition of consensus. In fact, the scope of possible utility of the condition for group consensus is broader, beyond the clustering scenario being dealt with here. Two typical simulation instances are exhibited to exemplify the process of clustering method. As to the potential future extensions, there are several explicit major directions: (1) the method can be utilized to handle various real-world applications such as image segmentation, electrocardiosignal analysis, and classification of natural languages; (2) a further exploration toward the mechanism of group consensus or quasi-consensus could be conducted, and a more straightforward correlation between group consensus and the topological characteristics of networks might be obtained; (3) the patterns of diverse nonconsensus motions can be studied in depth.



---

*Source: 4978613-2017-09-13.xml*