# Distributed Finite Time $k$-means Clustering
with Quantized Communucation and Transmission Stopping

Apostolos I. Rikos, Gabriele Oliva, Christoforos N. Hadjicostis, and Karl H.
Johansson Apostolos I. Rikos and K. H. Johansson are with the Division of
Decision and Control Systems, KTH Royal Institute of Technology, SE-100 44
Stockholm, Sweden. E-mails<EMAIL_ADDRESS>Oliva is with the
Unit of Automatic Control, Department of Engineering, Università Campus Bio-
Medico di Roma, via Álvaro del Portillo 21, 00128, Rome, Italy. E-mail:
<EMAIL_ADDRESS>N. Hadjicostis is with the Department of Electrical
and Computer Engineering, University of Cyprus, 1678 Nicosia, Cyprus. E-mail:
<EMAIL_ADDRESS>
###### Abstract

In this paper, we present a distributed algorithm which implements the
$k$-means algorithm in a distributed fashion for multi-agent systems with
directed communication links. The goal of $k$-means is to partition the
network’s agents in mutually exclusive sets (groups) such that agents in the
same set have (and possibly share) similar information and are able to
calculate a representative value for their group. During the operation of our
distributed algorithm, each node (i) transmits quantized values in an event-
driven fashion, and (ii) exhibits distributed stopping capabilities.
Transmitting quantized values leads to more efficient usage of the available
bandwidth and reduces the communication bottleneck. Also, in order to preserve
available resources, nodes are able to distributively determine whether they
can terminate the operation of the proposed algorithm. We characterize the
properties of the proposed distributed algorithm and show that its execution
(on any static and strongly connected digraph) will partition all agents to
mutually exclusive clusters in finite time. We conclude with examples that
illustrate the operation, performance, and potential advantages of the
proposed algorithm.

###### Index Terms:

Clustering, $k$-means optimization, distributed algorithms, quantization,
event-triggered, finite-time termination.

##  I Introduction

Data Clustering is a fundamental problem whereby data is clustered in groups
and a representative value is identified for each group. Such methods are
adopted in a broad variety of different applications, ranging from customer
segmentation [1] to cybersecurity [2]. Notably, in the case of wireless sensor
networks, a large amount of data is typically generated or sensed [3]. In this
view, the ability of a set of agents to collectively cluster their sensed data
would allow to contain the overall amount of information and to establish
functional connections among the agents, e.g., by identifying other agents
with similar values.

In the literature, there have been various works at distributing clustering
(e.g., see [4, 5] and references therein) and recently on distributed
algorithms such as the $k$-means [6, 7, 8] and the C-means [9]. However, most
clustering algorithms feature a message exchanges consisting of floating point
values. This leads to a significant increase in the computational and
bandwidth requirements and may be responsible for introducing quantization
errors or approximations.

Main Contributions. In this paper, we aim to analyze the distributed $k$-means
clustering problem while we reduce the communication bottleneck between nodes.
Specifically, we focus on the realistic scenario where nodes communicate with
quantized messages and we present a distributed algorithm which operates in an
event-triggered fashion and converges in finite time. Furthermore, in order to
preserve available resources, nodes are able to determine whether the
algorithm converged so as to terminate their operation. The main contributions
of our paper are the following.

  * $\bullet$

We present a novel distributed algorithm for solving the $k$-means clustering
problem. The algorithm allows nodes to calculate in a distributed fashion a
set of centroids that minimize the sum of squares within every cluster. During
its operation, nodes exchange quantized messages of finite length with their
neighboring nodes. We show that our proposed algorithm converges in a
deterministic manner after a finite number of time steps, and calculates the
exact result (represented as the ratio of two quantized values) without
introducing any final error (e.g., due to quantization or due to asymptotic
convergence). Furthermore, the algorithm’s operation relies on (i) calculating
the average of the observations of every cluster, and (ii) utilizing a
distributed stopping strategy to determine whether convergence has been
achieved and thus terminate the operation. For this reason, we present (i) a
novel algorithm for quantized average consensus for the case where each node’s
initial state is a vector (see Algorithm 1), and (ii) a novel distributed
stopping mechanism in order to terminate the operation of the proposed
algorithm in a finite number of time steps (and hence solve the $k$-means
clustering problem in finite time). Note that to the authors knowledge, this
is the first algorithm for solving the $k$-means clustering problem in a fully
distributed manner for the case where the operation of the nodes relies on
quantized communication; see Algorithm 2.

  * $\bullet$

We calculate a deterministic upper bound on the required time steps for the
convergence of our algorithm. Our bound depends on the network structure and
the number of centroid calculations; see Theorem 2.

  * $\bullet$

We demonstrate the operation of our algorithm via various simulations.
Furthermore, we compare our algorithm’s performance against other $k$-means
clustering algorithms; see Section VI.

The operation of our proposed algorithm relies on consecutive executions of a
quantized average consensus algorithm along with a distributed stopping
mechanism. More specifically, initially each node assigns its observation to
the cluster characterized by the nearest centroid. It executes a quantized
average consensus algorithm to calculate the new centroid values. Then, it
utilizes a distributed stopping mechanism in order to determine whether the
new centroid values have been calculated. This allows our algorithm to
calculate the optimal centroid values in finite time. Furthermore, the state
of each node is represented as a fraction of two quantized values. This
characteristic allows each node to calculate the exact value of each centroid
without any error. As a result, the proposed algorithm is able to calculate
the exact local optimal solution of the $k$-means clustering problem.

The current literature comprises of centralized or distributed algorithms
whose operation with real values increases bandwidth and processing
requirements and leads to approximate solutions. Our paper is a major
departure from the current literature since the operation of each node relies
on quantized communication. Utilization of quantized values allows more
efficient usage of network resources, and leads to calculation in finite time
of the exact solution without any error. Therefore, our proposed distributed
algorithm introduces a novel approach for data clustering with efficient
(quantized) communication.

##  II Mathematical Notation

Graph Theoretic Notions.  The sets of real, rational, and integer numbers are
denoted by $\mathds{R},\mathds{Q}$, and $\mathds{Z}$, respectively. The symbol
$\mathds{Z}_{\geq 0}$ ($\mathds{Z}_{>0}$) denotes the set of nonnegative
(positive) integer numbers. The set $\mathds{Z}_{\leq 0}$ ($\mathds{Z}_{<0}$)
denotes the set of nonpositive (negative) integer numbers. For any real number
$a\in\mathds{R}$, $\lfloor a\rfloor$ denotes the greatest integer less than or
equal to $a$ (i.e., the floor of $a$), and $\lceil a\rceil$ denotes the least
integer greater than or equal to $a$ (i.e., the ceiling of $a$). Vectors are
denoted by small letters, and matrices are denoted by capital letters. The
transpose of matrix $A$ is denoted by $A^{T}$. For matrix
$A\in\mathds{R}^{n\times n}$, $A_{(ij)}$ denotes the entry at row $i$ and
column $j$. For a vector $a\in\mathds{R}^{n}$, $a_{(i)}$ denotes the entry at
position $i$. The all-ones vector is denoted as $\mathbf{1}$ and the identity
matrix is denoted as $I$ (of appropriate dimensions).

