
## 6 Conclusion

We extended Elkan's k-means from vectors to graphs. Elkan's k-means exploits the triangle inequality to avoid graph distance calculations. Experimental results show that standard and Elkan's k-means for graphs perform equally with respect to solution quality, but Elkan's k-means outperforms standard k-means with respect to speed if there is a cluster structure in the data. The speedup factor of both accelerations increases slightly with the number k of centroids. This contribution is a rst step in accelerating clustering algorithms that directly operate in the domain of graphs. Future work aims at accelerating incremental clustering methods.

## A The Silhouette Index

Suppose that S = {X1*, . . . , X*m} is a sample of m patterns. Let C = {C1*, . . . ,* Ck}
be a partition of S consisting of k disjoint clusters with

$$S=\bigcup_{i=1}^{k}c_{i}.$$
$\downarrow$ . 
We assume that D is the underlying distance function dened on S. The distance between two subsets U, U
0 ⊆ S is dened by D (U, U
0) = min {D (*X, X*0) : X ∈ U, X0 ∈ U0} .

If U = {X} consists of a singleton, we simply write D (X, U
0) instead of D ({X}, U
0).

Let

$D_{\rm avg}\ (X,\mathcal{U})$). 
denote the average distance between pattern X ∈ S and subset *U ⊆ S*. Suppose that pattern Xi ∈ S is a member of cluster Cm(i) ∈ C. By C
0 m(i) we denote the set Cm(i) \ {Xi}. For each pattern Xi ∈ S let

$$a_{i}=D_{\mathrm{avg}}\left(X,{\mathcal{C}}_{m(i)}^{\prime}\right)$$

be the average distance between pattern Xi and subset C
0 m(i)
. By

$$b_{i}=\operatorname*{min}_{j\neq m(i)}D_{\mathrm{avg}}\left(X_{i},{\mathcal{C}}_{j}\right)$$

we denote the minimum average distance between pattern Xi and all clusters from C not containing Xi. The silhouette width of Xiis dened as

$$s_{i}={\frac{b_{i}-a_{i}}{\operatorname*{max}\left(b_{i},a_{i}\right)}}.$$
