ABSTRACT
Another distinction is whether the clusters formed overlap or not. In graph partitioning, clusters do not overlap, that is, they do not have common members whereas they may overlap in graph clustering. Whether the number of clusters is determined beforehand or not also affects the design of clustering algorithms. If the number of clusters is not known a priori, we need to specify an objective function to test and when this function reaches a desired value, the algorithm terminates. There are various parameters called validation indices to evaluate the quality (goodness) of a graph-based clustering. One such measure which is also applicable in data clustering is based on the intra-cluster distance which is the average distance of the vertices to the cluster center ci defined as below :
dintra = 1 n
∑
v∈Ci d(v,ci) (8.1)
number of distance is defined as the minimum distance between the centers of all clusters as dinter = min(d(ci,c j)),1 ≤ i, j ≤ k. The ratio of these two parameters indicates how close the nodes in a cluster are and how far the clusters are from each other [18]. Another measure is based on the density of the graph in which case subgraphs that have a density greater than a given threshold are searched.