Let us consider a network of $n$ nodes ($n>2$) where each node can communicate
only with its immediate neighbors. The communication topology is captured by a
directed graph (digraph) defined as
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$. In digraph $\mathcal{G}_{d}$,
$\mathcal{V}=\\{v_{1},v_{2},\dots,v_{n}\\}$ is the set of nodes with
cardinality $n=|\mathcal{V}|\geq 2$, and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}-\\{(v_{j},v_{j})\ |\
v_{j}\in\mathcal{V}\\}$ is the set of edges (self-edges excluded) with
cardinality $m=|\mathcal{E}|$. A directed edge from node $v_{i}$ to node
$v_{j}$ is denoted by $m_{ji}\triangleq(v_{j},v_{i})\in\mathcal{E}$, and
captures the fact that node $v_{j}$ can receive information from node $v_{i}$
(but not the other way around). We assume that the given digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ is strongly connected. This means
that for each pair of nodes $v_{j},v_{i}\in\mathcal{V}$, $v_{j}\neq v_{i}$,
there exists a directed path111A directed path from $v_{i}$ to $v_{j}$ exists
if we can find a sequence of nodes $v_{i}\equiv
v_{l_{0}},v_{l_{1}},\dots,v_{l_{t}}\equiv v_{j}$ such that
$(v_{l_{\tau+1}},v_{l_{\tau}})\in\mathcal{E}$ for $\tau=0,1,\dots,t-1$. from
$v_{i}$ to $v_{j}$. The diameter $D$ of a digraph is the longest shortest path
between any two nodes $v_{j},v_{i}\in\mathcal{V}$. The subset of nodes that
can directly transmit information to node $v_{j}$ is called the set of in-
neighbors of $v_{j}$ and is represented by
$\mathcal{N}_{j}^{-}=\\{v_{i}\in\mathcal{V}\;|\;(v_{j},v_{i})\in\mathcal{E}\\}$.
The cardinality of $\mathcal{N}_{j}^{-}$ is called the in-degree of $v_{j}$
and is denoted by $\mathcal{D}_{j}^{-}$. The subset of nodes that can directly
receive information from node $v_{j}$ is called the set of out-neighbors of
$v_{j}$ and is represented by
$\mathcal{N}_{j}^{+}=\\{v_{l}\in\mathcal{V}\;|\;(v_{l},v_{j})\in\mathcal{E}\\}$.
The cardinality of $\mathcal{N}_{j}^{+}$ is called the out-degree of $v_{j}$
and is denoted by $\mathcal{D}_{j}^{+}$.

Node Operation. We assume that each node $v_{j}$ can directly transmit
messages to each out-neighbor; however, it cannot necessarily receive messages
(at least not directly) from them. In the proposed distributed algorithm, each
node $v_{j}$ assigns a unique order in the set
$\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$ to each of its outgoing edges $m_{lj}$,
where $v_{l}\in\mathcal{N}^{+}_{j}$. More specifically, the order of link
$(v_{l},v_{j})$ for node $v_{j}$ is denoted by $P_{lj}$ (such that
$\\{P_{lj}\;|\;v_{l}\in\mathcal{N}^{+}_{j}\\}=\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$).
This unique predetermined order is used during the execution of the proposed
algorithm as a way of allowing node $v_{j}$ to transmit messages to its out-
neighbors in a round-robin222When executing the deterministic protocol, each
node $v_{j}$ transmits to its out-neighbors, one at a time, by following the
predetermined order. The next time it transmits to an out-neighbor, it
continues from the outgoing edge it stopped the previous time and cycles
through the edges in a round-robin fashion. fashion.

##  III Preliminaries on Distributed Coordination

The distributed $\max$-consensus algorithm calculates the maximum value of the
network in a finite number of time steps [10]. The intuition of the algorithm
is the following: every node $v_{j}$ in the network, performs the following
update rule:

$\displaystyle
x_{j}[\mu+1]=\max_{v_{i}\in\mathcal{N}_{j}^{-}\cup\\{v_{j}\\}}\\{x_{i}[\mu]\\}.$
(1)

The $\max$-consensus algorithm converges to the maximum value among all nodes
in a finite number of steps $s$, where $s\leq D$ (see, e.g., [11, Theorem
5.4]). Note here that similar results hold also for the $\min$-consensus
algorithm.

##  IV Problem Formulation

###  IV-A $k$-means Clustering

The problem we present in this paper is borrowed from [6], but is adjusted in
the context of quantized communication over directed networks. Specifically,
let us consider a set of $n$ observations $x_{1},\ldots,x_{n}$, where
$x_{i}\in\mathds{R}^{d}$ for $i\in\\{1,2,...,n\\}$. Each observation $x_{i}$
is assigned to each node $v_{i}$, respectively. In the $k$-means clustering
problem, we want to partition the $n$ observations into $k$ sets (where $k\leq
n$) or clusters $\mathcal{C}=\\{C_{1},\ldots,C_{k}\\}$ so we can minimize the
sum of squares within every cluster. Specifically, we want to find a set of
centroids $\textbf{c}_{1},\ldots,\textbf{c}_{k}$ (where
$\textbf{c}_{\gamma}\in\mathds{R}^{d}$, for $\gamma\in\\{1,2,...,k\\}$), each
associated to a cluster, which solve the following optimization problem:

$\displaystyle\mathcal{D}$
$\displaystyle=\operatorname*{arg\,min}_{C}\sum_{i=1}^{k}\sum_{j=1}^{n}r_{ij}||x_{j}-\textbf{c}_{i}||^{2},$
(2) $\displaystyle\text{s.t.}\ \ \sum_{i=1}^{k}r_{ij}=1,\ \text{for all}\
j=1,2,...n\ \text{and}$ (3) $\displaystyle r_{ij}\in\\{0,1\\},$ (4)

where $r_{ij}\in\mathds{Z}_{\geq 0}^{n\times k}$. Note here that $r_{ij}=1$,
means that node $v_{j}$ belongs in cluster $C_{i}$ ($r_{ij}=0$ otherwise).

