
## 2 Adaptive Affinity Propagation

In this section, the adaptive damping and escape methods are discussed first to eliminate oscillations, and then the adaptive scanning of p is designed. Finally, a cluster validity method is adopted to find the optimal clustering solution. It is noted that the same initial value is assigned to all the p(i) in the diagonal of matrix S. 

When oscillations occur and AP fails to converge, our target is to both eliminate oscillations and keep the speed of the algorithm. Although the lam near 1 has more probability for oscillation elimination, the R and A are updated very slow and much more time is needed to run AP. It is a better choice to check the effect of oscillation elimination while increasing lam gradually. Following this idea, the adaptive damping method is designed: (1) detect whether oscillation occurs in an iteration of the AP algorithm; (2) the lam is increased once by a step such as 0.05 if oscillations are detected, otherwise go to (1); (3) the iteration continues w times; (4) repeat these steps until the algorithm meets preset stop condition. 

It is a key to detect any oscillation while the algorithm runs, but features of oscillations are too complex to be described. Then, we turn to describe/define non-oscillation features: the number of identified exemplars is decreasing or unchanging during the iterative process. This definition is reasonable, since the decreasing and unchanging are the features that the algorithm is going to convergence. A moving monitoring window Kb(i) (window size w) is used to record whether non-oscillation features appear in a sequence of iterations, e.g., Kb(i)=1 when non-oscillation features appear in iteration i, otherwise Kb(i)=0. The criterion of whether oscillations occur is designed as follows: oscillations occur if the number of non-oscillation features in the monitoring window is less than two thirds of window size. This is a tolerant design that considers tolerating occasionally random vibrations in a short time and vibrations in initial iterations. Thus, the above monitoring -adjusting technique realizes adaptive adjustment of lam and leads AP to convergence. 

If it fails to depress oscillations by increasing lam (e.g., lam is increased to 0.85 or higher), an adaptive escape technique will be designed to avoid oscillations. That large lam brings little effect suggests that oscillations are pertinacious under the given p, so the alternative is to decrease p away from the given p to escape from oscillations. This escape method is workable due to that it works together with adaptive scanning of p discussed below, different from AP that works under a fixed p. 

The adaptive escape technique is designed as follows: when oscillations occur and lam≥0.85 in the iterative process, decreasing p gradually until oscillations disappear. This technique is added in the step (2)
of the adaptive damping method: if oscillations occur, increasing *lam* by a step such as 0.05; if *lam*≥0.85, decreasing p by step ps, otherwise go to step (1) of the adaptive damping method. Both adaptive damping and adaptive escape techniques are used to eliminate oscillations at the same time. The monitoring window size w=40 is appropriate as per our experiences (occasionally random vibrations and tolerant vibrations in initial iterations will be caught under too small w and AP runs slowly under too big w). The pseudo codes of adaptive damping and adaptive escape are listed in Table 1 (where *maxits* and ps will be set in Table 2). 

Initialization: damping factor *lam*←0.5, monitoring window size w←40, parameter w2←w/8, max iteration times *maxits*, decreasing step ps. 

for i←1 to *maxits* do *Kset*(i) ← K △ K is the number of exemplars Km(i)←mean(*Kset*(i-w2:i)) 
if Km(i)-Km(i-1) < 0 then Kd←1 △ record the decrease of K 
Kc←∑ j |Kset(i)-*Kset*(j)| △ record the unchanged of K, j∈i-w2 to i-1
△ record the decrease and unchangeableness of K in monitoring window Kb: 
if Kd = 1 or Kc = 0 then Kb(j)←1 △ j is the remainder of i/w else Kb(j)←0 △ j is the remainder of i/w Ks←∑ *j Kb*(j) △ j∈1 to w if Ks < 2w/3 then lam←lam+0.05 if lam >= 0.85 then p←p+ps 2 