# A Novel Approach for Cognitive Clustering of Parkinsonisms through Affinity Propagation
## 2 Materials and Methods
### Affinity Propagation
In addition to the similarity matrix, the AP algorithm works on two other matrices: the responsibility matrix (**R**) and the availability matrix (**A**) [8; 28; 30]. The final results are stored in a fourth matrix named criterion matrix (**C**). These three matrices are iteratively updated by the following four equations:  
\[r_{ij}\gets s_{ij}-\ max_{j\in s.t.\ j^{\prime}\
eq j}\Big{\{}a_{ij}+s_ {ij^{\prime}}\Big{\}} \tag{4}\]  
\[a_{jj}\leftarrow\sum\
olimits_{\rho\in s.t.\ i^{\prime}\
eq j}max\Big{\{}0, \ r_{r^{\prime}_{j}}\Big{\}} \tag{5}\]  
\[a_{ij}\gets min\Big{\{}0,\ r_{jj}+\ \sum\
olimits_{i^{\prime}s.t.\ i^{ \prime}\
eq i,\ j}max\Big{\{}0,\ r_{r^{\prime}j}\Big{\}}\ \Big{\}} \tag{6}\]  
\[c_{ij}\gets r_{ij}+\ a_{ij} \tag{7}\]  
where \(i\) and \(j\) are respectively the rows and columns indices (\(1\leq i\leq n\) and \(1\leq j\leq m\) ) of the associated matrix. Both the responsibility and availability represent the messages exchanged between nodes, bringing two different kind of competition [28]. In particular, the responsibility \(r(i,\ j)\) is sent by the point \(i\) to the candidate exemplar point \(j\), and it quantifies the eligibility of the point \(j\) to serve as an exemplar for the sample \(i\), considering also other competing exemplar points, e.g., \(j^{\prime}\) (Figure 1 for a schematic representation). On the contrary, the availability \(a(i,j)\) is sent by the candidate exemplar point \(j\) to point \(i\), transmitting the information on how is suitable for the point \(i\) to choose the point \(j\) as its exemplar, considering also the \"opinion\" of other supporting point, e.g., \(i^{\prime}\), regarding the eligibility of \(j\) as exemplar (Figure 1 for a schematic representation). Figure 1: Schematic representation of the functioning of the affinity propagation algorithm in a 3D fashion. Figure adapted and revised from [PERSON] and [PERSON] [28]. A third input of the AP algorithm is the damping factor \(d\), also called dampening parameter \(\lambda\)[8], which was introduced by [PERSON] [28] for assuring the convergence. The purpose of this factor is to add a modest amount of random noise to the similarity matrix and to damp percentage the updates of the responsibility and availability matrices at each iteration \(t\), as follows [30]:  
\[r_{t} =dr_{t-1}+\ (1-d)r^{\prime}_{t} \tag{8}\] \[a_{t} =da_{t-1}+\ (1-d)a^{\prime}_{t} \tag{9}\]  
where \(r^{\prime}\) and \(a^{\prime}\) are the undamped updates respectively of the responsibility and availability matrices, calculated by the Equations (4)-(6). The damping factor \(d\) is usually a value between 0.5 and 1. Indeed, it has been shown [48] that damping factor values in the interval \(0\leq d\leq 0.4\) could result in a significant degree of oscillation and issue with convergence of the algorithm [8]. Thus, in the present work, we used the recommended value of 0.5 [8], which means that 50% of the calculation of the responsibility and availability matrices at each iteration is based on information of the previous message exchanged and 50% of the calculation is based on the new message received. The outputs of the AP algorithm are the number of exemplars ex (clusters) found and the \(n\times 1\) cluster assignment vector \(\underline{\epsilon}\), containing the labels which are none other than the exemplars (clusters) to which each participant (point) belongs. The complete algorithm here applied on the MMSE subscale scores, including the calculation of the regression residuals and the application of the AP algorithm for cognitive clustering, is shown in Algorithm 1.