The problem in (2) is hard to solve exactly when $n$ and $k$ are large333The
problem is NP-hard in general Euclidean space $\mathds{R}^{d}$, even for $2$
clusters [12] and for a general number of clusters $k$, even in the plane
[13]., thus calling for approximate solutions. In particular, the $k$-means
algorithm represents a successful strategy to compute a local optimal solution
to the above problem. The intuition of the $k$-means algorithm is that it
starts with a random set of $k$ centroids
$\textbf{c}_{1}(1),\ldots,\textbf{c}_{k}(1)$, and alternates at each step
between an assignment and a refinement phase.

Assignment phase: Each observation $x_{\lambda}$ is assigned to the set
characterized by the nearest centroid, i.e.:

$C_{i}(T)=\\{x_{\lambda}:||x_{\lambda}-\textbf{c}_{i}||^{2}\leq||x_{\lambda}-\textbf{c}_{j}||^{2},\
i,j\in[1,k]\\}$ (5)

Refinement phase: Each centroid $\textbf{c}_{i}(T+1)$ is updated as:

$\textbf{c}_{i}(T+1)=\frac{\sum_{v_{j}\in C_{i}(T)}x_{j}}{|C_{i}(T)|}$ (6)

The two steps are iterated until convergence (i.e., if the centroids no longer
change) or up to a maximum of $M$ iterations.

Figure 1: Example of execution of $k$-means algorithm (source; Wikipedia
Commons available under GNU Free Documentation License v. 1.2).

Fig. 1 is an example of execution of the algorithm for a set of $n=12$
observations in $\mathds{R}^{2}$ and for $k=3$. Fig. 1 (a) shows with circles
the initial centroids. Fig. 1 (b) and Fig. 1 (c) report the assignment and
refinement phases for the first step. Fig. 1 (d) depicts the assignment phase
for the second step.

The $k$-means algorithm is known to converge to a local optimum value, while
there is no guarantee to converge to the global optimum [14]. However, given
the complexity of the problem at hand, the $k$-means algorithm is de facto the
most diffused heuristic algorithm: indeed “ease of implementation, simplicity,
efficiency, and empirical success are the main reasons for its popularity”
[15]. Furthermore, note that the convergence of the algorithm strongly depends
on the initial choice of the centroids. Therefore, a common practice is to
execute the algorithm several times – each time with different initial
conditions – and select the best solution.

###  IV-B Modification of $k$-means Clustering Problem: Finite Time $k$-means
Clustering with Quantized Communication

In this paper, we develop a distributed algorithm that allows nodes to find a
locally optimal solution to the problem P1 presented below, while transmitting
quantized information via available communication links.

P1. Consider a static strongly connected digraph $\mathcal{G}_{d}$, where each
node $v_{j}$ is endowed with a quantized state $x_{j}\in\mathds{R}^{d}$. We
aim at developing a distributed algorithm which calculates in a distributed
fashion a set of centroids $\textbf{c}_{1},\ldots,\textbf{c}_{k}$ (where
$\textbf{c}_{\gamma}\in\mathds{R}^{d}$, for $\gamma\in\\{1,2,...,k\\}$) and
association variables $r_{ij}$, which represent a locally optimal solution to
the following optimization problem:

$\displaystyle\mathcal{D}$
$\displaystyle=\operatorname*{arg\,min}_{C}\sum_{i=1}^{k}\sum_{j=1}^{n}r_{ij}||x_{j}-\textbf{c}_{i}||^{2},$
(7) $\displaystyle\text{s.t.}\ \ \sum_{i=1}^{k}r_{ij}=1,\ \text{for all}\
j=1,2,...n\ $ (8) $\displaystyle r_{ij}\in\\{0,1\\},$ (9)

where $r_{ij}\in\mathds{Z}_{\geq 0}^{n\times k}$. During the proposed
algorithm each node transmits quantized information. The proposed algorithm
converges in a finite number of time steps, upper bounded by a polynomial
function which depends on the communication network. Each node ceases
transmissions once convergence has been achieved.

##  V Finite Time $k$-means Clustering with Quantized Communication

In this section we propose a distributed algorithm which solves problem P1 in
Section IV-B. We first present an extended version of the algorithm in [16]
which is important for our subsequent development.

###  V-A Multidimensional Deterministic Exact Quantized Average Consensus

In this section, we present an extended version of the deterministic algorithm
in [16]. In this version, each node is able to calculate the exact average of
the initial states in a deterministic fashion after a finite number of time
steps for the case where the state of each node is an integer vector (i.e.,
$y_{j}[\mu]\in\mathds{Z}^{d}$, where $\mu,d\in\mathds{Z}_{>0}$). The proposed
algorithm is detailed as Algorithm 1 below.

Algorithm 1 Multidimensional Deterministic Exact Quantized Average Consensus
Algorithm

Input: A strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ with $n=|\mathcal{V}|$ nodes and
$m=|\mathcal{E}|$ edges. Each node $v_{j}\in\mathcal{V}$ has an initial
quantized state $y_{j}[1]\in\mathds{Z}^{d}$.
Initialization: Every node $v_{j}\in\mathcal{V}$ does the following:

  * $\bullet$

assigns to each of its outgoing edges $v_{l}\in\mathcal{N}^{+}_{j}$ a unique
order $P_{lj}$ in the set $\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$;

  * $\bullet$

sets $tr^{(j)}=0$ and $e=tr^{(j)}$;

  * $\bullet$

sets $z_{j}[1]=1$, $z^{s}_{j}[1]=z_{j}[1]$ and $y^{s}_{j}[1]=y_{j}[1]$ (which
means that $q^{s}_{j}[1]=y^{s}_{j}[1]/z^{s}_{j}[1]$);

  * $\bullet$

chooses out-neighbor $v_{l}\in\mathcal{N}_{j}^{+}$ according to the
predetermined order $P_{lj}$ (initially, it chooses
$v_{l}\in\mathcal{N}_{j}^{+}$ such that $P_{lj}=0$) and transmits $z_{j}[1]$
and $y_{j}[1]$ to this out-neighbor. Then, it sets $y_{j}[1]=0$, $z_{j}[1]=0$,
$\text{pass}_{j}=0$;

  * $\bullet$

sets $tr^{(j)}=tr^{(j)}+1$ and $e=tr^{(j)}\mod\mathcal{D}^{+}_{j}$;

Iteration: For $\mu=1,2,\dots$, each node $v_{j}\in\mathcal{V}$, does the
following:

  * $\bullet$

