The number of identified clusters depends on input p, but it is unknown which value of p will give best clustering solution for a given data set. Generally, cluster validation techniques (usually based on validation indices) [3] are used to evaluate which clustering solution is optimal for a data set. AP algorithm need give a series of clustering solutions with different NCs, among which the optimal clustering solution is found by a cluster validation index. There is no exact corresponding relation between the p and output NC, so we design the method of scanning space of p to obtain different NCs. 

The adaptive p-scanning technique is designed as follows: (1) specify a large p to start the algorithm; (2) 
an iteration runs and gives K exemplars; (3) check whether K exemplars converge (the condition is that every exemplar satisfies preset continuously unchanging times v); (4) go to step (5) if K exemplars converge, otherwise go to step (2); (5) decrease the p by step ps if K exemplars converge too in additional dy iterations (this is for more reliable convergence), otherwise go to step (2); (6) go to step (2). 

Thus, a series of clustering results with different NCs can be gained through scanning p, and the scanning of p space is designed inside the iterative process to keep the advantage of speed. To avoid possible repeated computation, in the p-scanning process we continue to calculate R(i,k) and A(i,k) based on (or using) the current values of R(i,j) and A(i,j) after each reduction of p (then S(i,i)=p(i) is changed but other elements of S
are unchanged). 

It is the key to select a proper decreasing step for the adaptive p-scanning technology. According to our experience, the decreasing step may be set to be ps=pm/100. This is a compromise design, which considers both cases: the algorithm runs slow when |ps| is too small, and the algorithm possibly miss the NC of the inherent cluster structure when |ps| is too big. Nevertheless, this fixed decreasing step cannot meet the different cases of big NC and small NC. Considering that big NC is more sensitive to ps than that of small NC, we design the adaptive decreasing step: ps=0.01pm/q, where decreasing parameter q = 0.1 K+50 . 

Thus, the q is adjusted dynamically with K, and the ps is smaller when K is bigger, while the ps is larger when K is smaller.

In order to check whether the convergence condition is satisfied, another monitoring window B (similar to that in adaptive damping method) is adopted to record the continuously unchanging times v of K exemplar, and the window size is set to be v=40, which is consistent with default convergence times 50 in AP [1] (v=40 pluses delay times of 10). 

It is important to specify the scanning scope, and a smaller scope is preferred for less running time. The p space [-∞, 0] corresponds to NC space [1, n]. For the clustering of n data points, it is reasonable to regard the square of n as the upper limit of the optimal NC [4]. In the following experiments we find: K1 at the first convergence equals or is over n when initial p=pm/2 is set, and the NCs searched by the algorithm are much bigger than n (since every data point is regarded as an exemplar when AP starts). Hence, we set initial p=pm/2. The minimal NC (K=2) determines the lower limit of p, i.e., reducing p until K=2. The large maxits=50000 is set so that the maximal iteration times *maxits* does not influence whether the algorithm reaches K=2. 

Finally, an acceleration technique of p-scanning is needed to save running time. As some NCs correspond to a large scope of p, the large reduction of p is needed to change NC. In this case, we may increase the decreasing step of p to obtain smaller NCs rapidly. The acceleration technique of p-scanning is designed as follows: (1) the iteration runs once; (2) check whether K exemplars converge; if yes, go to (3), otherwise set b=0 and go to (1); (3) the iteration continues dy=10 times; (4) check whether K exemplars converge; if yes, set b=b+1, otherwise go to (1); (5) set p = p+b×ps, and go to (3). The pseudo codes of the adaptive p-scanning technology are listed in the Table 2. 

Now the adaptive AP gives clustering solutions with different NCs through the p-scanning process, and then cluster validation technique is used to evaluate quality of these solutions. It is the validity indices that are usually used to evaluate quality of clustering results and to evaluate which clustering solution is the optimal for the data set. Among many validity indices, Silhouette index, which reflects the compactness and separation of clusters, is widely-used and has good performance on NC estimation for obvious cluster structures. It is applicable to both the estimation of the optimal NC and evaluation of clustering quality. Hence, we adopt Silhouette index, as an illustration, to find the optimal clustering solution. 

Let a data set with n samples be divided to k clusters Ci (i=1~k), a(t) be average dissimilarity of sample t of Cj to all other samples in Cj, d(*t,Ci*) be average dissimilarity of sample t of Cj to all samples in another cluster Ci, then b(t)=min{d(t,Ci)},i=1~k,i ≠ j. The Silhouette formula for sample t is [3]: 
3 