2021

These authors contributed equally to this work.

These authors contributed equally to this work.

[4]José M. Sigarreta These authors contributed equally to this work.

1]Facultad de Ciencias Químicas, Benemérita Universidad Autónoma de Puebla,
Puebla, 72570, Puebla, Mexico

2]Instituto de Física, Benemérita Universidad Autónoma de Puebla, Apartado
Postal J-48, Puebla, 72570, Puebla, Mexico

3]Departamento de Matemáticas, Universidad Carlos III de Madrid, Avenida de la
Universidad 30, Leganés, 28911, Madrid, Spain

4]Facultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame
No.54 Col. Garita, Acapulco, 610101, Guerrero, Mexico

# Multiplicative topological indices: Analytical properties and application to
random networks

R. Aguilar-Sánchez<EMAIL_ADDRESS>J. A. Méndez-Bermúdez
<EMAIL_ADDRESS>José M. Rodríguez<EMAIL_ADDRESS><EMAIL_ADDRESS>[  [  [  [

###### Abstract

We make use of multiplicative degree-based topological indices $X_{\Pi}(G)$ to
perform a detailed analytical and statistical study of random networks
$G=(V(G),E(G))$. We consider two classes of indices: $X_{\Pi}(G)=\prod_{u\in
V(G)}F_{V}(d_{u})$ and $X_{\Pi}(G)=\prod_{uv\in E(G)}F_{E}(d_{u},d_{v})$,
where $uv$ denotes the edge of $G$ connecting the vertices $u$ and $v$,
$d_{u}$ is the degree of the vertex $u$, and $F_{V}(x)$ and $F_{E}(x,y)$ are
functions of the vertex degrees. Specifically, we find analytical inequalities
involving these multiplicative indices. Also, we apply $X_{\Pi}(G)$ on three
models of random networks: Erdös-Rényi networks, random geometric graphs, and
bipartite random networks. We show that $\left<\ln X_{\Pi}(G)\right>$,
normalized to the order of the network, scale with the corresponding average
degree; here $\left<\cdot\right>$ denotes the average over an ensemble of
random networks.

###### keywords:

random networks, degree–based topological indices, scaling approach

##  1 Introduction

We can identify two types of graph invariants which are currently been studied
in chemical graph theory, namely

$\displaystyle X_{\Sigma}(G)=X_{\Sigma,F_{V}}(G)=\sum_{u\in
V(G)}F_{V}(d_{u})\qquad\mbox{or}\qquad$ (1) $\displaystyle
X_{\Sigma}(G)=X_{\Sigma,F_{E}}(G)=\sum_{uv\in E(G)}F_{E}(d_{u},d_{v})$

and

$\displaystyle X_{\Pi}(G)=X_{\Pi,F_{V}}(G)=\prod_{u\in
V(G)}F_{V}(d_{u})\qquad\mbox{or}\qquad$ (2) $\displaystyle
X_{\Pi}(G)=X_{\Pi,F_{E}}(G)=\prod_{uv\in E(G)}F_{E}(d_{u},d_{v})\,.$

Here $uv$ denotes the edge of the graph $G=(V(G),E(G))$ connecting the
vertices $u$ and $v$, $d_{u}$ is the degree of the vertex $u$, and $F_{V}(x)$
and $F_{V}(x,y)$ are appropriate chosen functions, see e.g. G13 . While both
$X_{\Sigma}(G)$ and $X_{\Pi}(G)$ are referred as topological indices in the
literature, to make a distinction between them, here we name $X_{\Pi}(G)$ as
multiplicative topological indices (MTIs).

Among the vast amount of topological indices of the form given by Eq. (1) we
can refer to some prominent examples: the first and second Zagreb indices G72

$M_{1}(G)=\sum_{u\in V(G)}d_{u}^{2}=\sum_{uv\in E(G)}d_{u}+d_{v}$ (3)

and

$M_{2}(G)=\sum_{uv\in E(G)}d_{u}d_{v},$ (4)

respectively, the Randić connectivity index R75

$R(G)=\sum_{uv\in E(G)}\frac{1}{\sqrt{d_{u}d_{v}}},$ (5)

the harmonic index F87

$H(G)=\sum_{uv\in E(G)}\frac{2}{d_{u}+d_{v}},$ (6)

the sum-connectivity index ZT46

$\chi(G)=\sum_{uv\in E(G)}\frac{1}{\sqrt{d_{u}+d_{v}}},$ (7)

and the inverse degree index F87

$ID(G)=\sum_{u\in V(G)}\frac{1}{d_{u}}=\sum_{uv\in
E(G)}\left(\frac{1}{d_{u}^{2}}+\frac{1}{d_{v}^{2}}\right).$ (8)

In fact, within a statistical approach on random networks, it has been
recently shown that the average values of indices of the type $X_{\Sigma}(G)$,
normalized to the order of the network $n$, scale with the average degree
$\left<k\right>$; see e.g. MMRS20 ; AHMS20 ; MMRS21 . That is,
$\left<X_{\Sigma}(G)\right>/n$ is a function of $\left<k\right>$ only.
Moreover, it was also found that $\left<X_{\Sigma}(G)\right>$, for indices
like $R(G)$ and $H(G)$, is highly correlated with the Shannon entropy of the
eigenvectors of the adjacency matrix of random networks AMRS20 . This is a
notable result because it puts forward the application of topological indices
beyond mathematical chemistry. Specifically, given que equivalence of the
Hamiltonian of a tight-binding network (in the proper setup) and the
corresponding network adjacency matrix, either $\left<R(G)\right>$ or
$\left<H(G)\right>$ could be used to determine the eigenvector localization
and delocalization regimes which in turn determine the insulator and metallic
regimes of quantum transport.

Therefore, motivated by their potential applications, in this work we study
MTIs, see Eq. (2), on random networks.

Indeed, several MTIs have been already deeply analyzed in the literature (see
e.g. the work of V. R. Kulli), among the most relevant we have to mention the
Narumi-Katayama index NK84

$NK(G)=\prod_{u\in V(G)}d_{u},$ (9)

and multiplicative versions of the Zagreb indices TC1084 :

$\Pi_{1}(G)=\prod_{u\in V(G)}d_{u}^{2},$ (10) $\Pi_{2}(G)=\prod_{uv\in
E(G)}d_{u}d_{v},$ (11)

and

$\Pi_{1}^{*}(G)=\prod_{uv\in E(G)}d_{u}+d_{v}.$ (12)

In addition to the MTIs of Eqs. (9-12), we also consider multiplicative
versions of the indices in Eqs. (5-8): the multiplicative Randić connectivity
index

$R_{\Pi}(G)=\prod_{uv\in E(G)}\frac{1}{\sqrt{d_{u}d_{v}}},$ (13)

the multiplicative harmonic index

$H_{\Pi}(G)=\prod_{uv\in E(G)}\frac{2}{d_{u}+d_{v}},$ (14)

the multiplicative sum-connectivity index

$\chi_{\Pi}(G)=\prod_{uv\in E(G)}\frac{1}{\sqrt{d_{u}+d_{v}}},$ (15)

and the multiplicative inverse degree index

$ID_{\Pi}(G)=\prod_{uv\in
E(G)}\left(\frac{1}{d_{u}^{2}}+\frac{1}{d_{v}^{2}}\right).$ (16)

Below we apply the MTIs of Eqs. (9-16) on three models of random networks:
Erdös-Rényi (ER) networks, random geometric (RG) graphs, and bipartite random
(BR) networks. ER networks SR51 ; ER59 ; ER60  $G_{\mbox{\tiny ER}}(n,p)$ are
formed by $n$ vertices connected independently with probability $p\in[0,1]$.
While RG graphs DC02 ; P03  $G_{\mbox{\tiny RG}}(n,r)$ consist of $n$ vertices
uniformly and independently distributed on the unit square, where two vertices
are connected by an edge if their Euclidean distance is less or equal than the
connection radius $r\in[0,\sqrt{2}]$. In addition we examine BR networks
$G_{\mbox{\tiny BR}}(n_{1},n_{2},p)$ composed by two disjoint sets, set 1 and
set 2, with $n_{1}$ and $n_{2}$ vertices each such that there are no adjacent
vertices within the same set, being $n=n_{1}+n_{2}$ the total number of
vertices in the bipartite network. The vertices of the two sets are connected
randomly with probability $p\in[0,1]$.

The purpose of this work is threefold. First, from an analytical viewpoint, we
find several inequalities that relate multiplicative indices to their additive
versions; second, we want to establish the statistical analysis of MTIs as a
generic tool for studying average properties of random networks; and third, we
perform for the first time (to our knowledge), a scaling study of MTIs on
random networks.

##  2 Some inequalities involving multiplicative topological indices

We obtain in this section several analytical inequalities involving general
multiplicative topological indices $X_{\Pi}$. There are many papers studying
particular multiplicative topological indices (see, e.g., GutmanMilovanovic ,
RetiGutman  and the references therein).

The following equalities are direct:

$\displaystyle X_{\Pi,F_{V}}(G)$ $\displaystyle=\prod_{u\in
V(G)}F_{V}(d_{u})=e^{\sum_{u\in V(G)}\log F_{V}(d_{u})}=e^{X_{\Sigma,\log
F_{V}}(G)},$ $\displaystyle X_{\Pi,F_{E}}(G)$ $\displaystyle=\prod_{uv\in
E(G)}F_{E}(d_{u},d_{v})=e^{\sum_{uv\in E(G)}\log
F_{E}(d_{u},d_{v})}=e^{X_{\Sigma,\log F_{E}}(G)}.$

Since the geometric mean is at most the arithmetic mean (by Jensen’s
inequality), we have the following inequalities.

######  Proposition 1.

Let $G$ be a graph with $n$ vertices and $m$ edges. Then

$\displaystyle X_{\Pi,F_{V}}(G)^{1/n}$
$\displaystyle\leq\frac{1}{n}\,X_{\Sigma,F_{V}}(G),\qquad
X_{\Pi,F_{E}}(G)^{1/m}\leq\frac{1}{m}\,X_{\Sigma,F_{E}}(G).$

In BQRS  appears the following Jensen-type inequality.

######  Theorem 2.

Let $\mu$ be a probability measure on the space $X$ and $a\leq b$ real
constants. If $f:X\rightarrow[a,b]$ is a measurable function and $\varphi$ is
a convex function on $[a,b]$, then $f$ and $\varphi\circ f$ are
$\mu$-integrable functions and

$\varphi\Big{(}a+b-\int_{X}f\,d\mu\Big{)}\leq\varphi(a)+\varphi(b)-\int_{X}\varphi\circ
f\,d\mu.$

Theorem 2 allows to find the following converse version of Proposition 1.

######  Theorem 3.

Let $G$ be a graph with $n$ vertices and $m$ edges, $a_{V}\leq b_{V}$,
$a_{E}\leq b_{E}$ be real constants and $F_{V}$, $F_{E}$ be functions
satisfying

$a_{V}\leq F_{V}(d_{u})\leq b_{V}\quad\forall\,u\in V(G),\qquad a_{E}\leq
F_{E}(d_{u},d_{v})\leq b_{E}\quad\forall\,uv\in E(G).$

Then

$\displaystyle\frac{1}{n}\,X_{\Sigma,F_{V}}(G)$ $\displaystyle\leq
e^{a_{V}}+e^{b_{V}}-\frac{e^{a_{V}+b_{V}}}{X_{\Pi,F_{V}}(G)^{1/n}}\,,$
$\displaystyle\frac{1}{m}\,X_{\Sigma,F_{E}}(G)$ $\displaystyle\leq
e^{a_{E}}+e^{b_{E}}-\frac{e^{a_{E}+b_{E}}}{X_{\Pi,F_{E}}(G)^{1/m}}\,.$

Proof: Since $\varphi(x)=e^{x}$ is a convex function on $\mathbb{R}$, Theorem
2 gives

$\displaystyle e^{a_{V}+b_{V}-\frac{1}{n}\sum_{u\in V(G)}\log F_{V}(d_{u})}$
$\displaystyle\leq e^{a_{V}}+e^{b_{V}}-\frac{1}{n}\sum_{u\in V(G)}e^{\log
F_{V}(d_{u})},$ $\displaystyle e^{a_{V}+b_{V}}e^{-\log(\Pi_{u\in
V(G)}F_{V}(d_{u}))^{1/n}}$ $\displaystyle\leq
e^{a_{V}}+e^{b_{V}}-\frac{1}{n}\sum_{u\in V(G)}F_{V}(d_{u}),$
$\displaystyle\frac{e^{a_{V}+b_{V}}}{X_{\Pi,F_{V}}(G)^{1/n}}$
$\displaystyle\leq e^{a_{V}}+e^{b_{V}}-\frac{1}{n}\,X_{\Sigma,F_{V}}(G).$

In a similar way,

$\displaystyle e^{a_{E}+b_{E}-\frac{1}{n}\sum_{uv\in E(G)}\log
F_{E}(d_{u},d_{v})}$ $\displaystyle\leq
e^{a_{E}}+e^{b_{E}}-\frac{1}{n}\sum_{uv\in E(G)}e^{\log F_{E}(d_{u},d_{v})},$
$\displaystyle e^{a_{E}+b_{E}}e^{-\log(\Pi_{uv\in
E(G)}F_{E}(d_{u},d_{v}))^{1/n}}$ $\displaystyle\leq
e^{a_{E}}+e^{b_{E}}-\frac{1}{n}\sum_{uv\in E(G)}F_{E}(d_{u},d_{v}),$
$\displaystyle\frac{e^{a_{E}+b_{E}}}{X_{\Pi,F_{E}}(G)^{1/m}}$
$\displaystyle\leq e^{a_{E}}+e^{b_{E}}-\frac{1}{m}\,X_{\Sigma,F_{E}}(G).$

The following Kober’s inequalities in Kober  (see also (ZGA, , Lemma 1)) are
useful.

######  Lemma 1.

If $a_{j}>0$ for $1\leq j\leq k$, then

$\sum_{j=1}^{k}a_{j}+k(k-1)\Big{(}\prod_{j=1}^{k}a_{j}\Big{)}^{1/k}\leq\Big{(}\sum_{j=1}^{k}\sqrt{a_{j}}\Big{)}^{2}\leq(k-1)\sum_{j=1}^{k}a_{j}+k\Big{(}\prod_{j=1}^{k}a_{j}\Big{)}^{1/k}.$

Lemma 1 has the following consequence.

######  Theorem 4.

Let $G$ be a graph with $n$ vertices and $m$ edges. Then

$\displaystyle X_{\Sigma,F_{V}^{2}}(G)+n(n-1)X_{\Pi,F_{V}}(G)^{2/n}$
$\displaystyle\leq
X_{\Sigma,F_{V}}(G)^{2}\leq(n-1)X_{\Sigma,F_{V}^{2}}(G)+nX_{\Pi,F_{V}}(G)^{2/n},$
$\displaystyle X_{\Sigma,F_{E}^{2}}(G)+m(m-1)X_{\Pi,F_{E}}(G)^{2/m}$
$\displaystyle\leq
X_{\Sigma,F_{E}}(G)^{2}\leq(m-1)X_{\Sigma,F_{E}^{2}}(G)+mX_{\Pi,F_{E}}(G)^{2/m}.$

Proof: Lemma 1 gives

$\displaystyle\sum_{u\in V(G)}F_{V}(d_{u})^{2}+n(n-1)\Big{(}\prod_{u\in
V(G)}F_{V}(d_{u})^{2}\Big{)}^{1/n}$ $\displaystyle\leq\Big{(}\sum_{u\in
V(G)}F_{V}(d_{u})\Big{)}^{2},$ $\displaystyle
X_{\Sigma,F_{V}^{2}}(G)+n(n-1)X_{\Pi,F_{V}}(G)^{2/n}$ $\displaystyle\leq
X_{\Sigma,F_{V}}(G)^{2},$

and

$\displaystyle\Big{(}\sum_{u\in V(G)}F_{V}(d_{u})\Big{)}^{2}$
$\displaystyle\leq(n-1)\sum_{u\in V(G)}F_{V}(d_{u})^{2}+n\Big{(}\prod_{u\in
V(G)}F_{V}(d_{u})^{2}\Big{)}^{1/n},$ $\displaystyle X_{\Sigma,F_{V}}(G)^{2}$
$\displaystyle\leq(n-1)X_{\Sigma,F_{V}^{2}}(G)+nX_{\Pi,F_{V}}(G)^{2/n}.$

In a similar way,

$\displaystyle\sum_{uv\in
E(G)}F_{E}(d_{u},d_{v})^{2}+m(m-1)\Big{(}\prod_{uv\in
E(G)}F_{E}(d_{u},d_{v})^{2}\Big{)}^{1/m}$ $\displaystyle\leq\Big{(}\sum_{uv\in
E(G)}F_{E}(d_{u},d_{v})\Big{)}^{2},$ $\displaystyle
X_{\Sigma,F_{E}^{2}}(G)+m(m-1)X_{\Pi,F_{E}}(G)^{2/m}$ $\displaystyle\leq
X_{\Sigma,F_{E}}(G)^{2},$

and

$\displaystyle\Big{(}\sum_{uv\in E(G)}F_{E}(d_{u},d_{v})\Big{)}^{2}$
$\displaystyle\leq(m-1)\sum_{uv\in
E(G)}F_{E}(d_{u},d_{v})^{2}+m\Big{(}\prod_{uv\in
E(G)}F_{E}(d_{u},d_{v})^{2}\Big{)}^{1/m},$ $\displaystyle
X_{\Sigma,F_{E}}(G)^{2}$
$\displaystyle\leq(m-1)X_{\Sigma,F_{E}^{2}}(G)+mX_{\Pi,F_{E}}(G)^{2/m}.$

Let us recall the following known Petrović inequality Petrovic .

######  Theorem 5.

Let $\varphi$ be a convex function on $[0,a]$, and $w_{1},\dots,w_{n}\geq 0$.
If $t_{1},\dots,t_{n}\in[0,a]$ satisfy $\sum_{k=1}^{n}t_{k}w_{k}\in(0,a]$, and

$\sum_{k=1}^{n}t_{k}w_{k}\geq t_{j},\qquad j=1,\dots,n,$

then

$\sum_{k=1}^{n}\varphi(t_{k})w_{k}\leq\varphi\Big{(}\sum_{k=1}^{n}t_{k}w_{k}\Big{)}+\Big{(}\sum_{k=1}^{n}w_{k}-1\Big{)}\varphi(0).$

Theorem 5 has the following consequence.

######  Proposition 6.

Let $\varphi$ be a convex function on $[0,a]$. If $t_{1},\dots,t_{n}\in[0,a]$
satisfy $\sum_{k=1}^{n}t_{k}\in(0,a]$, then

$\sum_{k=1}^{n}\varphi(t_{k})\leq\varphi\Big{(}\sum_{k=1}^{n}t_{k}\Big{)}+(n-1)\varphi(0).$

Proposition 6 allows to prove the following inequalities.

######  Theorem 7.

Let $G$ be a graph with $n$ vertices and $m$ edges. Then

$X_{\Sigma,F_{V}}(G)\leq X_{\Pi,F_{V}}(G)+n-1,\quad X_{\Sigma,F_{E}}(G)\leq
X_{\Pi,F_{E}}(G)+m-1.$

Proof: Let us consider the convex function $\varphi(x)=e^{x}$. Proposition 6
gives

$\displaystyle X_{\Sigma,F_{V}}(G)$ $\displaystyle=\sum_{u\in
V(G)}F_{V}(d_{u})=\sum_{u\in V(G)}e^{\log F_{V}(d_{u})}$ $\displaystyle\leq
e^{\sum_{u\in V(G)}\log F_{V}(d_{u})}+n-1=e^{\log\Pi_{u\in
V(G)}F_{V}(d_{u})}+n-1$ $\displaystyle=\Pi_{u\in
V(G)}F_{V}(d_{u})+n-1=X_{\Pi,F_{V}}(G)+n-1.$

In a similar way,

$\displaystyle X_{\Sigma,F_{E}}(G)$ $\displaystyle=\sum_{uv\in
E(G)}F_{E}(d_{u},d_{v})=\sum_{uv\in E(G)}e^{\log F_{E}(d_{u},d_{v})}$
$\displaystyle\leq e^{\sum_{uv\in E(G)}\log
F_{E}(d_{u},d_{v})}+m-1=e^{\log\Pi_{uv\in E(G)}F_{E}(d_{u},d_{v})}+m-1$
$\displaystyle=\Pi_{uv\in E(G)}F_{E}(d_{u},d_{v})+m-1=X_{\Pi,F_{E}}(G)+m-1.$

######  Theorem 8.

Let $G$ be a graph. Then

$X_{\Pi,F_{V}}(G)\geq X_{\Sigma,\log F_{V}}(G)+1,\qquad X_{\Pi,F_{E}}(G)\geq
X_{\Sigma,\log F_{E}}(G)+1.$

Proof: The equality $e^{x}\geq x+1$ holds for every $x\in\mathbb{R}$. This
inequality gives

$\displaystyle X_{\Pi,F_{V}}(G)$ $\displaystyle=e^{\log
X_{\Pi,F_{V}}(G)}\geq\log X_{\Pi,F_{V}}(G)+1$
$\displaystyle=\log\Big{(}\Pi_{u\in E(G)}F_{V}(d_{u})\Big{)}+1=\sum_{u\in
E(G)}\log F_{V}(d_{u})+1$ $\displaystyle=X_{\Sigma,\log F_{V}}(G)+1.$

The same argument gives the second inequality.

##  3 Statistical properties of multiplicative topological indices on random
networks

###  3.1 Multiplicative topological indices on Erdös-Rényi random networks

Before computing MTIs on ER random networks we note that in the dense limit,
i.e. when $\left<d\right>\gg 1$, we can approximate $d_{u}\approx
d_{v}\approx\left<d\right>$ in Eqs. (9-16), with

$\left<d\right>=(n-1)p.$ (17)

Thus, for example, when $np\gg 1$, we can approximate $NK_{\Pi}(G_{\mbox{\tiny
ER}})$ as

$NK(G_{\mbox{\tiny ER}})=\prod_{u\in V(G)}d_{u}\approx\prod_{u\in
V(G)}\left<d\right>\approx\left<d\right>^{n},$

which leads us to

$\ln NK(G_{\mbox{\tiny ER}})\approx n\ln\left<d\right>$

or

$\frac{\ln NK(G_{\mbox{\tiny ER}})}{n}\approx\ln\left<d\right>.$ (18)

A similar approximation gives

$\frac{\ln\Pi_{1}(G_{\mbox{\tiny ER}})}{n}\approx 2\ln\left<d\right>.$ (19)

Also, for $\Pi_{2}(G_{\mbox{\tiny ER}})$ we have that

$\Pi_{2}(G_{\mbox{\tiny ER}})=\prod_{uv\in E(G)}d_{u}d_{v}\approx\prod_{uv\in
E(G)}\left<d\right>\left<d\right>=\prod_{uv\in
E(G)}\left<d\right>^{2}\approx\left<d\right>^{n\left<d\right>},$

where we have used $\mid E(G_{\mbox{\tiny ER}})\mid=n\left<d\right>/2$.
Therefore

$\ln\Pi_{2}(G_{\mbox{\tiny ER}})\approx n\left<d\right>\ln\left<d\right>$

or

$\frac{\ln\Pi_{2}(G_{\mbox{\tiny
ER}})}{n}\approx\left<d\right>\ln\left<d\right>.$ (20)

Following this procedure, for the rest of the MTIs of Eqs. (12-16) we get:

$\frac{\ln\Pi_{1}^{*}(G_{\mbox{\tiny
ER}})}{n}\approx\frac{1}{2}\left<d\right>\ln(2\left<d\right>),$ (21)
$\frac{\ln R_{\Pi}(G_{\mbox{\tiny
ER}})}{n}\approx-\frac{1}{2}\left<d\right>\ln\left<d\right>,$ (22) $\frac{\ln
H_{\Pi}(G_{\mbox{\tiny
ER}})}{n}\approx-\frac{1}{2}\left<d\right>\ln\left<d\right>,$ (23)
$\frac{\ln\chi_{\Pi}(G_{\mbox{\tiny ER}})}{n}\approx-\frac{\ln
2}{4}\left<d\right>-\frac{1}{4}\left<d\right>\ln\left<d\right>,$ (24)

and

$\frac{\ln ID_{\Pi}(G_{\mbox{\tiny ER}})}{n}\approx\frac{\ln
2}{2}\left<d\right>-\left<d\right>\ln\left<d\right>.$ (25)

From the approximate expressions above we note that the logarithm of the MTIs
on ER random networks, normalized to the network size $n$, does not depend on
$n$. That is, in the dense limit, we expect $\ln X_{\Pi}(G_{\mbox{\tiny
ER}})/n$ to depend on $\left<d\right>$ only; here $X$ represents all the MTIs
of Eqs. (9-16).

Figure 1:  Average logarithm of the multiplicative topological indices of Eqs.
(9-16) as a function of the probability $p$ of Erdös-Rényi networks of size
$n$. The inset in (h) is an enlargement for small $p$.  Figure 2:  Average
logarithm of the multiplicative topological indices of Eqs. (9-16), normalized
to the network size $n$, as a function of the average degree $\left<k\right>$
of Erdös-Rényi networks. Orange dashed lines in (a-h) are Eqs. (18-25),
respectively. The vertical magenta dashed lines indicate $\left<k\right>=10$.
The inset in (h) is an enlargement for small $\left<k\right>$.

Having Eqs. (18-25) as a guide, in what follows we compute the average values
of the logarithm of the MTIs listed in Eqs. (9-16). All averages are computed
over ensembles of $10^{7}/n$ ER networks characterized by the parameter pair
$(n,p)$.

In Fig. 1 we present the average logarithm of the eight MTIs of Eqs. (9-16) as
a function of the probability $p$ of ER networks of sizes
$n=\\{125,250,500,1000\\}$. Since $\left<\ln X_{\Pi}(G_{\mbox{\tiny
ER}})\right><0$ for $R_{\Pi}$, $H_{\Pi}$ and $\chi_{\Pi}$ we conveniently
plotted $-\left<\ln X_{\Pi}(G_{\mbox{\tiny ER}})\right>$ in log scale to have
a detailed view of the data for small $p$, see Figs. 1(e-g). Thus we observe
that $\left<\ln X_{\Pi}(G_{\mbox{\tiny ER}})\right>$ for $NK$, $\Pi_{1,2}$ and
$\Pi_{1}^{*}$ [for $R_{\Pi}$, $H_{\Pi}$ and $\chi_{\Pi}$] is a monotonically
increasing [monotonically decreasing] function of $p$. In contrast, $\left<\ln
ID_{\Pi}(G_{\mbox{\tiny ER}})\right>$ is a nonmonotonic function of $p$, see
Fig. 1(h).

Then, following Eqs. (18-25), in Fig. 2 we show again the average logarithm of
the MTIs but now normalized to the network size, $\left<\ln
X_{\Pi}(G_{\mbox{\tiny ER}})\right>/n$, as a function of $\left<k\right>$. As
can be clearly observed in this figure, the curves $\left<\ln
X_{\Pi}(G_{\mbox{\tiny ER}})\right>/n$ versus $\left<k\right>$ fall one on top
of the other for different network sizes; so these indices are properly scaled
where $\left<k\right>$ works as the scaling parameter. That is,
$\left<k\right>$ is the parameter that fixes the average values of the
normalized MTIs on ER networks. It is remarkable that the scaling of
$\left<\ln X_{\Pi}(G_{\mbox{\tiny ER}})\right>/n$ with $\left<k\right>$,
expected for $\left<k\right>\gg 1$ according to Eqs. (18-25), works perfectly
well for all values of $\left<k\right>$; even for $\left<k\right>\ll 1$. Also,
in Figs. 2, we show that Eqs. (18-25) (orange-dashed lines) indeed describe
well the data (thick full curves) for $\left<k\right>\geq 10$, which can be
regarded as de dense limit of the ER model.

Figure 3:  Average logarithm of the multiplicative topological indices of Eqs.
(9-16) as a function of the connection radius $r$ of random geometric graphs
of size $n$. The inset in (h) is an enlargement for small $r$.  Figure 4:
Average logarithm of the multiplicative topological indices of Eqs. (9-16),
normalized to the graph size $n$, as a function of the average degree
$\left<k\right>$ of random geometric graphs. Orange dashed lines in (a-h) are
Eqs. (28-35), respectively. The vertical magenta dashed lines indicate
$\left<k\right>=10$. The inset in (h) is an enlargement for small
$\left<k\right>$.

###  3.2 Multiplicative topological indices on random geometric graphs

As in the previous Subsection, here we start by exploring the dense limit.
Indeed, for RG graphs in the dense limit, i.e. when $\left<d\right>\gg 1$, we
can approximate $d_{u}\approx d_{v}\approx\left<d\right>$, where

$\left<d\right>=(n-1)g(r)$ (26)

and EM15

$g(r)=\left\\{\begin{array}[]{ll}r^{2}\left[\pi-\frac{8}{3}r+\frac{1}{2}r^{2}\right],&0\leq
r\leq 1\,,\vspace{0.25cm}\\\
\frac{1}{3}-2r^{2}\left[1-\arcsin(1/r)+\arccos(1/r)\right]\vspace{0.15cm}\\\
\qquad+\frac{4}{3}(2r^{2}+1)\sqrt{r^{2}-1}-\frac{1}{2}r^{4},&1\leq
r\leq\sqrt{2}\,.\end{array}\right.$ (27)

Thus, we obtain:

$\frac{\ln NK(G_{\mbox{\tiny RG}})}{n}\approx\ln\left<d\right>,$ (28)
$\frac{\ln\Pi_{1}(G_{\mbox{\tiny RG}})}{n}\approx 2\ln\left<d\right>,$ (29)
$\frac{\ln\Pi_{2}(G_{\mbox{\tiny
RG}})}{n}\approx\left<d\right>\ln\left<d\right>,$ (30)
$\frac{\ln\Pi_{1}^{*}(G_{\mbox{\tiny
RG}})}{n}\approx\frac{1}{2}\left<d\right>\ln(2\left<d\right>),$ (31)
$\frac{\ln R_{\Pi}(G_{\mbox{\tiny
RG}})}{n}\approx-\frac{1}{2}\left<d\right>\ln\left<d\right>,$ (32) $\frac{\ln
H_{\Pi}(G_{\mbox{\tiny
RG}})}{n}\approx-\frac{1}{2}\left<d\right>\ln\left<d\right>,$ (33)
$\frac{\ln\chi_{\Pi}(G_{\mbox{\tiny RG}})}{n}\approx-\frac{\ln
2}{4}\left<d\right>-\frac{1}{4}\left<d\right>\ln\left<d\right>,$ (34)

and

$\frac{\ln ID_{\Pi}(G_{\mbox{\tiny RG}})}{n}\approx\frac{\ln
2}{2}\left<d\right>-\left<d\right>\ln\left<d\right>.$ (35)

Figure 5:  Average logarithm of the multiplicative topological indices of Eqs.
(9-16) as a function of the probability $p$ of bipartite random networks of
sizes $n_{1}$ and $n_{2}$. In all panels $n_{1}=n_{2}=\\{125,250,500,1000\\}$.
The inset in (h) is an enlargement for small $p$.  Figure 6:  Average
logarithm of the multiplicative topological indices of Eqs. (9-16), normalized
to the network size $n$, as a function of the average degree $\left<k\right>$
of bipartite random networks of sizes $n_{1}$ and $n_{2}$. In all panels
$n_{1}=n_{2}=\\{125,250,500,1000\\}$. Orange dashed lines in (a,b) are Eqs.
(18,19), respectively. Orange dashed lines in (c-h) are Eqs. (37-42),
respectively. The vertical magenta dashed lines indicate $\left<k\right>=10$.
The inset in (h) is an enlargement for small $\left<k\right>$.

Remarkably, the approximate Eqs. (28-35) for RG graphs are exactly the same as
the corresponding equations for ER graphs, see Eqs. (18-25); however note that
the definition of $\left<d\right>$ is different for both models, i.e. compare
Eqs. (17) and (26-27).

Then, in Fig. 3 we present the average logarithm of the eight MTIs of Eqs.
(9-16) as a function of the connection radius $r$ of RG graphs of sizes
$n=\\{125,250,500,1000\\}$. All averages are computed over ensembles of
$10^{7}/n$ random graphs, each ensemble is characterized by a fixed parameter
pair $(n,r)$.

For comparison purposes, Fig. 1 for ER networks and Fig. 3 for RG graphs have
the same format and contents. In fact, all the observations made in the
previous Subsection for ER networks are also valid for RG graphs by replacing
$G_{\mbox{\tiny ER}}\to G_{\mbox{\tiny RG}}$ and $p\to g(r)$. Therefore, in
Fig. 4 we plot $\left<\ln X_{\Pi}(G_{\mbox{\tiny RG}})\right>/n$ as a function
of $\left<k\right>$ showing that all curves are properly scaled; that is,
curves for different graph sizes fall on top of each other. Also, in Fig. 4,
we show that Eqs. (28-35) (orange-dashed lines) indeed describe well the data
(thick full curves) for $\left<k\right>\geq 10$, which can be regarded as de
dense limit of RG graphs.

###  3.3 Multiplicative topological indices on bipartite random networks

We start by writing approximate expressions for the MTIs on BR networks in the
dense limit. Moreover, since edges in a bipartite network join vertices of
different sets, and we are labeling here the sets as set 1 and set 2, we
replace $d_{u}$ by $d_{1}$ and $d_{v}$ by $d_{2}$ in the expression for the
MTIs. Thus, when $n_{1}p\gg 1$ and $n_{2}p\gg 1$, we can approximate
$d_{u}=d_{1}\approx\left<d_{1}\right>$ and
$d_{v}=d_{2}\approx\left<d_{2}\right>$ in Eqs. (9-16), with

$\left<d_{1,2}\right>=n_{2,1}p.$ (36)

Therefore, in the dense limit, the MTIs of Eqs. (11-16) on BR networks are
well approximated by:

$\frac{\ln\Pi_{2}(G_{\mbox{\tiny
BR}})}{n_{1,2}}\approx\left<d_{1,2}\right>\ln(\left<d_{1}\right>\left<d_{2}\right>),$
(37) $\frac{\ln\Pi_{1}^{*}(G_{\mbox{\tiny
BR}})}{n_{1,2}}\approx\left<d_{1,2}\right>\ln(\left<d_{1}\right>+\left<d_{2}\right>),$
(38) $\frac{\ln R_{\Pi}(G_{\mbox{\tiny
BR}})}{n_{1,2}}\approx-\frac{1}{2}\left<d_{1,2}\right>\ln\left(\left<d_{1}\right>\left<d_{2}\right>\right),$
(39) $\frac{\ln H_{\Pi}(G_{\mbox{\tiny
BR}})}{n_{1,2}}\approx\left<d_{1,2}\right>\left[\ln
2-\ln\left(\left<d_{1}\right>+\left<d_{2}\right>\right)\right],$ (40)
$\frac{\ln\chi_{\Pi}(G_{\mbox{\tiny
BR}})}{n_{1,2}}\approx-\frac{1}{2}\left<d_{1,2}\right>\ln\left(\left<d_{1}\right>+\left<d_{2}\right>\right),$
(41)

and

$\frac{\ln ID_{\Pi}(G_{\mbox{\tiny
BR}})}{n_{1,2}}\approx\left<d_{1,2}\right>\ln\left(\frac{1}{\left<d_{1}\right>^{2}}+\frac{1}{\left<d_{2}\right>^{2}}\right).$
(42)

Above we used $\mid E(G_{\mbox{\tiny
BR}})\mid=n_{1}n_{2}p=n_{1,2}\left<d_{1,2}\right>$. We note that we are not
providing approximate expressions for $NK(G_{\mbox{\tiny BR}})$ nor
$\Pi_{1}(G_{\mbox{\tiny BR}})$.

Now we compute MTIs on ensembles of $10^{7}/n$ BR networks. In contrast to ER
and RG networks now the BR network ensembles are characterized by three
parameters: $n_{1}$, $n_{2}$, and $p$. For simplicity, but without lost of
generality, in our numerical calculations we consider $n_{1}=n_{2}$. It is
remarkable to notice that in the case of $n_{1}=n_{2}=n/2$, where
$\left<k_{1}\right>=\left<k_{2}\right>=\left<k\right>=np/2$, Eqs. (37-42)
reproduce Eqs. (20-25).

Then, in Fig. 5 we present the average logarithm of the eight MTIs of Eqs.
(9-16) as a function of the probability $p$ of BR networks of sizes
$n_{1}=n_{2}=\\{125,250,500,1000\\}$. Therefore, by plotting $\left<\ln
X_{\Pi}(G_{\mbox{\tiny BR}})\right>/n$ as a function of $\left<k\right>$, see
Fig. 6, we confirm that the curves of the MTIs on BR networks are properly
scaled, as predicted by Eqs. (37-42); see the orange dashed lines in Fig.
6(c-h). Here, we can also say that $\left<k\right>\geq 10$ can be regarded as
de dense limit of BR networks. We have verified (not shown here) that we
arrive to equivalent conclusions when $n_{1}\neq n_{2}$.

Note that in panels (a,b) of Fig. 6 we included Eqs. (18,19) as orange dashed
lines. Those equations were obtained for ER networks, however they reproduce
perfectly well both $NK(G_{\mbox{\tiny BR}})$ and $\Pi_{1}(G_{\mbox{\tiny
BR}})$ when $\left<k\right>\geq 10$ since we are considering
$n_{1}=n_{2}=n/2$.

##  4 Conclusions

In this work we have performed a thorough analytical and statistical study of
multiplicative topological indices (MTIs) on random networks. As models of
random networks we have used Erdös-Rényi networks, random geometric graphs,
and bipartite random networks.

From an analytical viewpoint, we find several inequalities that relate
multiplicative indices to their additive versions.

Within a statistical approach, we show that the average logarithm of the MTIs,
$\left<\ln X_{\Pi}(G)\right>$, normalized to the order of the network, scale
with the network average degree $\left<k\right>$. Thus, we conclude that
$\left<k\right>$ is the parameter that fixes the average values of the
logarithm of the MTIs on random networks. Moreover, the equivalence among Eqs.
(18-25) for Erdös-Rényi networks, Eqs. (28-35) for random geometric graphs,
and Eqs. (37-42) for bipartite random networks (when the subsets are equal in
size) allows us to state a scaling law that connects the three graph models.
That is, given the multiplicative topological index $X_{\Pi}$, the average of
its logarithm divided by the network size is the same function of the average
degree regardless the network model:

$\frac{\left<\ln X_{\Pi}(G_{\mbox{\tiny ER}})\right>}{n}\approx\frac{\left<\ln
X_{\Pi}(G_{\mbox{\tiny RG}})\right>}{n}\approx\frac{\left<\ln
X_{\Pi}(G_{\mbox{\tiny BR}})\right>}{n}\approx f(\left<k\right>).$ (43)

To validate Eq. (43) we choose the Narumi-Katayama index, see Eq. (9), apply
it to Erdös-Rényi networks, random geometric graphs and bipartite random
networks and plot $\left<\ln NK_{\Pi}(G)\right>/n$ in Fig. 7(a). There, we can
clearly see that the curves corresponding to the three network models fall one
on top of the other, thus validating Eq. (43). Also notice that we are using
networks of different sizes to stress the scaling law in Eq. (43). We observe
the same scaling behavior in all the other MTIs of Eqs. (10-16), as can be
seen in Figs. 7(b,c) where we present $\left<\ln\chi_{\Pi}(G)\right>/n$ and
$\left<\ln ID_{\Pi}(G)\right>/n$, respectively.

Figure 7:  Average logarithm of (a) $NK(G)$, (b) $\chi_{\Pi}(G)$, and (c)
$ID_{\Pi}(G)$, normalized to the network size $n$, as a function of the
average degree $\left<k\right>$ of random geometric graphs of size $n=500$,
Erdös-Rényi networks of size $n=250$ and bipartite random networks of size
$n=2n_{1}=2n_{2}=2000$. Orange dashed lines are (a) Eq. (18), (b) Eq. (24),
and (c) Eq. (25). The inset in (c) is an enlargement for small
$\left<k\right>$.

Finally, it is fair to mention that we found that the multiplicative version
of the geometric-arithmetic index $GA_{\Pi}(G)$ on random networks does not
scale with the average degree. This situation is quite unexpected for us since
all other MTIs we study here scale with $\left<k\right>$. In addition, our
previous statistical and theoretical studies of topological indices of the
form $X_{\Sigma}(G)$, see Eq. (1), showed that the normalized geometric-
arithmetic index $GA_{\Sigma}(G)$ scales with $\left<k\right>$ AHMS20 . Thus,
we believe that the multiplicative index $GA_{\Pi}(G)$ on random graphs
requieres further analysis.

We hope that our work may motivate further analytical as well as computational
studies of multiplicative topological indices on random networks.

Acknowledgments

The research of J.M.R. and J.M.S. was supported by a grant from Agencia
Estatal de Investigación (PID2019-106433GBI00/AEI/10.13039/501100011033),
Spain. J.M.R. was supported by the Madrid Government (Comunidad de Madrid-
Spain) under the Multiannual Agreement with UC3M in the line of Excellence of
University Professors (EPUC3M23), and in the context of the V PRICIT (Regional
Programme of Research and Technological Innovation).

## Declarations

The authors declare no conflict of interest. The founding sponsors had no role
in the design of the study; in the collection, analyses, or interpretation of
data; in the writing of the manuscript, and in the decision to publish the
results.

## References

  * (1) I. Gutman, Degree-based topological indices, Croat. Chem. Acta 86, 351–361 (2013).
  * (2) I. Gutman and N. Trinajstić, Chem. Phys. Lett. 17 (1972) 535.
  * (3) Randić, M. On characterization of molecular branching. J. Am. Chem. Soc. 1975, 97 6609–6615.
  * (4) S. Fajtlowicz, On conjectures of Graffiti–II, Congr. Numer. 60 (1987) 187–197.
  * (5) B. Zhou and N. Trinajstić, J. Math. Chem. 46 (2009) 1252.
  * (6) C. T. Martínez-Martínez, J. A. Mendez-Berḿudez, J. M. Rodríguez, and J. M. Sigarreta, Computational and analytical studies of the Randić index in Erdös–Rényi models, Appl. Math. Comput. 377, 125137 (2020).
  * (7) R. Aguilar-Sanchez, I. F. Herrera-Gonzalez, J. A. Mendez-Bermudez, and J. M. Sigarreta, Computational properties of general indices on random networks. Symmetry 12, 1341 (2020).
  * (8) C. T. Martínez-Martínez, J. A. Mendez-Bermudez, J. M. Rodríguez, and J. M. Sigarreta, Computational and analytical studies of the harmonic index in Erdös–Rényi models, MATCH Commun. Math. Comput. Chem. 85, 395–426 (2021).
  * (9) R. Aguilar-Sanchez, J. A. Mendez-Bermudez, F. A. Rodrigues, and J. M. Sigarreta-Almira, Topological versus spectral properties of random geometric graphs, Phys. Rev. E 102, 042306 (2020).
  * (10) H. Narumi and M. Katayama, Mem. Fac. Engin. Hokkaido Univ. 16 (1984) 209.
  * (11) R. Todeschini and V. Consonni, MATCH Commun. Math. Comput. Chem. 64 (2010) 359.
  * (12) R. Solomonoff and A. Rapoport, Connectivity of random nets. Bull. Math. Biophys. 13, 107–117 (1951).
  * (13) P. Erdös and A. Rényi, On random graphs. Publ. Math. (Debrecen) 6, 290–297 (1959).
  * (14) P. Erdös and A. Rényi, On the evolution of random graphs, Inst. of the Hung. Acad. of Sci. 5, 17–61 (1960); P. Erdös and A. Rényi, On the strength of connectedness of a random graph, Acta Mathematica Hungarica 12, 261–267 (1961).
  * (15) J. Dall and M. Christensen, Random geometric graphs, Phys. Rev. E 66, 016121 (2002).
  * (16) M. Penrose, Random Geometric Graphs; (Oxford University Press, Oxford, 2003).
  * (17) E. Estrada and M. Sheerin, Random rectangular graphs, Phys Rev. E 91, 042805 (2015).
  * (18) P. Bosch, Y. Quintana, J. M. Rodríguez, J. M. Sigarreta, Jensen-type inequalities for m-convex functions, to appear in Open Math.
  * (19) I. Gutman, I. Milovanović, E. Milovanović, Relations between Ordinary and Multiplicative Degree-Based Topological Indices, Filomat 32:8 (2018) 3031–3042.
  * (20) H. Kober, On the arithmetic and geometric means and on Hölder’s inequality, Proc. Amer. Math. Soc. 9 (1958) 452–459.
  * (21) M. Petrović’s, Sur Une Fonctionnelle, Publ. Math. Univ. Belgrade 1 (1932) 146–149.
  * (22) T. Réti, I. Gutman, Relations between ordinary and multiplicative Zagreb indices, Bull. Inter. Math. Virtual Inst. 2 (2012) 133–140.
  * (23) B. Zhou, I. Gutman, T. Aleksić, A note on Laplacian energy of graphs, MATCH Commun. Math. Comput. Chem. 60 (2008) 441–446.


[1]Hui Yin

1] Swinburne University of Technology, Victoria, Australia

2] Australian National University, Canberra, Australia

# A Rapid Review of Clustering Algorithms

<EMAIL_ADDRESS>Amir Aryani<EMAIL_ADDRESS>Stephen Petrie
<EMAIL_ADDRESS>Aishwarya Nambissan<EMAIL_ADDRESS>Aland
Astudillo<EMAIL_ADDRESS>Shengyuan Cao
<EMAIL_ADDRESS>[  [

###### Abstract

Clustering algorithms aim to organize data into groups or clusters based on
the inherent patterns and similarities within the data. They play an important
role in today’s life, such as in marketing and e-commerce, healthcare, data
organization and analysis, and social media. Numerous clustering algorithms
exist, with ongoing developments introducing new ones. Each algorithm
possesses its own set of strengths and weaknesses, and as of now, there is no
universally applicable algorithm for all tasks. In this work, we analyzed
existing clustering algorithms and classify mainstream algorithms across five
different dimensions: underlying principles and characteristics, data point
assignment to clusters, dataset capacity, predefined cluster numbers and
application area. This classification facilitates researchers in understanding
clustering algorithms from various perspectives and helps them identify
algorithms suitable for solving specific tasks. Finally, we discussed the
current trends and potential future directions in clustering algorithms. We
also identified and discussed open challenges and unresolved issues in the
field.

###### keywords:

Clustering, Clustering algorithm, Clustering analysis, Unsupervised learning,
Review

##  1 Introduction

With the rapid transformation of digital technology, access to information has
become a more prevalent aspect of daily life than ever before. Businesses and
individuals now have access to vast information, encompassing billions of
documents, videos, and audio files across the internet. Most businesses
operate in an interconnected web of data linked to multiple information
sources, capable of providing access to substantial data points. However,
while our computing capabilities are rapidly growing, the sheer volume of data
often challenges our capacity to transform disconnected data into useful
information, practical knowledge, and actionable insights. One established
solution is to leverage machine learning, particularly clustering methods.
Clustering algorithms are machine learning algorithms that seek to group
similar data points based on specific criteria, thereby revealing natural
structures or patterns within a dataset. The primary purpose is to divide the
data into subgroups, or clusters, where items within the same group are more
comparable to those in other sets. Clustering methods contribute to
advancements in various fields, such as information retrieval, recommendation
systems, and topic discovery.

Clustering algorithms are ubiquitous in daily life. They are used for spam
email classification, recommendation systems, customer segmentation for
targeted marketing, image processing for organizing images based on visual
similarities, and more. Clustering algorithms can cluster text-based data and
are also applicable to audio, video, and images. Audio clustering algorithms
use acoustic features to group files and can be used for tasks like genre
identification. Clustering video data facilitates tasks like recommendation
and summarization by organizing content by visual or thematic similarities. In
image analysis, clustering is essential for segmentation and content-based
retrieval tasks. Clustering algorithms also act as a means of detecting
anomalies, whether in network traffic, financial transactions, or medical
records. Their versatility underscores their importance in extracting patterns
and insights from a wide range of data.

Based on the nature of the learning process and the availability of labeled
data, clustering algorithms are primarily categorized into two types:

  * •

Semi-supervised Learning: This category provides a training dataset for each
data sample associated with a known cluster label. The algorithm observes the
patterns in the training dataset and then learns to assign new data points to
clusters. Such as Constrained K-Means [1], Semi-Supervised Fuzzy C-Means
(SSFCM) [2].

  * •

Unsupervised Learning: In this category, no labeled dataset is provided. The
algorithm identifies patterns and structures within the data and then groups
similar data samples based on inherent similarities in the features without
prior knowledge of the groupings. Usually, the total number of clusters in the
entire dataset is unknown. Examples of algorithms in this category include
K-Means [3, 4], Density-Based Spatial Clustering of Applications with Noise
(DBSCAN) [5], and Fuzzy C-Means (FCM) [6]. Several methods can be employed to
determine a suitable value, such as the elbow method, silhouette score, gap
statistics, as discussed in Section 3.4.

As new applications emerge, there is a growing demand for clustering
algorithms that can effectively handle different types of data and scenarios.
At the same time, with the rise of big data and complex data structures, such
as high-dimensional, heterogeneous data and large-scale datasets, adaptable
clustering algorithms are needed to handle these different types of data
effectively. Therefore, clustering methodologies constantly evolve, so it
becomes crucial to comprehensively survey and review existing literature to
understand the latest developments. Several notable reviews have contributed
significantly to this effort. Rui Xu and Wunsch, D. [7] looked at clustering
techniques for computer science, machine learning, and statistics datasets.
They demonstrated how to use these algorithms on a few benchmark datasets: the
traveling salesman issue, and bioinformatics—a relatively new topic garnering
much attention. They also discussed cluster validation, closeness measures,
and several related subjects. Xu and Tian [8] conducted a comprehensive survey
of clustering algorithms in 2015, covering a diverse range of techniques. The
authors categorized these algorithms based on their underlying principles,
characteristics, and applications. The survey includes a detailed and
comprehensive comparison of all discussed algorithms. Ezugwu et al., [9]
provided an up-to-date, methodical, and thorough analysis of both conventional
and cutting-edge clustering algorithms for various domains from a more
practical viewpoint. It covered the application of clustering to various
fields, such as big data, artificial intelligence, and robotics. The review
also focused on the remarkable role that clustering plays in a variety of
disciplines including education, marketing, medicine, biology, and
bioinformatics. The three works mentioned above are the most comprehensive and
highly cited research on clustering algorithms since 2000. Published in 2005,
2015, and 2022, these works have made significant contributions to the field.

In addition to these seminal works, other notable pieces mostly focus on
specific classifications or applications within clustering. Bora et al., [10]
conducted a comparative study between the fuzzy and hard clustering
algorithms. The focus is on assessing and contrasting the performance of these
clustering algorithms, providing insights into their strengths and
limitations. Sisodia et al., [11] explored diverse clustering algorithms in
the field of data mining, emphasizing fundamental aspects such as clustering
basics, requirements, classification, challenges, and the application domains
of these algorithms. A comprehensive comparative analysis of 9 well-known
clustering algorithms is provided by Rodriguez et al., [12]. The authors
evaluated the performance and characteristics of these algorithms through a
systematic evaluation, offering insights into their strengths and limitations.
This study contributes to understanding clustering methods and facilitates
informed choices based on specific application requirements.

In this work, we conduct a comprehensive summary of the existing clustering
algorithm literature and classify it from four different perspectives to help
users identify algorithms suitable for their specific tasks efficiently.
Furthermore, we discuss an overview of the current research status and
highlight future clustering technology trends.

##  2 Method

In this section, we describe the review methodology, detailing the keywords
used to collect publications and how they were screened for inclusion. We
defined a set of keywords related to our topic, such as “clustering”,
“clustering algorithm”, “clustering method”, “consensus clustering”,
“clustering technique”. After creating the keyword list, we conducted search
across three reputable academic databases, including Google Scholar, arXiv,
and Scopus. We employed Boolean operators (AND, OR) and truncation to refine
search queries. We chose Google Scholar because it includes papers that have
not yet been formally published, such as preprints. We observed that some
preprint publications received many citations at an early stage due to their
significant contributions to the research field. However, because some
journals require lengthy processing times before official publication, these
publications may remain in preprint status for a long time.

We filtered the gathered publications based on the following criteria:
publications written in English, published within the last five years, and
focusing on novel clustering techniques. Additionally, we removed duplicate
papers not directly related to clustering algorithms to ensure that the
remaining content comprises algorithm introductions, articles on algorithm
technology improvement, and application articles. Next, we reviewed the
titles, abstracts, and keywords, further screening the publications to narrow
down the selection. Once we concentrated on the full text of the selected
publications, our aim was to identify the underlying principles of the
algorithms, the algorithms used in their applications, the experimental
procedures, and key findings. We considered aspects such as experimental
design, sample size, and statistical methodologies to assess the dependability
of the results. Finally, the results (presented in the next section)
synthesize the patterns and trends found in the literature.

##  3 Results

In this section, we analyze the fundamental characteristics and approaches of
clustering algorithms and classify algorithms based on these principles, which
is also currently the most recognized classification method. Subsequently, we
classify the algorithms from different dimensions, such as the algorithm’s
capability to handle different dataset sizes, data point assignment to
clusters, the requirement to predefine the number of clusters, and application
area. This classification aims to guide users in choosing a suitable algorithm
according to the specific clustering tasks. The structure of the algorithm
classification system is visually presented in Figure 1.

Figure 1: Structure of the clustering algorithm classification, covering five
dimensions.

###  3.1 Algorithm Classification by Underlying Principles and Characteristics

Based on the fundamental characteristics and approaches to grouping data,
clustering algorithms can be grouped into the following five distinct subsets
[13, 14, 15] (summarised in Table 1):

  * •

Partition-Based Clustering (e.g. Figure 2): Partition-based clustering
algorithms partition data into non-overlapping clusters. The basic idea of
these clustering algorithms is to consider the center of data points as the
center of the corresponding cluster, which generally has low time complexity
and high computing efficiency. However, they are not well-suited for non-
convex data, are sensitive to outliers, can be easily drawn into local optima,
and require a predefined number of clusters, which can impact the performance
of clustering results.

Figure 2: Example of Partition-Based Clustering Algorithm: the left side
represents the original data, and the right side shows the resulting clusters
after applying the K-Means clustering algorithm. Each data sample is
classified into only one cluster.

  * •

Hierarchical-Based Clustering (e.g. Figure 3): The sole concept of
hierarchical clustering lies in the construction and analysis of a dendrogram.
A dendrogram is a tree-like structure that contains the relationship between
all the data points in the system. There is no need to specify a predefined
number of clusters. These algorithms can handle clusters of various shapes and
sizes. Once the dendrogram is constructed, a horizontal cut through the
structure defines individual clusters at the highest level in the system. Each
resulting child branch below this cut represents a distinct cluster, assigning
cluster membership to each data sample. However, hierarchical clustering needs
intensive computation, especially for large datasets, and the time complexity
is often higher than other clustering methods. This structure is sensitive to
noise and outliers, which can lead to sub-optimal clusters without the
appropriate handle.

Figure 3: Schematic diagram of a hierarchical clustering algorithm: the left
side displays a dendrogram constructed from the relationships between samples
in the dataset, while the right side illustrates the resulting clusters based
on the dendrogram.

  * •

Density-Based Clustering (e.g. Figure 4): Density-based algorithms aim to
identify clusters in high-dimensional regions of the feature space while also
detecting noise points as outliers. These algorithms have high clustering
efficiency, are sensitive to parameters, and are suitable for datasets of
arbitrary shapes. In the case of uneven spatial data density, the quality of
clustering results will decrease. Additionally, higher computing resources are
required when processing large datasets.

Figure 4: Schematic diagram of density-based clustering algorithm: the left
side represents the original data, and the right side shows the clustering
results after applying the algorithm. There are some outliers, represented by
gray dots in the graph.

  * •

Grid-Based Clustering (e.g. Figure 5): The fundamental principle of these
clustering algorithms is to partition the initial data space into a grid
structure of a predetermined size for clustering. While exhibiting low time
complexity, high scalability, and compatibility with parallel processing and
incremental updates, these algorithms do come with considerations. The
clustering outcomes prove sensitive to the grid size, where the pursuit of
heightened calculation efficiency may come at the expense of cluster quality
and overall clustering accuracy.

Figure 5: Schematic diagram of grid-based clustering algorithm: the left
figure represents the original data, and the right is a schematic grid
algorithm diagram. The grid might allow for arbitrary shapes or adaptations to
suit the characteristics of the data better. The identification of clusters is
typically done by defining rules or criteria based on the occupancy of grid
cells.

  * •

Model-Based Clustering (e.g. Figure 6): The basic idea is to select a
particular model for each cluster and find the best fitting for that model.
Model-based clustering algorithms presume data points are generated from a
probabilistic model and seek to identify the most appropriate model to explain
the data distribution. Diverse and well-developed models provide means to
describe data adequately, and each model has its unique characteristics that
may offer some notable benefits in some specific areas. However, overall, the
time complexity of the models is relatively high, the premise is not entirely
true, and the clustering result is dependent on the parameters of the models
that are chosen.

Figure 6: Schematic diagram of model-based clustering algorithm. The left side
represents the original data, and the right side shows the clustering results
after applying the Gaussian Mixture Model (GMM). Real-world clustering results
may vary due to different model choices, parameter settings, and other
factors.

Table 1: Algorithms classified by underlying principles and characteristics. Category |  Benefits |  Limitations |  Algorithm Examples
---|---|---|---
Partition-Based Clustering |  Efficient (low time complexity). Relatively simple to implement. |  Sensitive to outliers. Drawn to local optima. Requires predefined number of clusters. |  K-Means [3, 4], K-medoids [16, 17, 18], PAM [16], CLARA [19], CLARANS [20], FCM [6]
Hierarchical Clustering |  Does not require a predefined number of clusters. Dendrogram provides heirarchical information on clusters, subclusters. |  Inefficient (high time complexity). Dendrogram structure sensitive to noise and outliers. |  Agglomerative Clustering [21], Chameleon [22], BIRCH [23], CURE [24], Complete Linkage [25], ROCK [26], Single Linkage Clustering [25], Divisive Clustering [27]
Density-Based Clustering |  High clustering efficiency. Suitable for arbitrary cluster shapes. |  Decreased clustering quality for uneven spatial data density. Inefficient for large datasets. |  DBSCAN [5], DENCLUE [28], HDBSCAN [29], Mean-Shift Clustering [30], OPTICS [31]
Grid-Based Clustering |  Efficient (low time complexity). Suitable for arbitrary cluster shapes. |  Clusters sensitive to grid size. |  WaveCluster, CLIQUE [32], STDBSCAN [33], Grid-DBSCAN [5], STING [34]
Model-Based Clustering |  Allows for non-spherical clusters. Produces uncertainty of cluster membership. Does not require a predefined number of clusters. |  Relatively inefficient (high time complexity). |  GMM [35], Hidden Markov Models (HMM) [36], Latent Dirichlet Allocation (LDA) [37], Expectation-Maximization Clustering (EM) [38]

###  3.2 Algorithm Classification by Data Point Assignment to Clusters: Single
vs. Multi

Clustering algorithms can be broadly categorized based on how they assign data
points to clusters. This leads to two primary classifications: hard
clustering, where each data point is exclusively associated with a single
cluster, and soft clustering, where data points can be simultaneously
associated with multiple clusters. Below are some classic algorithms under
each category.

  * •

Hard clustering: K-Means, hierarchical clustering (agglomerative), DBSCAN,
OPTICS, K-Medoids, Spectral Clustering (K-way Normalized Cut) [39], BIRCH.

  * •

Soft clustering: Fuzzy C-Means (FCM), Gaussian Mixture Model (GMM),
Possibilistic C-Means (PCM) [40], Possibilistic Fuzzy C-Means (PFCM) [41],
Kernelized Fuzzy C-Means (KFCM) [42], Hierarchical Fuzzy Clustering (HFC) [43]

###  3.3 Algorithm Classified by Dataset Capacity

Algorithms differ in their ability to handle dataset size, and in this section
we classify all algorithms into three categories based on their processing
capabilities. Of course, defining what constitutes a small, medium, or large
dataset can be somewhat subjective, depending on the the context of your
specific task. Based on an overview of the open-source library for Python
111https://scikit-learn.org/stable/modules/clustering.html#overview-of-
clustering-methods and existing work, we categorize algorithms into three
groups according to their processing capabilities, as illustrated in Table 2.

Small Dataset: Typically, a small dataset might contain a few hundred to a few
thousand instances. It is a scale where the entire dataset can be easily
loaded into memory and processed without significant computational resources.

Medium Dataset: A medium-sized dataset could range from a few thousand to tens
of thousands of instances. It might require more sophisticated algorithms and
computational resources compared to a small dataset, but it is still
manageable.

Large Dataset: Large datasets typically contain hundreds of thousands to
millions (or more) instances. Handling such datasets often requires
specialized algorithms, distributed computing, or parallel processing due to
the sheer volume of data.

Table 2: Algorithms classified by dataset capacity. Dataset |  Algorithm Examples |  Comments
---|---|---
Small (up to a few thousand instances) |  K-Means, DBSCAN, Hierarchical clustering |  These algorithms are often efficient and can run on standard machines thereby avoiding the need for extensive computational resources.
Medium (thousands to hundreds of thousands) |  Optimized K-Means, GMM, Optimized Agglomerative clustering, Mean-Shift clustering |  The algorithms may utilize more sophisticated techniques to deal with the increased size of the dataset.
Large [44, 45] (hundreds of thousands or more) |  Mini-Batch K-Means, BIRCH, DBSCAN (optimized for large datasets), Hierarchical clustering (optimized for large datasets) |  These algorithms are tailored for parallel processing to efficiently tackle computational challenges in handling large datasets.

###  3.4 Algorithm Classification by Predefined Cluster Numbers

Not all clustering algorithms require a predefined number of clusters. There
are two main types of clustering algorithms:

Hard clustering: Algorithms in this category, such as K-Means, require the
user to specify the number of clusters beforehand.

Soft clustering or hierarchical clustering: It is not necessary to specify the
number of clusters in advance when using algorithms like hierarchical
clustering or GMMs. Clustering can be done at different levels of granularity
or number of clusters, and you can choose which to use post-hoc.

The biggest challenge in hard clustering is how to determine the optimal
number of clusters. Clustering results can be interpreted differently
depending on the number of clusters used, the granularity of patterns
discovered in the data, and the practicality of the solution. As a crucial
step in the clustering process, choosing the right number of clusters also
influences the insights derived from the analysis and the usefulness of the
clustered groups in real-life situations. There are some methods that can be
used to determine the optimal number of clusters.

  * •

Elbow Method 222https://en.wikipedia.org/wiki/Elbow_method_(clustering): Run
the clustering algorithm for a range of cluster numbers and plot the within-
cluster sum of squares (inertia) against the number of clusters. Look for an
“elbow” in the plot, where the rate of decrease in inertia slows down. The
point where this occurs is often considered the optimal number of clusters.
There are several publications that employ the elbow method to determine the
optimal number of clusters [46, 47, 48].

  * •

Silhouette Score 333https://en.wikipedia.org/wiki/Silhouette_(clustering):
Refers to a method of interpretation and validation of consistency within
clusters of data. The silhouette score measures how similar an object is to
its own cluster compared to other clusters. Choose the number of clusters that
maximizes the silhouette score. There are several publications that employ the
silhouette score to evaluate the optimal number of clusters [49, 50, 51]

  * •

Gap Statistics [52]: Compare the clustering performance on your dataset with
the performance on a random dataset (or with fewer clusters). Optimal clusters
should have a larger gap in performance compared to random clustering. Here
are some publications that employ gap statistic to determine the number of
clusters [53, 54, 55]

  * •

Dendrogram [56] in Hierarchical Clustering: If the task applies to a
hierarchical clustering algorithm, visualize the dendrogram and look for a
level where cutting it results in a reasonable number of distinct clusters.
There are some publications using dendrogram for clustering [57, 58]

###  3.5 Algorithm Classification by Area of Application

In this section, we will compare various key application areas and the
clustering algorithms predominantly utilized in each domain, shown in Table 3.
In fields like data mining and information retrieval, algorithms like K-Means
and DBSCAN are frequently employed for their efficiency in handling large
datasets. In contrast, areas like image analysis and bioinformatics often rely
on algorithms like Spectral Clustering and Hierarchical Clustering, which are
better suited for these fields’ intricate patterns and structures. It is worth
noting that new algorithms like AutoClass [59] and Superpixel [60] work well
in specific complicated scenarios.

Table 3: Areas of application of clustering algorithms. Area of Application |  Algorithm Examples
---|---
Data Mining |  K-Means, DBSCAN
Image Analysis |  Spectral Clustering, Mean Shift
Pattern Recognition |  Hierarchical Clustering, K-Means
Information Retrieval |  Hierarchical Clustering, K-Means, DBSCAN
Bioinformatics |  Hierarchical Clustering, Spectral Clustering
Image reconstruction |  K-Means, Superpixel, Expectation Maximization
Network Analysis |  Hierarchical Clustering, K-Means, DBSCAN, AutoClass

##  4 Evaluation Metrics

While most datasets lack ground truth labels for clustering algorithms,
methods exist for evaluating clustering quality. Evaluation metrics, crucial
for guiding the development, selection, and optimization of clustering
algorithms, make the process more systematic and informed. Data samples
transform into vectors in a high-dimensional space during the clustering
process. The distances between these vectors intricately reflect the overall
similarity, incorporating all relevant features within the data samples.
Therefore, “distances between points” are pivotal in forming clusters and
serve as a common standard for evaluating clustering performance. This concept
refers to numerical measures of dissimilarity or similarity between individual
data points, often calculated based on data features. Typical metrics include
Euclidean distance, Manhattan distance, or other similarity measures like
cosine similarity for text data. Figure 7 illustrates an example of K-Means
clustering, showcasing the distances between data points. Two types of
distances are depicted: one represents the distance between data samples
within the cluster (blue and orange dashed lines), while the other indicates
the distance between different cluster centers (green dashed line). The
distance between data points within a cluster is considerably smaller than
between data points and the centers of other clusters.

Figure 7: Example of K-Means clustering with two clusters, illustrating two
different types of distance between data points.

By emphasizing the significance of evaluation metrics and the role of
distances between points, the process of assessing and improving clustering
algorithms becomes more robust and meaningful. Evaluation metrics are
categorized into internal and external types. Internal metrics assess the
quality of clusters based solely on inherent data information, focusing on
factors like the compactness (cohesion) of data samples within a cluster and
the distinctiveness (separation ) between clusters. Examples include the
Silhouette Coefficient, Davies-Bouldin Index, Dunn’s Index, and Inertia (for
K-Means). External metrics require true class labels, evaluating alignment
with known labels using precision, recall, and mutual information. Such as the
Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), Fowlkes-
Mallows Index, Precision, Recall, and F1 Score. Internal metrics focus on
intrinsic properties, while external metrics rely on ground truth to evaluate
algorithm accuracy. The choice depends on data availability and clustering
goals.

###  4.1 Internal Evaluation Metrics

Internal evaluation metrics for clustering algorithms can evaluate the quality
of clusters based solely on the data’s intrinsic characteristics and the
clustering algorithm’s results, without using any external information, such
as ground truth labels. Various aspects of clustering quality can be measured
quantitatively with these metrics, such as compactness, separation, and
variance. When choosing and interpreting these metrics, it is essential to
consider the specific characteristics of the data and the goals of the
clustering task.

####  4.1.1 Silhouette Score

The Silhouette Score is a widely used internal evaluation metric for assessing
the quality of clusters produced by unsupervised clustering algorithms. It
measures how well-separated clusters are and provides an indication of the
appropriateness of the clustering solution. The Silhouette Score for a single
data point is calculated as the difference between the average distance from
the data point to other points in the same cluster (a) and the average
distance from the data point to points in the nearest neighboring cluster (b),
divided by the maximum of a and b. For a data point $i$, the formula is:

$S(i)=\frac{b(i)-a(i)}{max\left\\{{a(i),b(i)}\right\\}}$ (1)

The Silhouette Score ranges from -1 to 1, with higher values indicating
better-defined clusters. The Score close to 1 indicates that the data point is
well matched to its own cluster and poorly matched to neighboring clusters,
suggesting a good clustering. A Silhouette Score around 0 indicates
overlapping clusters. A Silhouette Score close to -1 indicates that the data
point may be assigned to the wrong cluster. The overall Silhouette Score for a
clustering solution is the average of the Silhouette Scores for all data
points.

####  4.1.2 Davies-Bouldin Index

The Davies-Bouldin Index is a metric used for evaluating the quality of
clustering solutions. It measures the compactness and separation between
clusters, aiming to find clusters that are well-separated from each other. The
formula of Davies-Bouldin Index is:

$DBI=\frac{1}{n_{c}}\sum_{i=1}^{n_{c}}max_{i\neq
j}(\frac{{avg_{radius_{i}}+avg_{radius_{j}}}}{distance(c_{i},c_{j})})$ (2)

where: $n_{c}$ is the number of clusters, $c_{i}$ and $c_{j}$ are the
centroids of clusters $i$ and $j$, ${avg_{-}radius}_{i}$ and
${avg_{-}radius}_{j}$ are the average distances from the centroid to the
points in custer $i$ and $j$, distance$(c_{i},c_{j})$ is the distance between
the centroids of clusters $i$ and $j$.

The Davies-Bouldin Index is based on the Euclidean distance, which assumes
clusters have a spherical shape and may not perform well when dealing with
clusters of irregular shapes. Also, the formula assumes equal-sized clusters,
so it might not be suitable for datasets with imbalanced cluster sizes. It may
not perform well if the true number of clusters is unknown or if the
clustering algorithm produces a different number of clusters. Despite these
limitations, the Davies-Bouldin Index can be a useful tool when the
assumptions align with the characteristics of the data and the goals of the
clustering analysis.

####  4.1.3 Dunn’s Index

The Dunn’s Index focuses on the compactness and separation of clusters. It
aims to find a balance between minimizing the diameter (maximum distance
between points) within a cluster and maximizing the distance between cluster
centroids. The index is defined as the ratio of the minimum inter-cluster
distance to the maximum intra-cluster diameter.

$DBI=\frac{1}{n}\sum_{i=1}^{n}max_{j\neq
i}(\frac{avg_{-}intra_{-}distance(C_{i})+avg_{-}intra_{-}{distance}(C_{j})}{distance(c_{i},c_{j})}$
(3)

while $n$ is the number of clusters, $C_{i}$ and $C_{j}$ are clusters,
$avg_{-}intra_{-}distance(C_{i})$ is the average distance within cluster
$C_{i}$, and $distance(c_{i},c_{j})$ is the distance between cluster centers
$c_{i}$ and$c_{j}$.

Dunn’s Index is sensitive to outliers, and highly dependent on the distance
metric. It assumes that clusters are spherical, so if the clusters have non-
spherical shapes, it may not accurately reflect the true separation between
clusters. Dunn’s Index produces a numeric result, but its interpretation as
“good” or “bad” is subjective and context-dependent in clustering problems.
Despite these shortcomings, Dunn’s Index can still be a valuable tool when
used judiciously and in conjunction with other evaluation metrics.

The above three are commonly used evaluation metrics, there are other less
popular evaluation metrics, such as Calinski-Harabasz Index [61] which
evaluates the ratio of the between-cluster variance to the within-cluster
variance, the higher values the better-defined clusters. Inertia (Within-
Cluster Sum of Squares) [62] which measures the sum of squared distances
between data points and their cluster’s centroid. Lower inertia suggests
denser, more compact clusters. Gap Statistics [52] which compares the
clustering quality of the dataset to that of a reference random dataset. A
larger gap indicates better clustering. CH Index (Cophenetic Correlation
Coefficient) [25] which measures the correlation between the cophenetic
distances in the dendrogram and the original distances. Higher CH Index
suggests better clustering.

###  4.2 External Evaluation Metrics (when ground truth is available)

####  4.2.1 Adjusted Rand Index (ARI)

The Adjusted Rand Index (ARI) is a widely used metric in cluster analysis and
machine learning for evaluating the similarity between two clustering
solutions. It measures the agreement between the true class labels and the
labels assigned by a clustering algorithm while correcting for chance. The
formula of ARI is:

$ARI=\frac{\text{RI}-\text{Expected RI}}{\text{Max(RI)}-\text{Expected RI}}$
(4)

Where $RI$ is the Rand Index, which measures the proportion of agreements
(both in the same cluster or both in different clusters) between the true and
predicted clusterings. $Expected_{RI}$ is the expected Rand Index under the
assumption of random clustering. It represents the expected value of $RI$ when
clustering is performed randomly. The $max(RI)$ term in the denominator
represents the maximum possible Rand Index, which normalizes the ARI to the
range [-1, 1].

The limitations of ARI are as follows: Sensitivity to Imbalanced Cluster
Sizes: ARI can be sensitive to imbalanced cluster sizes. If there is a
significant difference in the number of samples in different clusters, ARI may
be biased towards the larger clusters. Dependence on the Number of Clusters:
ARI assumes knowledge of the true number of clusters. If the true number of
clusters is unknown or if the clustering algorithm produces a different number
of clusters, ARI might not provide an accurate evaluation. Random Clustering
Assumption: ARI’s correction for chance assumes that cluster assignments are
made randomly. In some cases, especially with certain clustering algorithms or
data types, the assumption of random clustering might not hold. Limited to
Pairwise Comparisons: ARI is designed for pairwise cluster comparison and does
not provide information on the overall structure of multiple clusters. It may
not capture more complex relationships in the data. Dependency on Ground
Truth: ARI requires knowledge of true class labels, which may not be available
in unsupervised learning scenarios. In such cases, alternative evaluation
metrics may be needed. Despite these limitations, ARI remains a widely used
and interpretable metric for clustering evaluation. It is important to
consider these shortcomings in the context of your specific clustering task
and choose evaluation metrics accordingly.

####  4.2.2 Normalized Mutual Information (NMI)

Normalized Mutual Information provides a quantitative measure of the agreement
between the true class labels and the labels assigned by a clustering
algorithm, taking into account both precision and recall, offering a balanced
perspective on the quality of the clustering solution.

The formula of NMI is:

$NMI=\frac{2\quad I(Y;C)}{H(Y)+H(C)}$ (5)

where $Y$ is the set of true class labels, $C$ is the set of cluster labels
assigned by the algorithm, $I(Y;C)$ is the mutual information between $Y$ and
$C$, and $H(Y)$ and $H(C)$ are the entropies of $Y$ and $C$ respectively. NMI
ranges from 0 to 1, where 0 indicates no mutual information, and 1 implies
perfect agreement between the true and predicted labels. A higher NMI suggests
a better clustering solution in terms of capturing the underlying class
structure. NMI is a commonly used metric in most of clustering solution, as it
accounts for both homogeneity and completeness in clustering evaluation and
normalization helps in comparing NMI across datasets of different sizes. The
limitation of NMI is it assumes that each cluster corresponds to a single
class, which may not always be the case in real-world data.

##  5 Discussion

In recent years, there has been a shift in the focus of clustering algorithm
research from solely improving the underlying algorithms to more targeted
applications in specific fields. This shift is driven by the increasing
recognition of the diverse and complex data challenges in various domains.
Researchers are now actively exploring how clustering algorithms can be
effectively applied and adapted to address the unique requirements of fields
such as bioinformatics [63, 64, 65], healthcare [66, 50, 67], natural language
processing [68, 69], image and video processing [70, 71], social network
analysis [72, 73, 74], cybersecurity [75, 76, 77, 78], and anomaly detection
[32, 79, 80, 81]. The research community has concentrated its efforts on
customizing clustering solutions to align with particular application
contexts, thereby facilitating significant progress in domain-specific
applications of clustering methodologies. We observed that the COVID-19
pandemic has led to a significant increase in the use of clustering algorithms
in medical imaging and healthcare from 2021 to 2022. Amidst the swift
evolution of deep learning technology, a discernible trend has emerged in the
advancement of clustering algorithms. Specifically, there is an increasingly
obvious trend to incorporate deep learning technologies, such as neural
networks, into clustering algorithms to improve their performance [82, 83,
84], particularly in processing high-dimensional and complex data. K-Means is
one of the oldest and most well-known clustering algorithms, having achieved
popularity over the years for its simplicity and effectiveness in partitioning
data into clusters based on similarity. Despite its age, K-Means continues to
be widely used in various applications and is a familiar presence in
clustering technical publications. It often serves as a baseline method for
comparison with proposed approaches, and ongoing efforts are made to enhance
performance [85, 86, 87, 88]. Another noteworthy observation is the increasing
popularity of hybrid clustering methods [89, 90]. These methods combine
different clustering algorithms or integrate clustering with other machine
learning techniques. These approaches aim to leverage the strengths of
multiple methods for enhanced performance.

Currently, the primary challenge confronting clustering algorithms revolves
around determining the optimal number of clusters. Groups generated using
existing techniques often exhibit ambiguous clusters—instances wherein data is
grouped into unspecified categories for reasons unknown. If only one group is
present, it can be classified as an outlier, but occasionally, multiple groups
remain unidentified. This highlights a potential discrepancy between the
algorithm’s grouping of data and the subjective human interpretation of those
groups. In recent academic literature, several different clustering methods
are frequently used, each with its own strengths and applications. Therefore,
the choice of a clustering method is highly task-dependent. There is no single
method universally outperforming others across all types of data and
applications. Our review classifies algorithms from multiple perspectives and
can assist users in choosing the appropriate clustering algorithm for a given
application.

## Acknowledgement

This research was supported by the Australian Government through the
Australian Research Council’s Industrial Transformation Training Centre for
Information Resilience (CIRES) project number IC200100022.

We would like to express our sincere gratitude to Junliang Yu, Luhan Cheng,
Nakul Nambiar, Yunzhong Zhang, Shuyi Shen, and Zhuochen Wu for their valuable
contributions and insightful feedback during the development of this work.

## Declarations

Conflict of interest The authors declare that they have no known competing
financial interests or personal relationships that could have appeared to
influence the work reported in this paper.

## References

  *   * Wagstaff et al. [2001] Wagstaff, K., Cardie, C., Rogers, S., Schrödl, S., et al.: Constrained k-means clustering with background knowledge. In: Icml, vol. 1, pp. 577–584 (2001)
  * Benkhalifa et al. [1999] Benkhalifa, M., Bensaid, A., Mouradi, A.: Text categorization using the semi-supervised fuzzy c-means algorithm. In: 18th International Conference of the North American Fuzzy Information Processing Society-NAFIPS (Cat. No. 99TH8397), pp. 561–565 (1999). IEEE
  * Lloyd [1982] Lloyd, S.P.: Least squares quantization in pcm. IEEE Transactions on Information Theory 28(2), 129–137 (1982) https://doi.org/10.1109/TIT.1982.1056489
  * Forgy [1965] Forgy, E.W.: Cluster analysis of multivariate data: Efficiency versus interpretability of classifications. Biometrics 21(3), 768–769 (1965)
  * Ester et al. [1996] Ester, M., Kriegel, H.-P., Sander, J., Xu, X.: A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In: Simoudis, E., Han, J., Fayyad, U.M. (eds.) Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), pp. 226–231. AAAI Press, ??? (1996). https://doi.org/10.1.1.121.9220
  * Bezdek et al. [1984] Bezdek, J.C., Ehrlich, R., Full, W.: Fcm: The fuzzy c-means clustering algorithm. Computers & geosciences 10(2-3), 191–203 (1984)
  * Xu and Wunsch [2005] Xu, R., Wunsch, D.: Survey of clustering algorithms. IEEE Transactions on Neural Networks 16(3), 645–678 (2005) https://doi.org/10.1109/TNN.2005.845141
  * Xu and Tian [2015] Xu, D., Tian, Y.: A comprehensive survey of clustering algorithms. Annals of Data Science 2, 165–193 (2015) https://doi.org/10.1007/s40745-015-0040-1
  * Ezugwu et al. [2022] Ezugwu, A.E., Ikotun, A.M., Oyelade, O.O., Abualigah, L., Agushaka, J.O., Eke, C.I., Akinyelu, A.A.: A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects. Engineering Applications of Artificial Intelligence 110, 104743 (2022) https://doi.org/10.1016/j.engappai.2022.104743
  * Bora and Gupta [2014] Bora, D.J., Gupta, A.K.: A comparative study between fuzzy clustering algorithm and hard clustering algorithm. CoRR abs/1404.6059 (2014) 1404.6059
  * Sisodia et al. [2012] Sisodia, D., Singh, L., Sisodia, S., Saxena, K.: Clustering techniques: a brief survey of different clustering algorithms. International Journal of Latest Trends in Engineering and Technology (IJLTET) 1(3), 82–87 (2012)
  * Rodriguez et al. [2019] Rodriguez, M.Z., Comin, C.H., Casanova, D., Bruno, O.M., Amancio, D.R., Costa, L.d.F., Rodrigues, F.A.: Clustering algorithms: A comparative approach. PloS one 14(1), 0210236 (2019) https://doi.org/10.1371/journal.pone.0210236
  * Zhou et al. [2022] Zhou, S., Xu, H., Zheng, Z., Chen, J., Bu, J., Wu, J., Wang, X., Zhu, W., Ester, M., et al.: A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions. arXiv preprint arXiv:2206.07579 (2022) https://doi.org/10.48550/arXiv.2206.07579
  * Sajana et al. [2016] Sajana, T., Rani, C.S., Narayana, K.: A survey on clustering techniques for big data mining. Indian journal of Science and Technology 9(3), 1–12 (2016) https://doi.org/10.17485/ijst/2016/v9i3/75971
  * Berkhin [2006] Berkhin, P.: A survey of clustering data mining techniques. In: Grouping Multidimensional Data: Recent Advances in Clustering, pp. 25–71. Springer, ??? (2006). https://doi.org/10.1007/3-540-28349-8_2
  * Kaufman and Rousseeuw [1990] Kaufman, L., Rousseeuw, P.J.: Partitioning Around Medoids (Program PAM), pp. 68–125. John Wiley & Sons, Inc., Hoboken, NJ, USA (1990). https://doi.org/10.1002/9780470316801.ch2
  * Schubert and Rousseeuw [2021] Schubert, E., Rousseeuw, P.J.: Fast and eager k-medoids clustering: O(k) runtime improvement of the pam, clara, and clarans algorithms. Information Systems 101, 101804 (2021) https://doi.org/10.1016/j.is.2021.101804 arXiv:arXiv:2008.05171 [cs.DS]
  * Rdusseeun and Kaufman [1987] Rdusseeun, L., Kaufman, P.: Clustering by means of medoids. In: Proceedings of the Statistical Data Analysis Based on the L1 Norm Conference, Neuchatel, Switzerland, vol. 31 (1987)
  * Kaufman and Rousseeuw [2009] Kaufman, L., Rousseeuw, P.J.: Finding Groups in Data: an Introduction to Cluster Analysis. John Wiley & Sons, ??? (2009)
  * Ng and Han [2002] Ng, R.T., Han, J.: Clarans: A method for clustering objects for spatial data mining. IEEE Transactions on Knowledge and Data Engineering 14(5), 1003–1016 (2002) https://doi.org/10.1109/TKDE.2002.1033770
  * Johnson [1967] Johnson, S.C.: Hierarchical clustering schemes. Psychometrika 32(3), 241–254 (1967)
  * Karypis et al. [1999] Karypis, G., Han, E.-H., Kumar, V.: Chameleon: Hierarchical clustering using dynamic modeling. computer 32(8), 68–75 (1999)
  * Zhang et al. [1996] Zhang, T., Ramakrishnan, R., Livny, M.: BIRCH: An Efficient Data Clustering Method for Very Large Databases. In: Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. SIGMOD ’96, pp. 103–114 (1996). https://doi.org/10.1145/233269.233324
  * Guha et al. [1998] Guha, S., Rastogi, R., Shim, K.: CURE: An Efficient Clustering Algorithm for Large Databases. Information Systems 26(1), 35–58 (1998) https://doi.org/10.1016/S0306-4379(01)00008-4
  * Sneath and Sokal [1973] Sneath, P.H., Sokal, R.R.: Numerical Taxonomy: The Principles and Practice of Numerical Classification. W. H. Freeman, ??? (1973)
  * Guha et al. [2000] Guha, S., Rastogi, R., Shim, K.: Rock: A robust clustering algorithm for categorical attributes. Information systems 25(5), 345–366 (2000)
  * Savaresi et al. [2002] Savaresi, S.M., Boley, D.L., Bittanti, S., Gazzaniga, G.: Cluster selection in divisive clustering algorithms. In: Proceedings of the 2002 SIAM International Conference on Data Mining, pp. 299–314 (2002). SIAM
  * Hinneburg and Keim [1998] Hinneburg, A., Keim, D.A.: An efficient approach to clustering in large multimedia databases with noise. In: Knowledge Discovery and Datamining (KDD’98), pp. 58–65 (1998)
  * Campello et al. [2013] Campello, R.J., Moulavi, D., Sander, J.: Density-based clustering based on hierarchical density estimates. In: Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 160–172 (2013). Springer
  * Comaniciu and Meer [2002] Comaniciu, D., Meer, P.: Mean shift: A robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(5), 603–619 (2002)
  * Ankerst et al. [1999] Ankerst, M., Breunig, M., Kriegel, H.-P., Sander, J.: Optics: Ordering points to identify the clustering structure. In: Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, vol. 28, pp. 49–60 (1999). ACM
  * Agrawal et al. [1998] Agrawal, R., Gehrke, J., Gunopulos, D., Raghavan, P.: Automatic subspace clustering of high dimensional data for data mining applications. In: Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, vol. 27, pp. 94–105 (1998). ACM
  * Birant and Kut [2007] Birant, D., Kut, A.: St-dbscan: An algorithm for clustering spatial–temporal data. Data & knowledge engineering 60(1), 208–221 (2007) https://doi.org/10.1016/j.datak.2006.01.013
  * Wang et al. [1997] Wang, W.-C., Yang, J., Muntz, R.: Sting: a statistical information grid approach to spatial data mining. In: VLDB, pp. 186–195 (1997)
  * Rasmussen [1999] Rasmussen, C.E.: The infinite gaussian mixture model. In: Advances in Neural Information Processing Systems, vol. 12, pp. 554–560 (1999)
  * Rabiner and Juang [1986] Rabiner, L., Juang, B.: An introduction to hidden markov models. ieee assp magazine 3(1), 4–16 (1986)
  * Blei et al. [2003] Blei, D.M., Ng, A.Y., Jordan, M.I.: Latent dirichlet allocation. Journal of machine Learning research 3(Jan), 993–1022 (2003)
  * Dempster et al. [1977] Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the em algorithm. Journal of the royal statistical society: series B (methodological) 39(1), 1–22 (1977)
  * Dhillon et al. [2004] Dhillon, I.S., Guan, Y., Kulis, B.: Kernel k-means: spectral clustering and normalized cuts. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 551–556 (2004)
  * Krishnapuram and Keller [1996] Krishnapuram, R., Keller, J.M.: The possibilistic c-means algorithm: insights and recommendations. IEEE transactions on Fuzzy Systems 4(3), 385–393 (1996)
  * Pal et al. [2005] Pal, N.R., Pal, K., Keller, J.M., Bezdek, J.C.: A possibilistic fuzzy c-means clustering algorithm. IEEE transactions on fuzzy systems 13(4), 517–530 (2005)
  * Zhang and Chen [2004] Zhang, D.-Q., Chen, S.-C.: A novel kernelized fuzzy c-means algorithm with application in medical image segmentation. Artificial intelligence in medicine 32(1), 37–50 (2004)
  * Di Gesú [1994] Di Gesú, V.: Integrated fuzzy clustering. Fuzzy Sets and Systems 68(3), 293–308 (1994)
  * Shirkhorshidi et al. [2014] Shirkhorshidi, A.S., Aghabozorgi, S., Wah, T.Y., Herawan, T.: Big data clustering: a review. In: Computational Science and Its Applications–ICCSA 2014: 14th International Conference, Guimarães, Portugal, June 30–July 3, 2014, Proceedings, Part V 14, pp. 707–720 (2014). https://doi.org/10.1007/978-3-319-09156-3_49 . Springer
  * Kurasova et al. [2014] Kurasova, O., Marcinkevicius, V., Medvedev, V., Rapecka, A., Stefanovic, P.: Strategies for big data clustering. In: 2014 IEEE 26th International Conference on Tools with Artificial Intelligence, pp. 740–747 (2014). https://doi.org/10.1109/ICTAI.2014.115 . IEEE
  * Syakur et al. [2018] Syakur, M., Khotimah, B., Rochman, E., Satoto, B.D.: Integration k-means clustering method and elbow method for identification of the best customer profile cluster. In: IOP Conference Series: Materials Science and Engineering, vol. 336, p. 012017 (2018). IOP Publishing
  * Bholowalia and Kumar [2014] Bholowalia, P., Kumar, A.: Ebk-means: A clustering technique based on elbow method and k-means in wsn. International Journal of Computer Applications 105(9) (2014)
  * Marutho et al. [2018] Marutho, D., Handaka, S.H., Wijaya, E., et al.: The determination of cluster number at k-mean using elbow method and purity evaluation on headline news. In: 2018 International Seminar on Application for Technology of Information and Communication, pp. 533–538 (2018). https://doi.org/%****␣sn-article.bbl␣Line␣725␣****10.1109/ISEMANTIC.2018.8549751 . IEEE
  * Shutaywi and Kachouie [2021] Shutaywi, M., Kachouie, N.N.: Silhouette analysis for performance evaluation in machine learning with applications to clustering. Entropy 23(6), 759 (2021) https://doi.org/10.3390/e23060759
  * Ogbuabor and Ugwoke [2018] Ogbuabor, G., Ugwoke, F.: Clustering algorithm for a healthcare dataset using silhouette score value. Int. J. Comput. Sci. Inf. Technol 10(2), 27–37 (2018) https://doi.org/10.5121/ijcsit.2018.10203
  * Shahapure and Nicholas [2020] Shahapure, K.R., Nicholas, C.: Cluster quality analysis using silhouette score. In: 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA), pp. 747–748 (2020). https://doi.org/10.1109/DSAA49011.2020.00096 . IEEE
  * Tibshirani et al. [2001] Tibshirani, R., Walther, G., Hastie, T.: Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 63(2), 411–423 (2001)
  * Yan and Ye [2007] Yan, M., Ye, K.: Determining the number of clusters using the weighted gap statistic. Biometrics 63(4), 1031–1037 (2007) https://doi.org/10.1111/j.1541-0420.2007.00784.x
  * El-Mandouh et al. [2019] El-Mandouh, A.M., Abd-Elmegid, L.A., Mahmoud, H.A., Haggag, M.H.: Optimized k-means clustering model based on gap statistic. International Journal of Advanced Computer Science and Applications 10(1) (2019) https://doi.org/10.14569/IJACSA.2019.0100124
  * Mohajer et al. [2011] Mohajer, M., Englmeier, K.-H., Schmid, V.J.: A comparison of gap statistic definitions with and without logarithm function. arXiv preprint arXiv:1103.4767 (2011)
  * CaliŃski [2014] CaliŃski, T.: Dendrogram. Wiley StatsRef: Statistics Reference Online (2014)
  * Langfelder et al. [2008] Langfelder, P., Zhang, B., Horvath, S.: Defining clusters from a hierarchical cluster tree: the dynamic tree cut package for r. Bioinformatics 24(5), 719–720 (2008)
  * Nielsen and Nielsen [2016] Nielsen, F., Nielsen, F.: Hierarchical clustering. Introduction to HPC with MPI for Data Science, 195–211 (2016) https://doi.org/10.1007/978-3-319-21903-5_8
  * Li et al. [2022] Li, H., Brouwer, C.R., Luo, W.: A universal deep neural network for in-depth cleaning of single-cell rna-seq data. Nature Communications 13(1), 1901 (2022) https://doi.org/%****␣sn-article.bbl␣Line␣875␣****10.1101/2020.12.04.412247
  * Asante-Mensah et al. [2023] Asante-Mensah, M.G., Phan, A.H., Ahmadi-Asl, S., Aghbari, Z.A., Cichocki, A.: Image Reconstruction using Superpixel Clustering and Tensor Completion (2023). https://doi.org/10.48550/arXiv.2305.09564
  * Caliński and Harabasz [1974] Caliński, T., Harabasz, J.: A dendrite method for cluster analysis. Communications in Statistics 3(1), 1–27 (1974) https://doi.org/10.1080/03610927408827101
  * MacQueen et al. [1967] MacQueen, J., et al.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297 (1967). Oakland, CA, USA
  * Karim et al. [2021] Karim, M.R., Beyan, O., Zappa, A., Costa, I.G., Rebholz-Schuhmann, D., Cochez, M., Decker, S.: Deep learning-based clustering approaches for bioinformatics. Briefings in Bioinformatics 22(1), 393–415 (2021) https://doi.org/10.1093/bib/bbz170
  * Higham et al. [2007] Higham, D.J., Kalna, G., Kibble, M.: Spectral clustering and its use in bioinformatics. Journal of computational and applied mathematics 204(1), 25–37 (2007) https://doi.org/%****␣sn-article.bbl␣Line␣950␣****10.1016/j.cam.2006.04.026
  * Olman et al. [2008] Olman, V., Mao, F., Wu, H., Xu, Y.: Parallel clustering algorithm for large data sets with applications in bioinformatics. IEEE/ACM Transactions on Computational Biology and Bioinformatics 6(2), 344–352 (2008) https://doi.org/10.1109/TCBB.2007.70272
  * Haraty et al. [2015] Haraty, R.A., Dimishkieh, M., Masud, M.: An enhanced k-means clustering algorithm for pattern discovery in healthcare data. International Journal of distributed sensor networks 11(6), 615740 (2015) https://doi.org/10.1155/2015/6157
  * Delias et al. [2015] Delias, P., Doumpos, M., Grigoroudis, E., Manolitzas, P., Matsatsinis, N.: Supporting healthcare management decisions via robust clustering of event logs. Knowledge-Based Systems 84, 203–213 (2015) https://doi.org/10.1016/j.knosys.2015.04.012
  * Yang et al. [2019] Yang, S., Huang, G., Cai, B.: Discovering topic representative terms for short text clustering. IEEE Access 7, 92037–92047 (2019)
  * Yin et al. [2021] Yin, H., Song, X., Yang, S., Huang, G., Li, J.: Representation learning for short text clustering. In: Web Information Systems Engineering–WISE 2021: 22nd International Conference on Web Information Systems Engineering, WISE 2021, Melbourne, VIC, Australia, October 26–29, 2021, Proceedings, Part II 22, pp. 321–335 (2021). Springer
  * Cao et al. [2023] Cao, L., Zhao, Z., Wang, D.: 5\. Clustering Algorithms. Springer, Singapore (2023). https://doi.org/10.1007/978-981-99-1533-0_5
  * Dhanachandra et al. [2015] Dhanachandra, N., Manglem, K., Chanu, Y.J.: Image segmentation using k-means clustering algorithm and subtractive clustering algorithm. Procedia Computer Science 54, 764–771 (2015) https://doi.org/10.1016/j.procs.2015.06.090
  * Jose and Babu [2019] Jose, T., Babu, S.S.: Detecting spammers on social network through clustering technique. Journal of Ambient Intelligence and Humanized Computing, 1–15 (2019) https://doi.org/10.1007/s12652-019-01541-6
  * Zhao and Zhang [2011] Zhao, P., Zhang, C.-Q.: A new clustering method and its application in social networks. Pattern Recognition Letters 32(15), 2109–2118 (2011) https://doi.org/10.1016/j.patrec.2011.06.008
  * Li et al. [2017] Li, P., Dau, H., Puleo, G., Milenkovic, O.: Motif clustering and overlapping clustering for social network analysis. In: IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, pp. 1–9 (2017). https://doi.org/%****␣sn-article.bbl␣Line␣1100␣****10.1109/INFOCOM.2017.8056956
  * Alom and Taha [2017] Alom, M.Z., Taha, T.M.: Network intrusion detection for cyber security using unsupervised deep learning approaches. In: 2017 IEEE National Aerospace and Electronics Conference (NAECON), pp. 63–69 (2017). https://doi.org/10.1109/NAECON.2017.8268746
  * Das and Morris [2017] Das, R., Morris, T.H.: Machine learning and cyber security. In: 2017 International Conference on Computer, Electrical & Communication Engineering (ICCECE), pp. 1–7 (2017). https://doi.org/10.1109/ICCECE.2017.8526232
  * Kolini and Janczewski [2017] Kolini, F., Janczewski, L.: Clustering and topic modelling: A new approach for analysis of national cyber security strategies (2017)
  * Landauer et al. [2020] Landauer, M., Skopik, F., Wurzenberger, M., Rauber, A.: System log clustering approaches for cyber security applications: A survey. Computers & Security 92, 101739 (2020) https://doi.org/10.1016/j.cose.2020.101739
  * Syarif et al. [2012] Syarif, I., Prugel-Bennett, A., Wills, G.: Unsupervised clustering approach for network anomaly detection. In: Networked Digital Technologies. Communications in Computer and Information Science, vol. 293. Springer, ??? (2012). https://doi.org/10.1007/978-3-642-30507-8_13
  * Markovitz et al. [2020] Markovitz, A., Sharir, G., Friedman, I., Zelnik-Manor, L., Avidan, S.: Graph embedded pose clustering for anomaly detection. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10539–10547 (2020)
  * Aggarwal and Zhai [2012] Aggarwal, C.C., Zhai, C.: A survey of text clustering algorithms. Mining text data, 77–128 (2012) https://doi.org/10.1007/978-1-4614-3223-4_4
  * Aljalbout et al. [2018] Aljalbout, E., Golkov, V., Siddiqui, Y., Strobel, M., Cremers, D.: Clustering with deep learning: Taxonomy and new methods. arXiv preprint arXiv:1801.07648 (2018) https://doi.org/10.48550/arXiv.1801.01587
  * Shaham et al. [2018] Shaham, U., Stanton, K., Li, H., Nadler, B., Basri, R., Kluger, Y.: Spectralnet: Spectral clustering using deep neural networks. arXiv preprint arXiv:1801.01587 (2018) https://doi.org/10.48550/arXiv.1801.01587
  * Bianchi et al. [2020] Bianchi, F.M., Grattarola, D., Alippi, C.: Spectral clustering with graph neural networks for graph pooling. In: III, H.D., Singh, A. (eds.) Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 119, pp. 874–883. PMLR, ??? (2020). https://proceedings.mlr.press/v119/bianchi20a.html
  * Sinaga and Yang [2020] Sinaga, K.P., Yang, M.-S.: Unsupervised k-means clustering algorithm. IEEE Access 8, 80716–80727 (2020) https://doi.org/10.1109/ACCESS.2020.2988796
  * Yu et al. [2018] Yu, S.-S., Chu, S.-W., Wang, C.-M., Chan, Y.-K., Chang, T.-C.: Two improved k-means algorithms. Applied Soft Computing 68, 747–755 (2018) https://doi.org/10.1016/j.asoc.2017.08.032
  * Fard et al. [2020] Fard, M.M., Thonet, T., Gaussier, E.: Deep k-means: Jointly clustering with k-means and learning representations. Pattern Recognition Letters 138, 185–192 (2020) https://doi.org/10.1016/j.patrec.2020.07.028
  * Ran et al. [2021] Ran, X., Zhou, X., Lei, M., Tepsan, W., Deng, W.: A novel k-means clustering algorithm with a noise algorithm for capturing urban hotspots. Applied Sciences 11(23), 11202 (2021) https://doi.org/10.3390/app112311202
  * Kumar et al. [2016] Kumar, D., Bezdek, J.C., Palaniswami, M., Rajasegarar, S., Leckie, C., Havens, T.C.: A hybrid approach to clustering in big data. IEEE Transactions on Cybernetics 46(10), 2372–2385 (2016) https://doi.org/10.1109/TCYB.2015.2477416
  * You et al. [2023] You, Y.Z., Pan, Y., Ma, Z., Zhang, L., Xiao, S., Zhang, D.D., Dang, S., Zhao, S.R., Wang, P., Dong, A.-J., et al.: Applying hybrid clustering in pulsar candidate sifting with multi-modality for fast survey. Research in Astronomy and Astrophysics (2023) https://doi.org/10.1088/1674-4527/ad0c28