receives $y_{i}[\mu]$ and $z_{i}[\mu]$ from its in-neighbors
$v_{i}\in\mathcal{N}_{j}^{-}$ and sets

$y_{j}[\mu+1]=y_{j}[\mu]+\sum_{v_{i}\in\mathcal{N}_{j}^{-}}w_{ji}[\mu]y_{i}[\mu],$

and

$z_{j}[\mu+1]=z_{j}[\mu]+\sum_{v_{i}\in\mathcal{N}_{j}^{-}}w_{ji}[\mu]z_{i}[\mu],$

where $w_{ji}[\mu]=0$ if no message is received (otherwise $w_{ji}[\mu]=1$);

  * $\bullet$

sets $\text{pass}_{j}=1$, sets $\text{dim}_{j}=1$;

  * $\bullet$

Event Trigger Conditions: while $\text{dim}_{j}\leq d$ then
C$1$: if $z_{j}[\mu+1]>z^{s}_{j}[\mu]$ break;
C$2$: if $z_{j}[\mu+1]<z^{s}_{j}[\mu]$ sets $\text{dim}_{j}=0$, break;
C$3$: if $z_{j}[\mu+1]=z^{s}_{j}[\mu]$ and
$y_{j(\text{dim}_{j})}[\mu+1]>y^{s}_{j(\text{dim}_{j})}[\mu]$ break;
C$4$: if $z_{j}[\mu+1]=z^{s}_{j}[\mu]$ and
$y_{j(\text{dim}_{j})}[\mu+1]=y^{s}_{j(\text{dim}_{j})}[\mu]$ sets
$\text{dim}_{j}=\text{dim}_{j}+1$;
C$5$: if $z_{j}[\mu+1]=z^{s}_{j}[\mu]$ and
$y_{j(\text{dim}_{j})}[\mu+1]<y^{s}_{j(\text{dim}_{j})}[\mu]$ sets
$\text{dim}_{j}=0$, break;

  * $\bullet$

if $\text{pass}_{j}=1$:

    * $\bullet$

sets $z^{s}_{j}[\mu+1]=z_{j}[\mu+1]$, $y^{s}_{j}[\mu+1]=y_{j}[\mu+1]$,

$q^{s}_{j}[\mu+1]=\frac{y^{s}_{j}[\mu+1]}{z^{s}_{j}[\mu+1]}.$

    * $\bullet$

transmits $z_{j}[\mu+1]$ and $y_{j}[\mu+1]$ towards out-neighbor
$v_{\lambda}\in\mathcal{N}_{j}^{+}$ for which $P_{\lambda j}=e$ and it sets
$y_{j}[\mu+1]=0$ and $z_{j}[\mu+1]=0$. Then it sets $tr^{(j)}=tr^{(j)}+1$ and
$e=tr^{(j)}\mod\mathcal{D}^{+}_{j}$.

Output: (10) holds for every $v_{j}\in\mathcal{V}$.

The intuition of Algorithm 1 is the following. Each node $v_{j}$ receives the
mass variables $y_{i}[k]$ and $z_{i}[k]$ from its in-neighbors
$v_{i}\in\mathcal{N}_{j}^{-}$ and sums them along with its stored mass
variables ($y_{j}[k]$ and $z_{j}[k]$). During the event-triggered conditions
C$1$ \- C$5$, node $v_{j}$ compares each element of the received vectors
against its stored vectors. According to the event-triggered conditions, it
decides whether it will update its state variables and will perform
transmission towards one of its out-neighbors. If it performs a transmission,
it sets its stored mass variables equal to zero and repeats the procedure.

######  Definition 1.

The system is able to achieve exact quantized average consensus in the form of
a quantized fraction if, for every $v_{j}\in\mathcal{V}$, there exists
$\mu_{0}\in\mathds{Z}_{+}$ so that for every $v_{j}\in\mathcal{V}$ we have

$q^{s}_{j}[\mu]=\frac{\sum_{l=1}^{n}{y_{l}[0]}}{n},$ (10)

for $\mu\geq\mu_{0}$, where $q$ is the real average of the initial states
defined as

$q=\frac{\sum_{l=1}^{n}{y_{l}[0]}}{n}.$ (11)

Let us now consider the following setup.

Setup $1$: Consider a strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ with $n=|\mathcal{V}|$ nodes and
$m=|\mathcal{E}|$ edges. Each node $v_{j}\in\mathcal{V}$ has an initial
quantized state $y_{j}[0]\in\mathds{Z}^{d}$. During the execution of the
Algorithm 1, at time step $\mu_{1}$, there is at least one node
$v_{j^{\prime}}\in\mathcal{V}$, for which

$z_{j^{\prime}}[\mu_{1}]\geq z_{i}[\mu_{1}],\ \forall v_{i}\in\mathcal{V}.$
(12)

Then, among the nodes $v_{j^{\prime}}$ for which (12) holds, there is at least
one node $v_{j}$ for which

$y_{j(\text{dim}_{j})}[\mu_{1}]\geq y_{j^{\prime}(\text{dim}_{j})}[\mu_{1}],\
v_{j},v_{j^{\prime}}\in\\{v_{i}\in\mathcal{V}\ |\
(\ref{great_z_prop1_det_multi})\ \text{holds}\\},$ (13)

for every $\text{dim}_{j}\in\\{1,2,...,d\\}$. For notational convenience we
will call the mass variables of node $v_{j}$ for which (12) and (13) hold as
the “leading mass” (or “leading masses”).

In the following theorem we present the deterministic convergence of Algorithm
1. The proof of the theorem is similar to Proposition $1$ in [16] and is
omitted.

######  Theorem 1.

Under Setup $1$ we have that the execution of Algorithm 1 allows each node
$v_{j}\in\mathcal{V}$ to reach quantized average consensus after a finite
number of steps $\mathcal{S}_{t}$, bounded by $\mathcal{S}_{t}\leq nm^{2}$.

######  Remark 1.

For developing our results in this paper, we rely on the operation of
Algorithm 1. As mentioned previously, this algorithm allows deterministic
convergence after a finite number of time steps as shown in Theorem 1. Please
note that we can also rely on the operation of the algorithm in [17] for
developing our results. The operation of [17] is simpler compared to Algorithm
1. However, [17] does not exhibit deterministic convergence but rather
converges with high probability to the exact real average $q$ in (11) after a
finite number of time steps.

###  V-B Finite Time $k$-means Clustering Algorithm with Quantized
Communication

