This procedure is repeated until there is only one cluster left or the size of the
cluster has reached the limit. Each round can take as many as five steps if it
is a cluster with Level > 0, or two steps if it is a cluster of Level = 0.
After a cluster has selected its best outgoing edge, it sends a CONNECT
request to the other side of the edge. Two clusters join together when (1) Two
clusters of Level L merge into one cluster of Level L+1; (2) a cluster of lower
354
Chpater 14 Performance Comparison of Clustering Schemes
level LL is absorbed by another cluster of higher level LH. In the first case,
the new clusterhead will be one of the two nodes connected to the merging
edge; in the second case, the final cluster level will remain at LH, and the
cluster head will remain the same. In both cases, if a join occurs, the previous
cluster head(s) will update the new cluster head with the list of members, so
the cluster head always has the most recent information.
A join attempt will fail if the cluster receiving the CONNECT request has
a lower level, or it has chosen a di?®erent edge to merge over, or it has stopped
clustering due to its size.
The clustering algorithm is terminated when all nodes in a cluster have
no outgoing edge or the cluster size n hits the limit 2 (1 ??’ ?±)N, where N is
the desired cluster size and 0 < ?± < 0.5. Upon termination of the clustering
algorithm, it is possible that a small number of clusters are undersized.
Pages:
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567