# Topological Clusters in Multi-Agent Networks: Analysis and Algorithm

Jeong-Min Ma, Hyung-Gon Lee, Kevin L. Moore, Hyo-Sung Ahn, and Kwang-Kyo Oh
J.-M. Ma, H.-S. Ahn and H.-G. Lee are with School of Mechanical Engineering,
Gwangju Institute of Science and Technology, Gwangju, Republic of
Korea(e-mail<EMAIL_ADDRESS>hyosung@gist.ac.kr),
<EMAIL_ADDRESS>K.-K. Oh is with Department of Electrical
Engineering, Sunchon National University, Sunchon, Republic of Korea (e-mail:
kkoh@scnu.ac.kr).K. L. Moore is with Department of Electrical Engineering,
Colorado School of Mines, Golden, CO, USA (e-mail: kmoore@mines.edu).

###### Abstract

We study clustering properties of networks of single-integrator nodes over a
directed graph, in which the nodes converge to steady-state values. These
values define clustering groups of nodes, which depend on interaction
topology, edge weights, and initial values. Focusing on the interaction
topology of the network, we introduce the notion of topological clusters,
which are sets of nodes that converge to an identical value due to the
topological characteristics of the network, independent of the value of the
edge weights. We then investigate properties of topological clusters and
present a necessary and sufficient condition for a set of nodes to form a
topological cluster. We also provide an algorithm for finding topological
clusters. Examples show the validity of the analysis and algorithm.

###### Index Terms:

Topological clusters, multi-agent systems, consensus

##  I Introduction

Multi-agent systems have attracted a significant amount of research interest
due to their theoretical challenges and richness of applications [1, 2, 3]. In
particular, directed networks have received considerable attention [4, 5]. In
directed networks, agents often tend to aggregate into clusters depending on
factors such as the values of the network’s edge weights, node dynamics, and
the topology of network. There have been many studies of clustering behavior
[6, 7, 8, 9, 10, 11]. In [6, 7, 8], group consensus has been investigated in
directed networks with time-varying topology, communication delays, or
negative couplings. The authors of [6, 7] have provided algebraic conditions
for clustering by dividing a network into several sub-networks. In [8],
clustering behavior has been investigated for a network with some negative
couplings. The authors of [9] have studied clustering in networks with
heterogeneous node dynamics, communication delay, or negative couplings. The
authors of [10] have studied the relationship between clustering and network
topology. They have shown how the number of clusters can be determined by the
Laplacian of a directed graph. The authors of [11] have studied clustering in
networks with equal edge weights, showing that clusters correspond to cells of
what is called the almost equitable graph partition.

Identification of clusters has been studied in [11] for a network of single-
integrator nodes. The authors of [11] have presented a method to identify
clusters of a single-integrator network with equal edge weights. The method in
[11] can be extended to a network with positive edge weights. However, since
the method relies on algebraic properties of the graph Laplacian, it is
difficult to apply when edge weights are not exactly defined or change
frequently. In other words, the analysis in [11] is dependent on edge weights.
Here, we study purely topological characteristics of clustering behavior,
independent of edge weights of networks. Specifically, we introduce the notion
of topological clusters defined independently of edge weights for a network of
single-integrator nodes operating over a directed graph. Then, we present an
algorithm to identify topological clusters of the network.

We comment that the notion of topological clusters is useful for analyzing and
controlling networks when edge weights are not exactly defined or change
frequently. Further, knowledge of topological clusters can become an adequate
theoretical basis for various control problems related to cluster behavior
[12, 13, 14]. For example, the topological clusters associated with thermal
dynamics of a building can be the basis for identifying suitable input-output
pairing of sensors and actuators in a multi-zone control scheme [15]. Also,
knowledge of topological clusters in a social network can be used to analyze
the behavior of opinion dynamics and the propagation of opinions [16, 17, 18].
In addition, the notion of topological clusters can be applied to swarm
control of UAVs [19].

Consequently, the contributions of this paper can be summarized as follows:
First, we introduce the notion of topological clusters and present a necessary
and sufficient condition for a set of nodes to form a topological cluster. Our
notion of topological clusters is independent of edge weights, as opposed to
[10, 11]. That is, we always obtain the same topological clusters for any
positive edge weights. Second, we propose an algorithm to identify topological
clusters from the interaction topology of the network. The algorithm can be
applied to social networks such as DeGroot model [20]. A preliminary, and
partial, version of this algorithm is found in [21]. Finally, we validate the
proposed algorithm based on a real world example. This shows that the proposed
algorithm can be useful for analyzing real world networks.

The outline of this paper is as follows. Following preliminaries in the next
section, topological clusters are defined and their properties are
investigated in Section III. In Section IV, an algorithm for finding
topological clusters is proposed. In Section V, the proposed algorithm is
applied to some examples, including a social network, and compared with the
existing works. Concluding remarks are then provided in Section VI.

##  II Preliminaries

The set of real numbers is denoted by $\mathbb{R}$. A zero matrix is denoted
by $\mathbf{0}$. A $n$-dimensional vector with ones is denoted by
$\mathbf{1}_{n}$. The cardinality of a set $\mathcal{A}$ is denoted by
$|\mathcal{A}|$. Given two sets, $\mathcal{A}$ and $\mathcal{B}$,
$\mathcal{A}\backslash\mathcal{B}$ denotes the set of elements that are in
$\mathcal{A}$ but not in $\mathcal{B}$.

A directed graph (or graph) $\mathcal{G}=(\mathcal{V},\mathcal{E},A)$ is
defined as a triple consisting of a node set $\mathcal{V}=\\{1,\ldots,N\\}$,
an edge set $\mathcal{E}\subset\\{(i,j):i,j\in\mathcal{V},i\not=j\\}$, where
an edge is an ordered pair of distinct nodes in $\mathcal{V}$, and a weight
matrix $A=[a_{ij}]\in\mathbb{R}^{N\times N}$, which is a nonnegative matrix
such that $a_{ij}>0$ if and only if $(j,i)\in\mathcal{E}$. The weight matrix
is also called the adjacency matrix of $\mathcal{G}$. If $a_{ij}=a_{ji}$,
$\mathcal{G}$ is called undirected. If $(i,j)$ is an edge of $\mathcal{G}$,
$i$ is a parent node of $j$ and $j$ is a child node of $i$. The set of
neighbors of node $i$ in $\mathcal{G}$ is defined as
$\mathcal{N}_{i}=\\{j:(j,i)\in\mathcal{E}\\}$.

A subgraph $\mathcal{G}_{s}=(\mathcal{V}_{s},\mathcal{E}_{s})$ of
$\mathcal{G}$ is a graph such that $\mathcal{V}_{s}\subseteq\mathcal{V}$ and
$\mathcal{E}_{s}\subseteq\mathcal{E}$. If $\mathcal{V}_{s}=\mathcal{V}$,
$\mathcal{G}_{s}$ is called a spanning subgraph of $\mathcal{G}$. Similarly,
the induced subgraph is a graph whose vertex set is $\mathcal{V}_{s}$ and
whose edge set consists of all of the edges in $\mathcal{E}$ that have both
endpoints in $\mathcal{V}_{s}$. It is also said that $\mathcal{G}_{s}$ is
induced by $\mathcal{V}_{s}$. The subgraph induced by $\mathcal{V}_{s}$ is
denoted by $\mathcal{G}[\mathcal{V}_{s}]$. A tree is a graph such that every
node except for a node called the root has exactly one parent. A forest is a
graph consisting of one or more trees, no two of which have a node in common.
A spanning tree (spanning forest) of $\mathcal{G}$ is a tree (forest) that is
a spanning subgraph of $\mathcal{G}$. A path in $\mathcal{G}$ is a sequence
$i_{1},\ldots,i_{k}$ of nodes such that $(i_{s},i_{s-1})\in\mathcal{E}$ for
$s=1,\ldots,k-1$. If there is a path from $i$ to $j$, we say $j$ can be
reached from $i$. A weak path in $\mathcal{G}$ is a sequence
$i_{1},\ldots,i_{k}$ of nodes such that either $(i_{s},i_{s-1})\in\mathcal{E}$
or $(i_{s-1},i_{s})\in\mathcal{E}$ for $s=1,\ldots,k-1$. A graph $\mathcal{G}$
is strongly connected (weakly connected) if there exists a path (weak path)
from $i$ to $j$ for any distinct nodes $i,j\in\mathcal{G}$.