We now present a distributed algorithm which solves Problem P1 presented in
Section IV-B. The proposed algorithm is detailed as Algorithm 2 below and
allows each node in the network to calculate, while processing and
transmitting quantized messages, in a finite number of time steps, a set of
centroids $\textbf{c}_{1},\ldots,\textbf{c}_{k}$, each associated to a
cluster, which fulfill (7). Furthermore, each node is able to determine
whether convergence has been achieved and proceed to cease transmissions. To
solve the $k$-means clustering problem, we make the following two assumptions
which are necessary for the operation of Algorithm 2.

######  Assumption 1.

Every node $v_{j}\in\mathcal{V}$ knows the diameter of the network $D$ (or an
upper bound $D^{\prime}$).

######  Assumption 2.

Each node $v_{j}$ knows the initial set of centroids
$C[0]=[\textbf{c}_{1}[0],\textbf{c}_{2}[0],...,\textbf{c}_{k}[0]]\in\mathds{R}^{d\times
k}$ ($k<n$).

Assumption 1 is a necessary condition for the $\min$\- and $\max$-consensus
algorithm, so that each node $v_{j}$ is able to determine whether convergence
has been achieved and thus our proposed algorithm can terminate. Note,
however, that this assumption can be relaxed if we utilize the distributed
algorithm in [18] instead of Algorithm 1. The algorithm in [18] converges to
the exact real average in finite time without requiring knowledge of the
network diameter $D$. Assumption 2 is a necessary condition so that each node
can calculate the updated value of the centroids without having to communicate
their real values to other nodes (because communication is restricted to
quantized values).

######  Remark 2.

Regarding Assumption 2, previous work in [6] ensures that one node is elected
as the leader node and propagates the real values of the centroids to every
node. Note that in our case, nodes communicate by exchanging quantized values.
Therefore, each node needs to know the initial set of centroids in order to
calculate their updated values without the need of a leader node (which
transmits the updated value of the centroids to every node in the network).
When the initial set of centroids is known only to a certain leader node, then
the leader node can propagate the set of centroids to every node if the
initial set of centroids are quantized values. Thus, after $D$ time steps,
every node in the network will know the initial centroids and Assumption 2
will be fulfilled.

We now describe the main operations of Algorithm 2. The initialization
involves the following steps:

Initialization. Centroid Selection and Unique Order: Each node
$v_{j}\in\mathcal{V}$ has a quantized state $x_{j}\in\mathds{Z}^{d}$. Then, it
assigns to each of its outgoing edges a unique order.

The iteration involves the following steps:

Iteration - Step $1$. Cluster Assignment and Labeled Multidimensional
Deterministic Exact Quantized Average Consensus: At each step $\mu$, each node
$v_{j}$ assigns its value $x_{j}$ to the nearest centroid according to (5)
(since each node knows the set of initial centroids
$C(0)=[\textbf{c}_{1}(0),\textbf{c}_{2}(0),...,\textbf{c}_{k}(0)]\in\mathds{R}^{d\times
k}$ ($k<n$)). This means that it sets $r_{\lambda j}=1$ (where
$\textbf{c}_{\lambda}(0)$ is the nearest centroid) with respect to (8). Then,
it performs $k$ quantized average consensus operations – each operation is
done with the states of the nodes that belong in the same cluster.
Specifically, each node $v_{j}$ executes $k$ times in parallel Algorithm 1 in
Section V-A. Each execution is done with the nodes $\\{v_{i}\in\mathcal{V}\ |\
r_{\lambda i}=r_{\lambda j}=1\\}$ (i.e., that belong in the same cluster). In
this way, each node calculates the exact updated value of every centroid in
finite time.

Iteration - Step $2$. Labeled Distributed Stopping: Every node $v_{j}$
performs $k$ parallel $\min-$ and $\max-$consensus operations every $D$ time
steps as described in Section III. Each operation is done with the states of
the nodes that belong in the same cluster (i.e., with nodes $v_{i},v_{j}$ for
which $r_{\lambda j}=r_{\lambda i}=1$). In this way, each node is able to
determine whether convergence has been achieved and the updated set of
centroids $\textbf{c}_{\gamma}[T+1]$, for every $\gamma\in\\{1,2,...,k\\}$,
has been calculated.

Iteration - Step $3$. Centroid Update, Cluster Assignment and Algorithm
Termination: Once all $k$ executions of Algorithm 1 have converged, each node
$v_{j}$ updates the stored set of centroids. Then, it assigns its value
$x_{j}$ to the nearest updated centroid according to (5). It checks if the
previous centroid values are equal to the new centroid values. If this
condition holds for each node $v_{j}$, the operation of the algorithm is
terminated. Otherwise, the iteration is repeated.

The flowchart for the operation of each node during Algorithm 2 is shown in
Fig. 2. In the flowchart we can see that initially each node assigns a unique
order to its outgoing edges and it also assigns its value to the cluster
characterized by the nearest centroid. Then, for each of the $k$ clusters it
executes (i) “Labeled Multidimensional Deterministic Exact Quantized Average
Consensus” (shown in Algorithm 1 for the case where we have one cluster
$k=1$), and (ii) “Labeled Distributed Stopping”. This allows the calculation
of the new centroid values. Then, it checks if the previous centroid values
are equal to the new centroid values. If this condition holds, the algorithm
has converged and every node terminates its operation. Otherwise, the process
is repeated.

Figure 2: Flowchart for operation of each node during Algorithm 2. Algorithm 2
Finite Time Quantized $k$-means Algorithm

Input: A strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ with $n=|\mathcal{V}|$ nodes and
$m=|\mathcal{E}|$ edges. Each node $v_{j}\in\mathcal{V}$ has an initial
quantized state $x_{j}\in\mathds{Z}^{d}$, and has knowledge of $D$. Each node
$v_{j}$ knows the number of clusters $k<n$ and the initial centroids
$C[0]=[\textbf{c}_{1}[0],\textbf{c}_{2}[0],...,\textbf{c}_{k}[0]]\in\mathds{R}^{d\times
k}$.
Initialization: Each node $v_{j}$ sets $\text{flag}_{j}=0$ and assigns to each
of its outgoing edges $v_{l}\in\mathcal{N}^{+}_{j}$ a unique order $P_{lj}$ in
the set $\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$.
Iteration: For $\mu=1,2,\dots$, each node $v_{j}\in\mathcal{V}$, does the
following:

  * $\bullet$

while $\text{flag}_{j}=0$ then

    * $\bullet$

sets $r_{j\lambda}=1$, where
$||x_{j}-c_{\lambda}[\mu]||\leq||x_{j}-c_{\gamma}[\mu]||$, where
$\gamma\in\\{1,2,...,k\\}\setminus\\{\lambda\\}$;

    * $\bullet$

