# Affinity Propagation Clustering Using Path Based Similarity
## 2 Method
### Affinity Propagation Clustering  
APC assumes each sample can be a potential cluster representative sample (cluster center or exemplar). It iteratively transmits messages between affinity samples, until a high-quality set of exemplars emerges. Let \(\mathbf{X}=[\mathbf{x}_{1};\mathbf{x}_{2};\cdots;\mathbf{x}_{n}]\in\mathbb{R }^{n\times d}\) be a data matrix of \(n\) samples, and each vector \(\mathbf{x}_{i}\) corresponds to a \(d\)-dimensional sample. \(\mathbf{S}\in\mathbb{R}^{n\times n}\) encodes the similarity between these \(n\) samples, the entry \(\mathbf{S}(i,j)\) is specified as below:  
\[\mathbf{S}(i,j)=-\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|^{2},(i\
eq j) \tag{1}\]  
where \(\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|^{2}\) is the Euclidean distance between \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\). When \(i=j\), since all samples are initially viewed as the potential exemplars, each diagonal entry of \(\mathbf{S}\) is set as \(p\), which reflects the preference of choosing a sample as the cluster center. \(p\) can be adjusted to get an appropriate number of exemplars (or clusters). In most cases, \(p\) is set as the median of \(\mathbf{S}\). [PERSON] et al. [8] suggested that \(p\) can be adjusted to produce an expected (or user-specified) number of clusters. The smaller the value of \(p\), the fewer the clusters are. There are two matrices involved with APC: the responsibility matrix (\(\mathbf{R}\in\mathbb{R}^{n\times n}\)) and availability matrix (\(\mathbf{A}\in\mathbb{R}^{n\times n}\)). \(\mathbf{R}(i,j)\) measures the accumulated evidence of how well-suited sample \(\mathbf{x}_{j}\) serves as the exemplar for sample \(\mathbf{x}_{i}\). \(\mathbf{A}(i,j)\) measures the accumulated evidence of how appropriate \(\mathbf{x}_{i}\) chooses \(\mathbf{x}_{j}\) as its exemplar. At first, elements of \(\mathbf{R}\) and \(\mathbf{A}\) are initialized with zero. The response matrix \(\mathbf{R}\) is updated by a formula as follow:  
\[\mathbf{R}^{(t)}(i,j)=\mathbf{S}(i,j)-max_{h\
eq j}\left\{\mathbf{A}^{(t-1)}( i,h)+\mathbf{S}(i,h)\right\} \tag{2}\]  
where \(\mathbf{R}^{(t)}(i,j)\) is the updated \(\mathbf{R}(i,j)\) in the \(t\)-th iteration, and \(\mathbf{A}^{(t-1)}(i,h)\) is the updated \(\mathbf{A}(i,h)\) in the \((t-1)\)-th iteration. \(\mathbf{A}^{(t-1)}(i,h)+\mathbf{S}(i,h)\) measures the potentiality of taking \(\mathbf{x}_{h}\) as the exemplar of \(\mathbf{x}_{i}\). \(\mathbf{R}^{(t)}(i,j)\) reflects the degree that \(\mathbf{x}_{i}\) supports \(\mathbf{x}_{j}\) to be an exemplar compared with \(\mathbf{x}_{i}\) supporting the most potential sample \(\mathbf{x}_{h}\) to be an exemplar. If \(\mathbf{R}^{(t)}(i,j)\) is larger than zero, \(\mathbf{x}_{j}\) is more supported as an exemplar of \(\mathbf{x}_{i}\) than \(\mathbf{x}_{h}\). The larger the value of \(\mathbf{R}^{(t)}(i,j)\), the larger the likelihood \(\mathbf{x}_{j}\) as an exemplar of \(\mathbf{x}_{i}\) is. For special case \(i=j\), \(\mathbf{R}^{(t)}(j,j)\) reflects accumulated evidence that \(\mathbf{x}_{j}\) is an exemplar based on the initial preference value \(p\). The available matrix \(\mathbf{A}\) is iteratively updated as:  
\[\mathbf{A}^{(t)}(i,j)=min\left\{0,\mathbf{R}^{(t)}(j,j)+\sum_{h\
eq j,h\
eq j }max\{0,\mathbf{R}^{(t)}(h,j)\}\right\} \tag{3}\]  
where \(max\{0,\mathbf{R}^{(t)}(h,j)\}\) means only the positive elements of incoming \(\mathbf{R}^{(t)}(h,j)\) are considered, since it is only necessary for a good exemplar to well account for some samples (positive responsibilities), regardless how poorly it accounts for other samples (negative responsibilities). To restrict the influence of large positive \(\mathbf{R}^{(t)}(j,j)\), Equation (3) restricts the total sum is no more than zero. The diagonal entry of \(\mathbf{A}^{(t)}(i,i)\) is updated as:  
\[\mathbf{A}^{(t)}(i,i)=\sum_{h\
eq i}max\left\{0,\mathbf{R}^{(t)}(h,i)\right\} \tag{4}\]  
The \(\mathbf{A}^{(t)}(i,j)\) indicates the possibility of \(\mathbf{x}_{j}\) as an exemplar based on its all positive responsibilities.