The Laplacian matrix $L=[l_{ij}]\in\mathbb{R}^{N\times N}$ of $\mathcal{G}$ is
defined as

$\displaystyle
l_{ij}=\left\\{\begin{array}[]{ll}\sum_{j\in\mathcal{N}_{i}}a_{ij},&i=j,\\\
-a_{ij},&(j,i)\in\mathcal{E},\\\ 0,&\mathrm{otherwise}.\end{array}\right.$ (4)

The following lemmas are useful for analyzing consensus networks:

######  Lemma II.1 ([22])

For the Laplacian matrix of a graph, the following is true:

  * •

All the eigenvalues of the Laplacian matrix have nonnegative real parts;

  * •

Zero is an eigenvalue of the Laplacian matrix with $\mathbf{1}_{N}$ as the
corresponding right eigenvector.

######  Lemma II.2 ([23, 24])

For the Laplacian matrix of a graph, zero is a simple eigenvalue if and only
if the graph has a directed spanning tree.

######  Lemma II.3 ([25])

If a graph $\mathcal{G}=(\mathcal{V},\mathcal{E},A)$ has no directed spanning
tree, its nodes can be partitioned into $\mathcal{A}$, $\mathcal{B}$, and
$\mathcal{C}$ such that

  * •

The node sets $\mathcal{A}$ and $\mathcal{B}$ are nonempty and
$\mathcal{G}[\mathcal{A}]$ is strongly connected;

  * •

No nodes in $\mathcal{A}$ and $\mathcal{B}$ have incoming edges from
$\mathcal{V}\backslash\mathcal{A}$ and $\mathcal{V}\backslash\mathcal{B}$,
respectively;

  * •

The node set $\mathcal{C}$ corresponds to
$\mathcal{V}\backslash(\mathcal{A}\cup\mathcal{B})$.

The key idea of Lemma II.3 can be summarized as follows: Let
$\mathcal{G}_{c}=(\mathcal{V}_{c},\mathcal{E}_{c})$ be the condensation of
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, which is a acyclic graph formed by
contracting strongly connected components of $\mathcal{G}$ [26]. Since
$\mathcal{G}$ has no directed spanning tree, $\mathcal{G}_{c}$ is acyclic;
thus there is $v_{\mathcal{A}}\in\mathcal{V}_{c}$ having no parent nodes. The
set $\mathcal{A}\subset\mathcal{V}$ corresponds to $v_{\mathcal{A}}$. Further
$\mathcal{C}\subset\mathcal{V}$ corresponds to the nodes that are reachable
from $v_{\mathcal{A}}$. Finally, the set
$\mathcal{B}=\mathcal{V}\backslash(\mathcal{A}\cup\mathcal{C})$ is nonempty
because $\mathcal{G}_{c}$ has no directed spanning tree. Then, no nodes in
$\mathcal{A}$ and $\mathcal{B}$ have incoming edges from
$\mathcal{V}\backslash\mathcal{A}$ and $\mathcal{V}\backslash\mathcal{B}$,
respectively. It follows from Lemma II.3 that if $\mathcal{G}$ has no directed
spanning tree, its Laplacian $L$ can be partitioned as follows:

$\displaystyle L=\left[\begin{matrix}L_{\mathcal{A}}&\mathbf{0}&\mathbf{0}\\\
\mathbf{0}&L_{\mathcal{B}}&\mathbf{0}\\\
L_{\mathcal{CA}}&L_{\mathcal{CB}}&L_{\mathcal{C}}\\\ \end{matrix}\right].$

This shows that $L_{\mathcal{A}}$ and $L_{\mathcal{B}}$ correspond to the
Laplacian matrix of induced subgraph $\mathcal{G}[\mathcal{A}]$ and
$\mathcal{G}[\mathcal{B}]$, respectively. On the other hand, $L_{\mathcal{C}}$
is not the Laplacian matrix of $\mathcal{G}[\mathcal{C}]$ because either
$L_{\mathcal{CA}}$ or $L_{\mathcal{CB}}$ is nonzero.

In this paper, we study the following diffusively coupled dynamics with
positive edge weights:

$\displaystyle\dot{x}_{i}=\sum_{j\in\mathcal{N}_{i}}a_{ij}(x_{j}-x_{i}),$ (5)

where ${x}_{i}$ is a state of node $i$ and ${a}_{ij}$ is a weight of $(j,i)$.
Without losing generality, assume that $n=1$. The node dynamics in (5) can be
written as

$\displaystyle\dot{x}=-Lx,$ (6)

where $x=[x_{1}\cdots x_{N}]^{T}$ and $L$ is the Laplacian matrix of
$\mathcal{G}$. It is said that the network (6) over $\mathcal{G}$ reaches
consensus if $x_{i}-x_{j}\to 0$ as $t\to\infty$ for any nodes $i,j$ of
$\mathcal{G}$. It is well-known that the coupled network (6) over a graph
$\mathcal{G}$ reaches consensus if and only if $\mathcal{G}$ has a directed
spanning tree.

If $\mathcal{G}$ has no directed spanning tree, the network (6) cannot reach
consensus. To discuss this, we need the concept of leader and followers. For a
graph, a node is a leader node if it has no neighbor, and a follower node if
it has at least one neighbor. Denote the set of leader nodes by $\mathcal{L}$
and the set of follower nodes by $\mathcal{F}$. The consensus protocol in (5)
can be written as follows [27]:

$\displaystyle\dot{x_{i}}$
$\displaystyle=\sum_{j\in\mathcal{N}_{i}}a_{ij}(x_{j}-x_{i}),\;i\in\mathcal{F},$
(7a) $\displaystyle\dot{x_{i}}$ $\displaystyle=0,\;i\in\mathcal{L}.$ (7b)

All the follower nodes of (7) over a graph $\mathcal{G}$ converge to the
stationary convex hull spanned by the stationary leader nodes if and only if
$\mathcal{G}$ has a directed spanning forest [27, 28].

##  III Clusters in Consensus Networks

In this section, we first review clustering behavior in single-integrator node
networks, which is dependent on edge weights. Then, we develop the notion of
topological clusters, which is independent of edge weights. Some properties of
topological clusters are also investigated.

###  III-A Clusters of networks over weighted graphs

1234567$\mathcal{H}_{1}$$\mathcal{H}_{2}$$\mathcal{C}$1111111 (a) 3 clusters

1234567$\mathcal{H}_{1}$$\mathcal{H}_{2}$$\mathcal{C}_{1}$$\mathcal{C}_{2}$1213412
(b) 4 clusters

Figure 1: Clusters of networks with identical graph topology but different
edge weights

Consider a network of single-integrator nodes over a graph. Though the network
cannot reach a consensus in the absence of a spanning tree, it can be shown
that the state of each node converges to a steady-state value. Further, some
nodes can converge to the same value to form a node group, which we call a
cluster.

For a network over a weighted graph, the authors of [11] have proposed a
method to identify clusters based on algebraic properties of the Laplacian
matrix. According to [11], the Laplacian matrix of a weighted graph can be
written as

$\bar{L}=\left[\begin{matrix}L_{1}&0&\cdots&0&0\\\ 0&L_{2}&\cdots&0&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&\cdots&L_{\mu}&0\\\
M_{1}&M_{2}&\cdots&M_{\mu}&M\\\ \end{matrix}\right]$ (8)

based on appropriate ordering of the nodes. In (8), the set of nodes related
to $L_{i}$ corresponds to a cluster for $i=1,\ldots,\mu$. The remaining
clusters formed by the nodes related to $M$ can be identified by investigating
algebraic condition of the kernel base of $\bar{L}$ as discussed in [11].

Fig. 1 shows that clusters of two networks with the same graph topology but
different edge weights, which can be obtained by using the method in [11]. In
both networks, nodes 6 and 7 are related to $M$ in (8). Depending on edge
weights, one cluster is formed by nodes 6 and 7 in Fig. 1(a) while two
clusters are formed in Fig. 1(b).

The method proposed in [11] is useful to analyze clustering behavior in
networks. However, the method requires exact information about edge weights,
which is not realistic in some cases. For instance, it is challenging to
identify the exact values of edge weights in a social network. Further, edge
weights of a network can be time-varying. This observation suggests a
necessity for an weight-independent notion of clusters, which is introduced in
the following subsection.

###  III-B Topological clusters

In this section, we introduce a new concept called topological clusters, which
are determined by purely topological connectivity, independent of the edge
weight values. These clusters only depend on topological characteristics of
networks. Fig. 2 shows examples of topological clusters. In these networks the
nodes in each cluster converge to an identical value independent of edge
weights.

135426 (a) 4 topological clusters

547138926 (b) 5 topological clusters

Figure 2: Examples of topological clusters.

To clearly characterize clustering properties due to topological
characteristics, we define topological clusters as follows:

######  Definition III.1 (Topological cluster)

For a network, a topological cluster is defined as a maximal set of nodes that
converge to an identical value independent of edge weights.

In the above definition, a topological cluster is a maximal set because it
cannot be expanded by addition of any node. That is, if a node is added to a
topological cluster, the nodes of the expanded set may not converge to an
identical value. In contrast, a topological cluster can be a part of a
cluster.

Since topological clusters are dependent only on node dynamics and interaction
topology, they can be found by analyzing the interaction topology once node
dynamics are given. The following theorem provides a necessary and sufficient
condition for topological clusters of (6):

###### Theorem III.1

For a network (6) over a digraph $\mathcal{G}=(\mathcal{V},\mathcal{E},A)$, a
subset $\mathcal{S}\subset\mathcal{V}$ is a topological cluster if and only if
$\mathcal{S}$ is a maximal set subject to the following conditions:

  1. (C1)

The induced subgraph $\mathcal{G}[\mathcal{S}]$ has at least one spanning
tree;

  2. (C2)

In $\mathcal{S}$, only one root node of $\mathcal{G}[\mathcal{S}]$ or no node
has incoming edges from $\mathcal{V}\backslash\mathcal{S}$.

###### Proof:

(Sufficiency) To prove sufficiency, we consider the following two cases: the
set $\mathcal{S}$ is a maximal set such that $\mathcal{G}[\mathcal{S}]$ has at
least one spanning tree, and either

  * •

no node in $\mathcal{S}$ has incoming edges from
$\mathcal{V}\backslash\mathcal{S}$ or

  * •

only one root node of $\mathcal{G}[\mathcal{S}]$ has incoming edges from
$\mathcal{V}\backslash\mathcal{S}$.

In the following, we show that the nodes in $\mathcal{G[S]}$ reach consensus
for each case.

We first assume that no node in $\mathcal{S}$ has incoming edges from
$\mathcal{V}\backslash\mathcal{S}$. Denote by $x_{\mathcal{S}}$ the
concatenated vector of the nodes in $\mathcal{S}$. The node dynamics can be
written as follows:

$\displaystyle\dot{x}_{\mathcal{S}}=-L_{\mathcal{S}}x_{\mathcal{S}},$

where $L_{\mathcal{S}}$ is the Laplacian matrix of the induced subgraph
$\mathcal{G}[\mathcal{S}]$. According to Lemma II.1 and II.2, since
$\mathcal{G}[\mathcal{S}]$ has at least one spanning tree, the nodes in
$\mathcal{S}$ reach consensus regardless of the edge weights.

We then consider the case where only one root node of $\mathcal{G[S]}$ has
incoming edges from $\mathcal{V}\backslash\mathcal{S}$. Let $x_{\mathcal{S}}$
and $x_{\mathcal{V}\backslash\mathcal{S}}$ denote the concatenated vector of
the nodes in $\mathcal{S}$ and $\mathcal{V}\backslash\mathcal{S}$,
respectively. Then $\dot{x}=-Lx$ can be partitioned into

$\displaystyle\left[\begin{array}[]{l}\dot{x}_{\mathcal{S}}\\\
\dot{x}_{\mathcal{V}\backslash\mathcal{S}}\\\
\end{array}\right]=-\left[\begin{matrix}L_{\mathcal{S}}&L_{\mathcal{S}-\mathcal{V}\backslash\mathcal{S}}\\\
L_{\mathcal{V}\backslash\mathcal{S}-\mathcal{S}}&L_{\mathcal{V}\backslash\mathcal{S}}\\\
\end{matrix}\right]\left[\begin{array}[]{l}x_{\mathcal{S}}\\\
x_{\mathcal{V}\backslash\mathcal{S}}\\\ \end{array}\right].$ (13)

Since $\mathcal{G}[\mathcal{S}]$ has at least one spanning tree,
$L_{\mathcal{S}}$ is invertible [28]. Further it follows that
$x_{\mathcal{S}}$ and $x_{\mathcal{V}\backslash\mathcal{S}}$ converge to
constant vectors as $t\to\infty$ [27]. Thus we obtain

$\displaystyle\mathbf{0}=L_{\mathcal{S}}x^{ss}_{\mathcal{S}}+L_{\mathcal{S}-\mathcal{V}\backslash\mathcal{S}}x^{ss}_{\mathcal{V}\backslash\mathcal{S}},$

where $x^{ss}_{\mathcal{S}}$ and $x^{ss}_{\mathcal{V}\backslash\mathcal{S}}$
denote the steady-state constant vector of the nodes in $\mathcal{S}$ and
$\mathcal{V}\backslash\mathcal{S}$, respectively. Due to the invertibility of
$L_{\mathcal{S}}$, it is obvious that $x^{ss}_{\mathcal{S}}$ is uniquely
determined for given $x^{ss}_{\mathcal{V}\backslash\mathcal{S}}$. Suppose that
$r\in\mathcal{S}$ is the root node having incoming edges from
$\mathcal{V}\backslash\mathcal{S}$. Then
$\dot{x}_{\mathcal{S}}=-L_{\mathcal{S}}x_{\mathcal{S}}-L_{\mathcal{S}-\mathcal{V}\backslash\mathcal{S}}x_{\mathcal{V}\backslash\mathcal{S}}$
can be written as

$\displaystyle\dot{x}_{i}$
$\displaystyle=\sum_{j\in\mathcal{S}}a_{ij}(x_{j}-x_{i}),\;i\in\mathcal{S},i\not=r,$
$\displaystyle\dot{x}_{r}$
$\displaystyle=\sum_{j\in\mathcal{S}}a_{rj}(x_{j}-x_{r})+\sum_{j\in\mathcal{V}\backslash\mathcal{S}}a_{rj}(x_{j}-x_{r}),$

which results in

$\displaystyle
x_{\mathcal{S}}^{ss}=\mathbf{1}_{|\mathcal{S}|}\frac{\sum_{j\in\mathcal{V}\backslash\mathcal{S}}a_{rj}x^{ss}_{j}}{\sum_{j\in\mathcal{V}\backslash\mathcal{S}}a_{rj}}.$

Hence, nodes belonging to $\mathcal{S}$ converge to an identical steady-state
value $x_{\mathcal{S}}^{ss}$ whatever edge weights are.

(Necessity) The necessity could be proved by a contraposition. Let us consider
the following three cases:

  * •

$\mathcal{G}[\mathcal{S}]$ does not have a spanning tree;

  * •

Any nodes that are not root nodes, or more than or equal to two root nodes of
$\mathcal{G}[\mathcal{S}]$ have incoming edges from
$\mathcal{V}\backslash\mathcal{S}$;

  * •

$\mathcal{S}$ is not maximal while conditions in (C1) and (C2) are satisfied.

In the following, we show that $\mathcal{S}$ is not a topological cluster for
each of the above three cases.

First, suppose that $\mathcal{G}[\mathcal{S}]$ does not have a spanning tree.
It follows from Lemma II.3 that $\mathcal{S}$ can be partitioned into
$\mathcal{S}_{1}$, $\mathcal{S}_{2}$, and $\mathcal{S}_{3}$ such that

  * •

$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ are nonempty and
$\mathcal{G}[\mathcal{S}_{1}]$ is strongly connected;

  * •

no nodes in $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ have incoming edges from
$\mathcal{S}\backslash\mathcal{S}_{1}$ and
$\mathcal{S}\backslash\mathcal{S}_{2}$, respectively;

  * •

$\mathcal{S}_{3}$ corresponds to
$\mathcal{S}\backslash(\mathcal{S}_{1}\cup\mathcal{S}_{2})$.

Based on the partitioning, $L_{\mathcal{S}}$ in (13) can be written as
follows:

$\displaystyle
L_{\mathcal{S}}=\left[\begin{matrix}L_{\mathcal{S}_{1}}&\mathbf{0}&\mathbf{0}\\\
\mathbf{0}&L_{\mathcal{S}_{2}}&\mathbf{0}\\\
L_{\mathcal{S}_{31}}&L_{\mathcal{S}_{32}}&L_{\mathcal{S}_{3}}\\\
\end{matrix}\right].$

Then it can be shown that $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ converge to
different values depending on edge weights of the network as follows:

  * •

If $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ do not have incoming edges from
$\mathcal{V}\backslash\mathcal{S}$, the steady-state values of
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ are determined independently of each
other. Thus $\mathcal{S}$ is not a topological cluster.

  * •

If only one of $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ has incoming edges from
$\mathcal{V}\backslash\mathcal{S}$, the steady-state value of the nodes in the
set is determined independently of the nodes in the other set, which means
that $\mathcal{S}$ is not a topological cluster.

  * •

Suppose that both of $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ have incoming
edges from $\mathcal{V}\backslash\mathcal{S}$.

    * –

Suppose that $\mathcal{S}_{1}$ has only a single incoming edge from a node in
$\mathcal{V}\backslash\mathcal{S}$. Since $\mathcal{S}_{1}$ is strongly
connected and has no incoming edges from
$\mathcal{S}\backslash\mathcal{S}_{1}$, $\mathcal{S}_{1}$ belongs to another
topological cluster that includes the starting node of the incoming edge. Thus
$\mathcal{S}$ is not a topological cluster.

    * –

If $\mathcal{S}_{1}$ has more than one incoming edges only from the nodes of a
topological cluster in $\mathcal{V}\backslash\mathcal{S}$, the steady-state
value of $\mathcal{S}_{1}$ is equal to that of the topological cluster in
$\mathcal{V}\backslash\mathcal{S}$. This means that $\mathcal{S}_{1}$ belongs
to the topological cluster in $\mathcal{V}\backslash\mathcal{S}$. Thus
$\mathcal{S}$ is not a topological cluster.

    * –

If $\mathcal{S}_{1}$ has more than one incoming edges from the nodes of
multiple topological clusters in $\mathcal{V}\backslash\mathcal{S}$ and
$\mathcal{S}_{2}$ also has incoming edges, the steady-state values of
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ are dependent on the weights for the
incoming edges, which means that $\mathcal{S}$ is not a topological cluster.

Second, suppose that any nodes that are not root nodes of
$\mathcal{G}[\mathcal{S}]$, or more than or equal to two root nodes of
$\mathcal{G}[\mathcal{S}]$ have incoming edges from
$\mathcal{V}\backslash\mathcal{S}$. We consider only the case where
$\mathcal{G}[\mathcal{S}]$ has at least one spanning tree because
$\mathcal{S}$ cannot be a topological cluster in the absence of spanning trees
as shown above.

Denote the set of the root nodes of $\mathcal{G}[\mathcal{S}]$ by
$\mathcal{S}_{r}$ and the set of remaining nodes by $\mathcal{S}_{f}$. Then
$\dot{x}=-Lx$ can be written as

$\displaystyle\left[\begin{array}[]{l}\dot{x}_{\mathcal{S}_{f}}\\\
\dot{x}_{\mathcal{S}_{r}}\\\ \dot{x}_{\mathcal{V}\backslash\mathcal{S}}\\\
\end{array}\right]=-\left[\begin{matrix}L_{\mathcal{S}_{f}}&L_{\mathcal{S}_{f}-\mathcal{S}_{r}}&L_{\mathcal{S}_{f}-\mathcal{V}\backslash\mathcal{S}}\\\
\mathbf{0}&L_{\mathcal{S}_{r}}&L_{\mathcal{S}_{r}-\mathcal{V}\backslash\mathcal{S}}\\\
L_{\mathcal{V}\backslash\mathcal{S}-\mathcal{S}_{r}}&L_{\mathcal{V}\backslash\mathcal{S}-\mathcal{S}_{f}}&L_{\mathcal{V}\backslash\mathcal{S}}\\\
\end{matrix}\right]\left[\begin{array}[]{l}x_{\mathcal{S}_{f}}\\\
x_{\mathcal{S}_{r}}\\\ x_{\mathcal{V}\backslash\mathcal{S}}\\\
\end{array}\right].$

Since $\mathcal{G}[\mathcal{S}]$ has at least one spanning tree,
$L_{\mathcal{S}}$ is invertible; thus $L_{\mathcal{S}_{f}}$ is also invertible
[28, Lemma 4]. Then $x_{\mathcal{S}_{f}}^{ss}$ is uniquely determined as
follows:

$\displaystyle
x_{\mathcal{S}_{f}}^{ss}=-L_{\mathcal{S}_{f}}^{-1}L_{\mathcal{S}_{f}-\mathcal{S}_{r}}x_{\mathcal{S}_{r}}^{ss}-L_{\mathcal{S}_{f}}^{-1}L_{\mathcal{S}_{f}-\mathcal{V}\backslash\mathcal{S}}x_{\mathcal{V}\backslash\mathcal{S}}^{ss}.$

Consider the case where only some nodes that are not root nodes of
$\mathcal{G}[\mathcal{S}]$ have incoming edges from
$\mathcal{V}\backslash\mathcal{S}$. The dynamics of the nodes in
$\mathcal{S}_{f}$ and $\mathcal{S}_{r}$ can be written as

$\displaystyle\dot{x}_{i}$
$\displaystyle=\sum_{j\in\mathcal{S}_{f}}a_{ij}(x_{j}-x_{i})+\sum_{j\in\mathcal{S}_{r}}a_{ij}(x_{j}-x_{i})$
$\displaystyle\quad+\sum_{j\in\mathcal{V}\backslash\mathcal{S}}a_{ij}(x_{j}-x_{i}),\;i\in\mathcal{S}_{f},$
$\displaystyle\dot{x}_{i}$
$\displaystyle=\sum_{j\in\mathcal{S}_{r}}a_{ij}(x_{j}-x_{i}),\;i\in\mathcal{S}_{r},$

Since the nodes in $\mathcal{S}_{r}$ do not have any incoming edges from
$\mathcal{V}\backslash\mathcal{S}_{r}$, they converge to the steady-state
value that is dependent on $\mathcal{G}[\mathcal{S}_{r}]$ and the initial
values. However, the steady-state values of the nodes in $\mathcal{S}_{f}$ are
dependent on $x_{\mathcal{V}\backslash\mathcal{S}}$. Therefore, the steady-
state values of the nodes in $\mathcal{S}_{r}$ and $\mathcal{S}_{f}$ cannot be
identical for arbitrary edge weights and initial values, which means that
$\mathcal{S}$ is not a topological cluster.

We next consider the case where more than or equal to two nodes have incoming
edges from $\mathcal{V}\backslash\mathcal{S}$ and at least one of them is a
root node of $\mathcal{G}[\mathcal{S}]$. We exclude the case where all
incoming edges into the nodes of $\mathcal{S}$ come out from the same
topological cluster because it makes the nodes of $\mathcal{S}$ belonging to
the other topological cluster. Let $x_{r}$ be the root node which has incoming
edges from $\mathcal{V}\backslash\mathcal{S}$, and $x_{k}$ be another node
which has incoming edges from $\mathcal{V}\backslash\mathcal{S}$. Then we have

$\displaystyle\dot{x}_{r}$
$\displaystyle=\sum_{j\in\mathcal{S}_{r}}a_{rj}(x_{j}-x_{r})+\sum_{j\in\mathcal{V}\backslash\mathcal{S}}a_{rj}(x_{j}-x_{r}),$
$\displaystyle\dot{x}_{k}$
$\displaystyle=\sum_{j\in\mathcal{S}}a_{kj}(x_{j}-x_{k})+\sum_{j\in\mathcal{V}\backslash\mathcal{S}}a_{kj}(x_{j}-x_{k}).$

Suppose that $\mathcal{S}$ is a topological cluster. Then, we have

$\displaystyle x_{r}^{ss}$
$\displaystyle=\frac{\sum_{j\in\mathcal{V}\backslash\mathcal{S}}a_{rj}x_{j}^{ss}}{\sum_{j\in\mathcal{S}_{r}}a_{rj}+\sum_{j\in\mathcal{V}\backslash\mathcal{S}}a_{rj}}$
$\displaystyle=\frac{\sum_{j\in\mathcal{V}\backslash\mathcal{S}}a_{kj}x_{j}^{ss}}{\sum_{j\in\mathcal{S}}a_{kj}+\sum_{j\in\mathcal{V}\backslash\mathcal{S}}a_{kj}}=x_{k}^{ss},$

which cannot be identically true for arbitrary edge weights. This
contradiction shows that $\mathcal{S}$ is not a topological cluster.

Finally, suppose that $\mathcal{S}$ is not maximal while conditions in (C1)
and (C2) are satisfied. It follows from the proof for sufficiency that all the
nodes of $\mathcal{S}$ converge to an identical value if conditions in (C1)
and (C2) are satisfied. Since $\mathcal{S}$ is not maximal, one can expand the
set $\mathcal{S}$ by adding at least one node in
$\mathcal{V}\backslash\mathcal{S}$ while satisfying conditions in (C1) and
(C2), which shows that $\mathcal{S}$ is not a topological cluster.

∎

###### Remark III.1

Several remarks are provided:

  * •

Though we focus on (6), the result developed in what follows can be applied to
a general network model studied in [29].

  * •

If a topological cluster in the network (6) has incoming edges from the other
topological clusters, the edges need to come out from two or more topological
clusters. If not, the maximality condition in Theorem III.1 cannot be
satisfied.

  * •

There may exist topological clusters consisting of only a single node. For
instance, a topological cluster can consist of only one leader node. Further
there may exist topological clusters consisting of only single node that has
incoming edges from two or more topological clusters. An existence of
topological clusters of a single node implies that every node belongs to a
topological cluster.

  * •

The root node of a topological cluster $\mathcal{S}$ is defined as the root
node of a spanning tree in the induced subgraph $\mathcal{G}[\mathcal{S}]$.

  * •

If a subset $\mathcal{S}$ satisfies (C1) and (C2) in Theorem III.1 but does
not satisfy the maximality condition, all nodes in $\mathcal{S}$ belong to the
same topological cluster, but $\mathcal{S}$ is not a topological cluster.

Based on the proof of Theorem III.1, topological clusters can be categorized
into two classes as follows:

######  Definition III.2 (Leader and follower topological clusters)

A topological cluster is a leader topological cluster if it has no incoming
edges coming out from the other topological clusters. On the other hand it is
called a follower topological cluster if it is not a leader topological
cluster.

The convergence value of a leader topological cluster is determined
independently of the other topological clusters. In this sense, a leader
topological cluster can be regarded as a leader in the network. In contrast, a
follower topological cluster has multiple incoming edges staring from two or
more topological clusters. As shown in the proof of Theorem III.1, the
convergence value of a follower topological cluster is determined by the
convergence values of the topological clusters from which the incoming edges
come out.

12345678910111213141516CDFBEA Figure 3: Illustration of topological clusters

We provide an example to illustrate the notion of topological clusters. Fig. 3
illustrates various types of topological clusters marked as $A,B,C,D,E$ and
$F$ . First, $A$, $B$, and $C$ are leader topological clusters. A leader
topological cluster may or may not have a leader node. For instance, $A$ has a
leader node while $B$ has not. A leader topological cluster may consist of
single node as $C$. Second, $D$, $E$, and $F$ are follower topological
clusters. As discussed in Theorem III.1 and Remark III.1, it is shown that the
induced subgraph of each follower topological cluster has at least one root
node and the corresponding spanning tree. Accordingly, we can predict the
consensus value of each topological cluster as follows:

  * •

Cluster $A$: the initial value of node 1.

  * •

Cluster $B$: the weighted sum of the initial values of nodes 5 and 6.

  * •

Cluster $C$: the initial value of node 9.

  * •

Cluster $D$: the weighted sum of the initial values of nodes $A$ and $C$.

  * •

Cluster $E$: the weighted sum of the initial values of nodes $A$ and $B$.

  * •

Cluster $F$: the weighted sum of the initial values of nodes $D$ and $E$.

##  IV Topological Clustering Algorithm

Prior to discussing the topological clustering algorithm, let us introduce
leader-like strongly connected components (LSCCs). In Fig. 3, nodes 5 and 6
are strongly connected and have no incoming edges from other parts of the
graph, except from each other. These nodes always belong to the same
topological cluster and behave like leader nodes. Based on this observation,
we define LSCC as follows:

######  Definition IV.1 (Leader-like strongly connected component)

A leader-like strongly connected component (LSCC) of a graph is a strongly
connected component that has no incoming edges from the other part of the
graph.

We next define LSCC condensation. Since all nodes in an LSCC always converge
to an identical value, it is convenient to contract the LSCC into a node when
considering topological clusters. For example, the LSCC condensation of Fig. 3
can be observed in Fig. 4. The nodes 5 and 6 in Fig. 3 are contracted onto
node 5 in Fig. 4. Based on this contraction, LSCC condensation is defined as
follows:

######  Definition IV.2 (LSCC condensation)

The LSCC condensation of a graph $\mathcal{G}$ is a graph obtained by
contracting each LSCC in $\mathcal{G}$ onto a single node.

123456789101112131415CDFBEA Figure 4: LSCC condensation of network in Fig. 3

Due to the convergence property of nodes in each LSCC, it is obvious that the
topological clusters of (6) over $\mathcal{G}$ are the same as those of the
network over the LSCC condensation of $\mathcal{G}$. Accordingly, in this
paper, it is assumed that there is no LSCCs in (6) for simplicity. Now, we are
ready to define the cluster root and cluster follower nodes as follows:

######  Definition IV.3 (Cluster root and cluster follower nodes)

For (6), a node is a cluster root (CR) node if it is a leader node or the root
node that has incoming edges from the outside of its topological cluster. A
node is a cluster follower (CF) node if it is not a CR node.

Considering Definition IV.3, it follows from the second condition of Theorem
III.1 that each topological cluster has exactly one CR node. In Fig. 4, nodes
1, 5, 8, 9, 12, and 15 are CR nodes, and there is one in each cluster.
Furthermore, all other nodes are CF nodes. The identification whether it is CR
or CF node is crucial for the topological clustering algorithm. The following
lemma shows connectivity between CR and CF nodes:

###### Lemma IV.1

For network (6), every CF node has at least one path from the CR node in its
topological cluster.

###### Proof:

Consider an arbitrary CF node. From Definition IV.3, the CF node is neither a
leader node nor the root node that has incoming edges from the outside of its
topological cluster. It follows from Theorem III.1 and Definition IV.3 that
the CF node lies on a spanning tree of the induced subgraph of a topological
cluster. Further the root node of the spanning tree is the CR node of the
topological cluster. Therefore, the CF node has at least one path from the CR
node in its topological cluster. ∎

According to the following theorem, a node with one or zero incoming edges can
be classified as a CR or CF node.

###### Theorem IV.1

For network (6) over the LSCC condensation of a digraph, the following is
true:

  * •

A node without an incoming edge is a CR node.

  * •

A node with only one incoming edge is a CF node.

###### Proof:

First, a node without an incoming edge is a leader node. It follows from
Definition IV.3 that the node is a CR node.

Second, let $i$ be a node with only one incoming edge. If $j$ is a neighbor of
$i$, it follows from the maximality condition in Theorem III.1 that both $i$
and $j$ belong to the same topological cluster. Suppose that $i$ is the CR
node of the topological cluster. Since $i$ has no incoming edge from the
outside of the topological cluster, it is a leader node, which is a
contradiction. Therefore, a node with only one incoming node is a CF node. ∎

For example, nodes 1, 5, and 8 in Fig. 4 have no incoming edges and they are
CR nodes. On the other hand, nodes 2, 4, 6, 7, 10, and 13 have only one
incoming edge and they are classified as CF nodes. However, it can be quite
challenging to classify nodes with two or more incoming edges as either CR or
CF nodes. To this end, we first define popular nodes as follows:

######  Definition IV.4 (Popular node)

For network (6), a node with two or more incoming edges is called a popular
node.

According to Definition IV.4, nodes 3, 9, 11, 12, 14, and 15 in Fig. 4 are
popular nodes. Next, to propose a theorem classifying these popular nodes, the
following lemma is necessary:

###### Lemma IV.2

For a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ that has no LSCC, every
node that is not a leader node always has at least one path from a leader
node.

###### Proof:

Consider an arbitrary node $i\in\mathcal{V}$, which is not a leader node. Let
$\mathcal{S}\subset\mathcal{V}$ be the set of all nodes that have at least one
path to the node $i$. Accordingly, $\mathcal{S}$ has no incoming edge from the
outside. We prove the lemma by contradiction. Suppose that every node in
$\mathcal{S}$ is not a leader node, which means that every node in
$\mathcal{S}$ has at least one incoming edge from the other nodes. Obviously,
the out-degree of each nodes in $\mathcal{S}$ is more than or equal to 1.
Hence, a node in $\mathcal{S}$ forms at least one directed cycle together with
some other nodes, which means that each node in $\mathcal{S}$ belongs to a
strongly connected component. Denote the strongly connected components by
$\mathcal{S}_{1},\mathcal{S}_{2},...,\mathcal{S}_{N}$. Due to the assumption
that there is no LSCC in $\mathcal{G}$, each strongly connected component has
at least one incoming edge from one of the other strongly connected
components. Applying the same argument repeatedly, it can be concluded that
some of the strongly connected components form an LSCC, which is a
contradiction. Therefore, there exists at least one leader node in
$\mathcal{S}$, which implies that node $i$ has at least one path from a leader
node.

∎

Based on Lemma IV.2, we propose a theorem that classifies the popular nodes
into CR and CF nodes.

###### Theorem IV.2

For network (6), a popular node is a CF node if and only if all acyclic paths
from any leader node to the popular node contain at least one common node
other than the popular node.

###### Proof:

(Sufficiency) Let $i$ be a popular node and assume that all acyclic paths from
a leader node to $i$ share at least one common node other than $i$. Let $j$ be
the farthest node from $i$ among the common nodes. Denote by $\mathcal{N}$ the
set of nodes contained in all acyclic paths from $j$ to $i$. If there exist
any incoming edges from the outside of $\mathcal{N}$ to nodes in $\mathcal{N}$
other than $j$, $j$ cannot be the farthest common node, which is a
contradiction. This means that only $j$ has incoming edges from the outside of
$\mathcal{N}$. Further $j$ has at least one directed path to every other node
in $\mathcal{N}$. That is, $\mathcal{N}$ satisfies the conditions (C1) and
(C2) of Theorem III.1. In general, $\mathcal{N}$ does not satisfy the
maximality condition of Theorem III.1. Yet, as discussed in Remark III.1, all
nodes in $\mathcal{N}$ belong to the same topological cluster. Assume that
node $k$ is the CR node of the topological cluster. It follows from Theorem
III.1 that there is a directed path from $k$ to every other node in
$\mathcal{N}$. Since every incoming edge from outside of the topological
cluster can be connected to only $k$, $k$ is the farthest common node of all
acyclic paths from a leader node to $i$, which implies that $k$ corresponds to
$j$. Therefore, $j$ is a CR node of the topological cluster and thus $i$ is a
CF node.

(Necessity) Let $i$ be a popular node and assume that it is a CF node. Let $j$
be the CR node of the topological cluster to which $i$ belongs. It follows
from Theorem III.1 that there exists at least one directed path from $j$ to
every other node in the topological cluster. Further only $j$ has incoming
edges starting from outside of the topological cluster. This implies that $j$
is a common node of all acyclic paths from a leader node to $i$, which
completes the proof. ∎

According to the Theorem IV.2, nodes 3, 11, and 14 in Fig. 4 are CF nodes. For
instance, node 11 has many acyclic paths from any leader node, and node 9 is a
common node in all of those paths. On the other hand, node 9, 12, and 15 in
Fig. 4 are CR nodes because they have no common node in all of those paths.

Based on the above discussions, we present the following topological
clustering algorithm, which takes the graph of network (6) and yields
information about topological clusters:

  1. 1.

Obtain LSCC condensation for given graph.

  2. 2.

Classify the nodes that have no incoming edges or exactly one incoming edge as
CR or CF node, respectively.

  3. 3.

Find all acyclic paths from a leader node to each popular node.

    1. (a)

If there exists a common node that the paths share other than the popular
node, classify the popular node as a CF node.

    2. (b)

Otherwise, classify the popular node as a CR node.

  4. 4.

Identify all topological clusters based on graph connectivity and the
classification found in the above steps.

In the above topological clustering algorithm, the LSCC condensation of
$\mathcal{G}$ can be obtained based on the existing algorithms that search
strongly connected components [30]. By checking the connectivity of each
strongly connected component with the other part of the graph, LSCC
condensation can be obtained. The pseudo-code of the topological clustering
algorithm is provided in Algorithm 1 and Algorithm 2. It is assumed that the
graph $\mathcal{G}$ has no LSCCs for simplicity. In Algorithm 1, each node is
classified into a CR or CF node. The set of each CR node and its corresponding
CF nodes is then identified as a topological cluster. This requires searching
all acyclic paths from a leader node to every popular node as implemented in
Algorithm 2. Note that Algorithm 2 is called in line 15 of Algorithm 1.

Algorithm 1 Search topological clusters

1:Input: graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$

2:Initialize $\mathcal{P}$, the set of popular nodes

3:Initialize $\mathcal{L}$, the set of leader nodes

4:for each $v$ in $\mathcal{V}$ do

5: if $v$ has no incoming edge then

6: Classify $v$ as a CR node, and add $v$ to $\mathcal{L}$

7: else if $v$ has only one incoming edge then

8: Classify $v$ as a CF node

9: else if $v$ has more than one incoming edges then

10: Add $v$ to $\mathcal{P}$

11: end if

12:end for

13:for each node $v$ in $\mathcal{P}$ do

14: Obtain $\mathcal{M}_{v}$ by calling Algorithm 2 with $v$, $\mathcal{G}$,
$\mathcal{L}$, and $\mathcal{D}_{v}=\\{v\\}$

15: if all rows of $\mathcal{M}_{v}$ share a common node other than $v$ then

16: Classify $v$ as a CF node

17: else if all rows of $\mathcal{M}_{v}$ do not share a common node other
than $v$ then

18: Classify $v$ as a CR node

19: end if

20:end for

21:Identify the set of each CR node and its corresponding CF nodes as a
topological cluster

22:Output: topological clusters

Algorithm 2 takes a popular node $v$ as input and identifies all acyclic paths
that start from a leader node and end at $v$. It returns a matrix with rows
containing the information of the acyclic paths.

Algorithm 2 Search acyclic paths

1:Input: popular node $v$, graph $\mathcal{G}$, set of leader nodes
$\mathcal{L}$, and a set $D_{v}$ for checking duplication of nodes

2:Initialize $\mathcal{M}_{v}$, matrix with paths from leader nodes to $v$ in
rows

3:for each $e$ in $\mathcal{E}$ do

4: Find a node $n$ such that $e=(v,n)\in\mathcal{E}$

5: if $n$ $\notin$ $\mathcal{D}_{v}$ then

6: if $n\in\mathcal{L}$ then

7: Append a path $v,n$ to an empty row of $\mathcal{M}_{v}$

8: else if $n\notin\mathcal{L}$ then

9: Obtain $\mathcal{M}_{n}$ by calling Algorithm 2 with $n$, $\mathcal{G}$,
$\mathcal{L}$, and $\mathcal{D}_{n}=\mathcal{D}_{v}\cup\\{n\\}$

10: Insert $v$ to the first of every row of $\mathcal{M}_{n}$

11: Append each row of $\mathcal{M}_{n}$ to the empty rows of
$\mathcal{M}_{v}$

12: end if

13: end if

14:end for

15:Output: $\mathcal{M}_{v}$

##  V Example

We now provide examples that illustrate the analysis and use of the
topological clustering algorithm.

###  V-A Comparison with state trajectory

In the first example, we identify topological clusters in the network shown in
Fig. 4, which is the LSCC condensation of the network shown in Fig. 3.
According to Algorithm 1 presented in Section IV, the set of leader nodes is
$\mathcal{L}=\\{1,5,8\\}$. Further,
$\\{2,4,6,7,10,13\\}\subset\mathcal{N}^{CF}$, where $\mathcal{N}^{CF}$ is the
set of CF nodes. Subsequently, the set of popular nodes is given as
$\mathcal{P}=\\{3,9,11,12,14,15\\}$. By Algorithm 2 and Theorem IV.2, the
popular nodes are identified as CR or CF nodes:
$\\{9,12,15\\}\subset\mathcal{N}^{CR}$,
$\\{3,11,14\\}\subset\mathcal{N}^{CF}$, where $\mathcal{N}^{CR}$ is the set of
CR nodes. The identification result is as follows:

$\displaystyle\mathcal{N}^{CR}$ $\displaystyle=\\{1,5,8,9,12,15\\},$
$\displaystyle\mathcal{N}^{CF}$ $\displaystyle=\\{2,3,4,6,7,10,11,13,14\\}$

By matching each CR node with the appropriate CF nodes, the topological
clusters are identified. The clustering result is summarized in Table I.

TABLE I: Clustering result of example A Cluster no. | CR node |  CF node
---|---|---
1 | 1 |  2, 3, 4
2 | 5 |  6, 7
3 | 8 |  -
4 | 9 |  10, 11
5 | 12 |  13, 14
6 | 15 |  -

(a) State trajectory with random edge weight set 1

(b) State trajectory with random edge weight set 2

Figure 5: State trajectories of network in example A

To validate the result in Table I, we investigate the state trajectory of the
network by simulation. For the network shown in Fig. 4, we randomly selected
initial state values of nodes between 1 and 20, and edge weights were chosen
as random positive numbers less than 5. Fig. 5 illustrates the state
trajectories for two cases. In Fig. 5(a) and Fig. 5(b), we can observe that
the nodes belong to a topological cluster converge to an identical value for
both cases.

###  V-B Comparison with existing works

123456789 Figure 6: Network topology in example B

In the second example, we compare a topological cluster and a cluster obtained
based on the method proposed in [11]. Consider a network in Fig. 6 with a
weight matrix $A=[a_{ij}]\in\mathbb{R}^{N\times N}$, where $\forall
i,j\in\mathcal{V},a_{ij}\geq 0$. To clearly illustrate the difference between
the two concepts, we randomly choose the edge weights, but make sure they
satisfy the following condition:

$\displaystyle a_{7,3}=a_{8,3}=a_{9,3}=2$ $\displaystyle
a_{7,5}=a_{8,5}=a_{9,5}=3$ $\displaystyle a_{7,6}=a_{8,6}=a_{9,6}=5$

123456789 (a) Clusters identified by method in [11]

123456789 (b) Topological clusters

Figure 7: Clusters of network in example B

Using the method proposed in [11], we can obtain the result shown in Fig.
7(a), which is dependent on the edge weights. We can obtain the topological
clusters by applying the algorithm proposed in Section IV. Different from the
result in Fig. 7(a), Fig. 7(b) shows the topological clusters which are
independent of edge weights.

###  V-C Real world example

Figure 8: Topological clusters of social network in example C Figure 9: Part
of social network and topological clusters

We apply the topological clustering algorithm to a social network found in
[31]. The social network, consisting of 185 nodes and 360 edges, shows
interaction among students in a course. Fig. 8 shows the results of the
topological clustering algorithm for the social network. Solid circles
indicate nodes, and dotted circles around nodes indicate topological clusters.
The result shown in Fig. 8 clearly identifies the relationship between the
topological clusters, which can be useful for analyzing the network.

In [31], the edge weights were set in proportion to the intensity of the
students’ interactions. The authors of [31] measured the intensity by counting
the number of online communications among the students, which seems to be
ambiguous. Further, the intensity can frequently change. The proposed
algorithm can be successfully applied to the network because the notion of the
topological clusters is not dependent on the values of edge weights.

Additionally, we can use this result to analyze the opinion propagation in the
network. If we assume that the opinion dynamics can be modeled by (6), we can
explain how the opinions propagate among the students. For example, a part of
the network are shown in Fig. 9. Nodes 4 and 50 are the CR nodes of the
corresponding topological clusters. The opinion of each node dominates that of
each cluster. Regardless of the initial values and the changes in edge
weights, nodes 63, 72, and 94 converge to the opinion of node 50. Nodes 123
and 148 converge to the opinion of node 4. Further the opinion of node 179 is
between opinions of the two topological clusters.

##  VI Conclusion

We studied clustering behavior in a network of single-integrator nodes. We
proposed the notion of topological clusters that is independent of edge
weights. We also presented a necessary and sufficient condition for
topological clusters. We then provided an algorithm to search topological
clusters. The algorithm allows us to obtain information about topological
clusters from the graph representing the interaction topology. Examples
validated the analysis and algorithm.

## References

  * [1] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” _Proceedings of the IEEE_ , vol. 95, no. 1, pp. 215–233, 2007.
  * [2] W. Ren, R. W. Beard, and E. M. Atkins, “Information consensus in multivehicle cooperative control,” _IEEE Control Systems Magazine_ , vol. 27, no. 2, pp. 71–82, 2007.
  * [3] K.-K. Oh, M.-C. Park, and H.-S. Ahn, “A survey of multi-agent formation control,” _Automatica_ , vol. 53, pp. 424–440, 2015.
  * [4] D. Mukherjee and D. Zelazo, “Robustness of consensus over weighted digraphs,” _IEEE Transactions on Network Science and Engineering_ , vol. 6, no. 4, pp. 657–670, 2019.
  * [5] Y. Shang, “Constrained consensus in state-dependent directed multiagent networks,” _IEEE Transactions on Network Science and Engineering_ , vol. 9, no. 6, pp. 4416–4425, 2022.
  * [6] J. Yu and L. Wang, “Group consensus in multi-agent systems with switching topologies and communication delays,” _Systems & Control Letters_, vol. 59, no. 6, pp. 340–348, 2010.
  * [7] ——, “Group consensus of multi-agent systems with directed information exchange,” _International Journal of Systems Science_ , vol. 43, no. 2, pp. 334–348, 2012.
  * [8] J. Qin and C. Yu, “Group consensus of multiple integrator agents under general topology,” in _52nd IEEE Conference on Decision and Control_ , 2013, pp. 2752–2757.
  * [9] W. Xia and M. Cao, “Clustering in diffusively coupled networks,” _Automatica_ , vol. 47, no. 11, pp. 2395–2405, 2011.
  * [10] J.-W. Yi, Y.-W. Wang, and J.-W. Xiao, “Reaching cluster consensus in multi-agent systems,” in _2011 2nd International Conference on Intelligent Control and Information Processing_ , vol. 2. IEEE, 2011, pp. 569–573.
  * [11] S. Monaco and L. Ricciardi Celsi, “On multi-consensus and almost equitable graph partitions,” _Automatica_ , vol. 103, pp. 53–61, 2019.
  * [12] F. Cacace, M. Mattioni, S. Monaco, and L. Ricciardi Celsi, “Topology-induced containment for general linear systems on weakly connected digraphs,” _Automatica_ , vol. 131, p. 109734, 2021.
  * [13] V. T. Pham, N. Messai, and N. Manamanni, “Impulsive observer-based control in clustered networks of linear multi-agent systems,” _IEEE Transactions on Network Science and Engineering_ , vol. 7, no. 3, pp. 1840–1851, 2020.
  * [14] X.-G. Guo, P.-M. Liu, J.-L. Wang, and C. K. Ahn, “Event-triggered adaptive fault-tolerant pinning control for cluster consensus of heterogeneous nonlinear multi-agent systems under aperiodic dos attacks,” _IEEE Transactions on Network Science and Engineering_ , vol. 8, no. 2, pp. 1941–1956, 2021.
  * [15] T. G. Nikolaou, D. S. Kolokotsa, G. S. Stavrakakis, and I. D. Skias, “On the application of clustering techniques for office buildings’ energy and thermal comfort classification,” _IEEE Transactions on Smart Grid_ , vol. 3, no. 4, pp. 2196–2210, 2012.
  * [16] V. D. Blondel, J. M. Hendrickx, and J. N. Tsitsiklis, “Continuous-time average-preserving opinion dynamics with opinion-dependent communications,” _SIAM Journal on Control and Optimization_ , vol. 48, no. 8, pp. 5214–5240, 2010.
  * [17] M. Mäs, A. Flache, and D. Helbing, “Individualization as driving force of clustering phenomena in humans,” _PLOS Computational Biology_ , vol. 6, no. 10, pp. 1–8, 10 2010.
  * [18] F. Dietrich, S. Martin, and M. Jungers, “Control via leadership of opinion dynamics with state and time-dependent interactions,” _IEEE Transactions on Automatic Control_ , vol. 63, no. 4, pp. 1200–1207, 2018.
  * [19] Z. A. Ali, Z. Han, and R. J. Masood, “Collective motion and self-organization of a swarm of uavs: A cluster-based architecture,” _Sensors_ , vol. 21, no. 11, 2021.
  * [20] M. H. DeGroot, “Reaching a consensus,” _Journal of the American Statistical association_ , vol. 69, no. 345, pp. 118–121, 1974.
  * [21] J.-M. Ma, H.-G. Lee, H.-S. Ahn, and K. L. Moore, “Clusters in multi-leader directed consensus networks,” in _2020 20th International Conference on Control, Automation and Systems (ICCAS)_ , 2020, pp. 379–384.
  * [22] C. Godsil and G. F. Royle, _Algebraic graph theory_. Springer Science & Business Media, 2001, vol. 207.
  * [23] Z. Lin, B. Francis, and M. Maggiore, “Necessary and sufficient graphical conditions for formation control of unicycles,” _IEEE Transactions on Automatic Control_ , vol. 50, no. 1, pp. 121–127, 2005.
  * [24] W. Ren and R. Beard, “Consensus seeking in multiagent systems under dynamically changing interaction topologies,” _IEEE Transactions on Automatic Control_ , vol. 50, no. 5, pp. 655–661, 2005.
  * [25] N. M. D. Niezink, “Consensus in networked multi-agent systems,” Master’s thesis, University of Groningen, Groningen, Netherlands, 2011.
  * [26] F. Bullo, _Lectures on network systems_. Kindle Direct Publishing, 2020.
  * [27] Y. Cao and W. Ren, “Containment control with multiple stationary or dynamic leaders under a directed interaction graph,” in _Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference_ , 2009, pp. 3014–3019.
  * [28] H. Liu, G. Xie, and L. Wang, “Necessary and sufficient conditions for containment control of networked multi-agent systems,” _Automatica_ , vol. 48, no. 7, pp. 1415–1422, 2012.
  * [29] P. Wieland, R. Sepulchre, and F. Allgöwer, “An internal model principle is necessary and sufficient for linear output synchronization,” _Automatica_ , vol. 47, no. 5, pp. 1068–1074, 2011.
  * [30] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, _Introduction to algorithms_. MIT press, 2009.
  * [31] M. Fire, G. Katz, Y. Elovici, B. Shapira, and L. Rokach, “Predicting student exam’s scores by analyzing social network data,” in _Proceedings of the 8th International Conference on Active Media Technology_. Berlin, Heidelberg: Springer-Verlag, 2012, p. 584–595.