sets $x^{cl}_{j}[\mu]=x_{j}$, for $cl=\lambda$, where $r_{j\lambda}=1$, and
$x^{cl}_{j}[\mu]=0$, for $cl=\\{1,2,...,k\\}\setminus\\{\lambda\\}$;

    * $\bullet$

calls Algorithm 2.A;

  * $\bullet$

if

$\textbf{c}_{\gamma}(T+1)=\textbf{c}_{\gamma}(T),\ \text{for every}\
\gamma\in\\{1,2,...,k\\},$ (14)

then $\text{flag}_{j}=1$;

Output: (7), (8), (9) hold for every $v_{j}\in\mathcal{V}$.

Algorithm 2.A Extended Labeled Multidimensional Deterministic Quantized
Average Consensus with Labeled Distributed Stopping

Input: $D$, $T$, $\mu$, $x^{cl}_{j}[\mu]$ for $cl=\\{1,2,...,k\\}$, $P_{lj}$
for every $v_{l}\in\mathcal{N}_{j}^{-}$;
Initialization: $y^{cl}_{j}[1]=x^{cl}_{j}[\mu]$ for $cl=\\{1,2,...,k\\}$;
Iteration: For $\mu^{\prime}=1,2,\dots$, each node $v_{j}\in\mathcal{V}$, does
the following:

  * $\bullet$

while $\text{flag}_{j}=0$ then

    * $\bullet$

if $\mu^{\prime}\mod D=1$ then sets
$M^{cl}_{j}=x^{cl}_{j}[\mu^{\prime}]/z^{cl}_{j}[\mu^{\prime}]$,
$m^{cl}_{j}=x^{cl}_{j}[\mu^{\prime}]/z^{cl}_{j}[\mu^{\prime}]$, where
$z_{j}[\mu^{\prime}]=1$, $cl=\\{1,2,...,k\\}$;

    * $\bullet$

broadcasts $M^{cl}_{j}$, $m^{cl}_{j}$, $cl=\\{1,2,...,k\\}$, to every
$v_{j}\in\mathcal{N}_{j}^{+}$;

    * $\bullet$

receives $M^{cl}_{i}$, $m^{cl}_{i}$ from every $v_{i}\in\mathcal{N}_{j}^{-}$,
$cl=\\{1,2,...,k\\}$;

    * $\bullet$

sets $M^{cl}_{j}=\max_{v_{i}\in\mathcal{N}_{j}^{-}\cup\\{v_{j}\\}}\
M^{cl}_{i}$, $m^{cl}_{j}=\min_{v_{i}\in\mathcal{N}_{j}^{-}\cup\\{v_{j}\\}}\
m^{cl}_{j}$;

    * $\bullet$

executes Iteration Steps of Algorithm 1 for each $cl=\\{1,2,...,k\\}$ with
initial state $y^{cl}_{j}[\mu]$;

    * $\bullet$

receives $z^{cl}_{i}[\mu^{\prime}]$, $y^{cl}_{i}[\mu^{\prime}]$ from
$v_{i}\in\mathcal{N}_{j}^{-}$ and sets

$y^{cl}_{j}[\mu^{\prime}+1]=y^{cl}_{j}[\mu^{\prime}]+\sum_{v_{i}\in\mathcal{N}_{j}^{-}}w_{ji}[\mu^{\prime}]\
y^{cl}_{i}[\mu^{\prime}],$ (15)
$z^{cl}_{j}[\mu^{\prime}+1]=z^{cl}_{j}[\mu^{\prime}]+\sum_{v_{i}\in\mathcal{N}_{j}^{-}}w_{ji}[\mu^{\prime}]\
z^{cl}_{i}[\mu^{\prime}],$ (16)

where $w_{ji}[\mu^{\prime}]=1$ if node $v_{j}$ receives a message from
$v_{i}\in\mathcal{N}_{j}^{-}$ at iteration $\mu^{\prime}$ (otherwise
$w_{ji}[\mu^{\prime}]=0$);

    * $\bullet$

if $\mu^{\prime}\mod D=0$ then, if $M^{cl}_{j}=m^{cl}_{j}$, for every
$cl=\\{1,2,...,k\\}$ then sets
$\textbf{c}_{cl}[T+1]=q^{s,cl}_{j}[\mu^{\prime}]$ for every
$cl=\\{1,2,...,k\\}$ and sets $\text{flag}_{j}=1$.

Output: $\textbf{c}_{cl}[T+1]$ for every $cl=\\{1,2,...,k\\}$.

Next, we show that, during the operation of Algorithm 2, each node $v_{j}$ is
able to (i) calculate a set of centroids
$\textbf{c}_{1},\ldots,\textbf{c}_{k}$ that fulfill (7) after a finite number
of time steps, and (ii) terminate its operation once convergence has been
achieved.

######  Theorem 2.

Consider a strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ with $n=|\mathcal{V}|$ nodes and
$m=|\mathcal{E}|$ edges. Each node $v_{j}\in\mathcal{V}$ has an initial
quantized state $x_{j}\in\mathds{Z}^{d}$. Each node $v_{j}$ knows the $k$
initial clusters (where $k<n$) and their initial centroids
$C[0]=[\textbf{c}_{1}[0],\textbf{c}_{2}[0],...,\textbf{c}_{k}[0]]\in\mathds{R}^{d\times
k}$. During the operation of Algorithm 2, each node $v_{j}$ is able to address
problem P1 in Section IV-B after a finite number of time steps $C_{t}$ bounded
by

$C_{t}\leq T(D+nm^{2}),$ (17)

where $T$ is the number of new centroid calculations until (14) holds, $D$ is
the diameter of network $\mathcal{G}_{d}$.

###### Proof.

Similarly to the work in [6], the operation of Algorithm 2 follows the same
step as that for the centralized $k$-means algorithm except that every step is
performed in a decentralized manner. Therefore, Algorithm 2 is able to
calculate, in a distributed fashion, a set of centroids
$\textbf{c}_{1},\ldots,\textbf{c}_{k}$ (where
$\textbf{c}_{\gamma}\in\mathds{R}^{d}$, for $\gamma\in\\{1,2,...,k\\}$), each
associated to a cluster, which fulfill (7), (8) and (9) in finite time.

During the operation of Algorithm 2, we have that each node in the network
executes Algorithms 1, 2.A, until (14) holds (i.e., the new centroid values
are equal to the old centroid values). The required number of time steps for
convergence of Algorithm 1 is equal to $nm^{2}$ (see Theorem 1). The required
number of time steps of the distributed stopping protocol is $D$ since its
operation relies on max- and min-consensus (see Section III). Furthermore, we
use $T$ to denote the number of new centroid calculations until (14) holds. As
a result, we have that during the operation of Algorithm 2 after a finite
number of time steps $C_{t}$ bounded by $C_{t}\leq T(D+nm^{2}),$ each node
$v_{j}$ is able to address problem P1 in Section IV-B. ∎

###  V-C Advantages of Finite Time $k$-means Clustering with Quantized
Communication

Compared to [6] and [7], the main advantage of Algorithm 2 is in the (i)
network requirements, (ii) centroid calculation step and, (iii) distributed
stopping step.

In [6] the new centroid values are calculated via a finite time average
consensus algorithm which operates over the corresponding cluster.
Furthermore, [6] assumes that the graph underlying the agents’ interaction is
undirected (in particular, the finite-time average consensus algorithms
adopted are not suitable for directed graphs). Moreover, in [6] agents need to
know on upper bound for the number of nodes in the network. Finally, in [6]
each node processes and transmits real valued messages. Therefore, in case
communication is quantized, there are no convergence guarantees; moreover, the
messages require more bandwidth than the proposed approach.

In [7] the underlying network is modelled as a strongly connected digraph.
However, in order to calculate the average of the node’s values the digraph
needs to be weight balanced which is a strong assumption (e.g., see [19] and
references therein). Furthermore, the algorithm requires a normalization step
(used to obtain the maximum and minimum value of every component of every
observation) and execution of $k$-means++ algorithm to produce the initial
centroids. Additionally, each node knows an upper bound for the number of
nodes in the network. Finally, as in [6], this algorithm does not provide
convergence guarantees when communication is quantized and messages require
more bandwidth than our proposed approach.

In Algorithm 2 the underlying network is modelled as a strongly connected
digraph. However, in order to calculate the average of the nodes’ values, the
digraph does not need to be weight balanced. Furthermore, in order to
terminate its operation, each node knows an upper bound over the network
diameter and not on the number of nodes. Additionally, each node transmits
quantized messages, which do not require a large amount of bandwidth for
communication and are more suitable for realistic applications (i.e., nodes
need to transmit small messages of finite length). Finally, by utilizing
Algorithm 1 (which is an extension of [16]), nodes are able to calculate the
exact solution in finite time without a final error. This means that the set
of centroids that minimize (2) are calculated exactly. As a result, Algorithm
2 computes the exact minimum of the sum of squares within every cluster (see
Section IV) (and not an approximation of the minimum due to a final error).

##  VI Simulation Results

We now present simulation results to illustrate the behavior of Algorithm 2
over several examples.

Evaluation over a Random Network of $100$ Nodes. We execute Algorithm 2 over a
random digraph of $100$ nodes with diameter $D=4$. The $100$ nodes are
randomly selected in the region $[50,50]\times[50,50]$ with uniform
probability. During the operation of Algorithm 2 we partition nodes into $k=3$
clusters and calculate the centroid values that fulfill (7) in finite time. In
this case, the observations coincide with the agent’s positions (i.e., the
agents are clustered according to their position). In Fig. 3 (A) the initial
positions of the $3$ centroids are marked by red, blue and green crosses, the
nodes are marked with circles, and each circle color is the color of the
nearest initial centroid (i.e., nodes are marked red, blue, or green color).
In Fig. 3 (B) we show the trajectories of the centroids which are marked with
red, blue, or green lines according to the color of the centroid. We can see
that after $T=10$ the centroid values fulfill (14). This means that the nodes
are able to determine that convergence has been achieved and thus proceed to
terminate their operation. In Fig. 4 we show the evolution of the Distance
Objective Function $F(T)$ defined as

$F(T)=\sum_{i=1}^{k}\sum_{v_{j}\in C_{i}(T)}||x_{j}-\textbf{c}_{i}(T)||^{2},$
(18)

for the network of Fig. 3. We can see that $F[T]$ is non-increasing over time.
Furthermore, we can see that $F[9]=F[10]$. This means that for $T=10$ the
centroid values fulfill (14) and nodes terminate their operation (also shown
in Fig. 3 (B)).

Figure 3: Execution of Algorithm 2 over a random directed network with $100$
nodes and $3$ clusters. Positions of nodes are marked with circles and
centroid positions are marked with red, blue and green crosses. (A) Initial
centroid positions, and initial position and cluster assignment for every
node. (B) Centroid trajectories, final centroid positions, and final cluster
assignment for every node. Figure 4: Evolution of Distance Objective Function
$F[T]$ during execution of Algorithm 2 over a random directed network with
$100$ nodes and $3$ clusters.

Evaluation over $1000$ Random Networks of $1000$ Nodes. We execute of
Algorithm 2 over $1000$ random networks each consisting of $1000$ nodes, with
diameter $D\in\\{3,4,5\\}$. During the operation of Algorithm 2, we aim to
partition nodes into $k=3$ clusters. For each of the $1000$ simulations, the
nodes and the centroid positions are randomly selected in the region
$[100,100]\times[100,100]$ with uniform probability. We present the
distribution $\mathcal{F}[T]$ of the new centroid calculations $T$ until (14)
holds for $100$ simulations of Algorithm 2. Furthermore, we present the
average value $\overline{F}[T]$ of the Distance Objective Function $F[T]$ in
(18), averaged over the $1000$ simulations of Algorithm 2.

Figure 5: Executions of Algorithm 2 over $1000$ random directed networks of
$1000$ nodes and $k=3$ clusters. (A) Evolution of Average Distance Objective
Function $\overline{F}[T]$ during execution of Algorithm 2, averaged over
$1000$ executions. (B) Distribution $\mathcal{F}[T]$ of number of new centroid
calculations $T$ until (14) holds, for $1000$ executions.

In Fig. 5 (A), for $1000$ executions of Algorithm 2 we have that
$\overline{F}[T]$ almost converges after $17$ centroid calculations $T$. Also,
note that in Fig. 5 (A), $\overline{F}[T]$ is plotted for
$T\in\\{1,2,...,56\\}$, where $56$ is the maximum value of $T$ for Algorithm 2
to converge over the $1000$ executions. In Fig. 5 (B), we have that the
average value of $T$ for Algorithm 2 to converge over the $1000$ executions is
$17.39$. The minimum value of $T$ is $5$, and the maximum is $56$ (also seen
in Fig. 5 (A)). Furthermore, we can see that in most cases, the required $T$
for Algorithm 2 to converge over the $1000$ executions is in the set
$T\in\\{8,9,...,20\\}$.

Comparison with Previous Literature. We now compare the performance of
Algorithm 2 against algorithms [6], and [7] in the current literature. We
execute the three algorithms over $1000$ random networks each consisting of
$1000$ nodes, with diameter $D\in\\{3,4,5\\}$, and we aim to partition nodes
into $k=3,6,12$ clusters. Note that the main differences of Algorithm 2
compared to [6], and [7] are mentioned in Section V-C. In [7] we initially
execute a $k$-means++ algorithm for the initial centroids. Furthermore, [6]
requires the underlying graph to be undirected. For this reason, during the
operation of [6] we make the randomly generated underlying digraphs undirected
by enforcing that if $(v_{l},v_{j})\in\mathcal{E}$, then also
$(v_{j},v_{l})\in\mathcal{E}$.

In Table VI we present the average number of centroid calculations $T$ over
$1000$ executions of Algorithm 2, [6], and [7]. We can see that the
performance of Algorithm 2 is close to the current literature but requires
slightly more time steps. However, the aim of Algorithm 2 is to implement a
communication efficient solution to the clustering problem. Specifically,
Algorithm 2 operates with quantized values and requires less assumptions
compared to the current literature i.e., in [7] a $k$-means++ algorithm is
initially executed and the network needs to be weight balanced, and in [6] the
network of each cluster is undirected and connected (see Section V-C).

TABLE I: Average Number of Centroid Calculations During Operation of Algorithm 2 (A), [6] (B), [7] (C), averaged for $1000$ executions over a random digraph of $1000$ nodes. Algorithm | $k=3$ | $k=6$ | $k=12$
---|---|---|---
(A) | $17.39$ | $20.79$ | $25.49$
(B) | $16.55$ | $21.62$ | $24.16$
(C) | $11.57$ | $16.86$ | $23.25$

##  VII Conclusions and Future Directions

In this paper, we have considered the problem of $k$-means clustering over a
directed network. We presented a novel algorithm which is able to address the
$k$-means clustering problem in a fully distributed fashion. We showed that
our algorithm converges after a finite number of time steps, and we provided a
deterministic upper bound on convergence time which relies on the network
parameters. Finally, we demonstrated the operation of our proposed algorithm
and compared its performance against other algorithms in the existing
literature. Please note that to the best of the authors knowledge, this is the
first work that tries to tackle the problem of distributed $k$-means
clustering using quantized communication while also providing a thorough
evaluation.

Utilizing our algorithm’s quantized nature in order to introduce privacy
guarantees through cryptographic strategies, is our main future work
direction.

## References

  * [1] Y. Li, J. Qi, X. Chu, and W. Mu, “Customer segmentation using $k$-means clustering and the hybrid particle swarm optimization algorithm,” _The Computer Journal_ , 2022.
  * [2] M. Jain, G. Kaur, and V. Saxena, “A $k$-means clustering and SVM based hybrid concept drift detection technique for network anomaly detection,” _Expert Systems with Applications_ , p. 116510, 2022.
  * [3] S. Ferjaoui, “Data: The new form of wealth and power,” _IEEE Potentials_ , vol. 39, no. 6, pp. 6–10, 2020.
  * [4] I. S. Dhillon and D. S. Modha, “A data-clustering algorithm on distributed memory multiprocessors,” in _Workshop on Large-Scale Parallel KDD Systems, SIGKDD_ , 2000, pp. 245–260.
  * [5] S. Bandyopadhyay, C. Giannella, U. Maulik, H. Kargupta, K. Liu, and S. Datta, “Clustering distributed data streams in peer-to-peer environments,” _Information Sciences_ , vol. 176, no. 14, pp. 1952–1985, 2006.
  * [6] G. Oliva, R. Setola, and C. N. Hadjicostis, “Distributed $k$-means algorithm,” _arXiv preprint arXiv:1312.4176_ , 2015.
  * [7] J. Qin, W. Fu, H. Gao, and W. X. Zheng, “Distributed $k$-means algorithm and fuzzy $c$-means algorithm for sensor networks based on multiagent consensus theory,” _IEEE Transactions on Cybernetics_ , vol. 47, no. 3, pp. 772–783, 2017.
  * [8] P. A. Forero, A. Cano, and G. B. Giannakis, “Consensus-based $k$-means algorithm for distributed learning using wireless sensor networks,” in _Proceedings of Workshop Sensors Signal Info Process_ , 2008, pp. 11–14.
  * [9] L. Faramondi, G. Oliva, R. Setola, and C. N. Hadjicostis, “Distributed $c$-means clustering via broadcast-only token passing,” _IEEE Transactions on Control of Network Systems_ , vol. 7, no. 1, pp. 315–325, 2019\.
  * [10] J. Cortés, “Distributed algorithms for reaching consensus on general functions,” _Automatica_ , vol. 44, pp. 726–737, March 2008.
  * [11] S. Giannini, D. Di Paola, A. Petitti, and A. Rizzo, “On the convergence of the max-consensus protocol with asynchronous updates,” in _Proceedings of IEEE Conference on Decision and Control (CDC)_ , 2013, pp. 2605–2610.
  * [12] D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,” _Machine Learning_ , vol. 75, no. 2, pp. 245–248, 2009.
  * [13] M. Mahajan, P. Nimbhorkar, and K. Varadarajan, “The planar $k$-means problem is NP–hard,” _WALCOM: Algorithms and Computation_ , pp. 274–285, 2009\.
  * [14] J. MacQueen, “Some methods for classification and analysis of multivariate observations,” _Proceedings of the $5^{th}$ Berkeley Symposium on Mathematical Statistics and Probability_, vol. 1, pp. 281–297, 1967.
  * [15] A. K. Jain, “Data clustering: $50$ years beyond $k$-means,” _Pattern Recognition Letters_ , vol. 31, no. 8, pp. 651–666, 2010.
  * [16] A. I. Rikos and C. N. Hadjicostis, “Event-triggered quantized average consensus via ratios of accumulated values,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 3, pp. 1293–1300, 2020.
  * [17] ——, “Distributed average consensus under quantized communication via event-triggered mass summation,” _Proceedings of the IEEE Conference on Decision and Control_ , pp. 894–899, 2018.
  * [18] A. I. Rikos, C. N. Hadjicostis, and K. H. Johansson, “Finite time exact quantized average consensus with limited resources and transmission stopping for energy-aware networks,” _arXiv preprint arXiv:2110.00359_ , 2021.
  * [19] A. I. Rikos, T. Charalambous, and C. N. Hadjicostis, “Distributed weight balancing over digraphs,” _IEEE Transactions on Control of Network Systems_ , vol. 1, no. 2, pp. 190–201, June 2014.