Pseudo Code for Affinity Propagation

Here is the pseudo-code for the Affinity Propagation algorithm:

Input:

• Similarity matrix S of size N x N

• Damping factor lambda

• Maximum number of iterations max_iter

Output:

• Exemplars of the clusters

Algorithm:

1. Initialize the responsibility matrix R and availability matrix A to 0, both of size N x N

Repeat for each iteration t until convergence or until max_iter is reached:

a. Update the responsibility matrix R using the following formula:

R(i,k) = S(i,k) - max{j≠k}[A(i,j) + S(i,j)]

b. Update the availability matrix A using the following formula:

A(i,k) = min{0, R(k,k) + sum{max(0, R(j,k))} for all j ≠ i}

c. Update the responsibility matrix R using the damping factor lambda:

R = lambda*R + (1-lambda)R_new

d. Update the availability matrix A using the damping factor lambda:

A = lambdaA + (1-lambda)*A_new

e. Calculate the criterion matrix C as the sum of R and A

f. Check for convergence by comparing the criterion matrix C to the criterion matrix from the previous iteration. If the difference is below a certain threshold, exit the loop.

2. Identify the exemplars of the clusters by finding the data points with the highest values in the diagonal of the responsibility matrix R.

3. Assign each data point to its nearest exemplar to form the final clusters.

In the above algorithm, the responsibility matrix R represents the extent to which each data point is responsible for being an exemplar of a cluster, while the availability matrix A represents the extent to which each data point is available to be selected as an exemplar by other data points. The damping factor lambda controls the amount of influence of the previous iteration's matrices on the current iteration.

The algorithm uses an iterative approach to update the matrices until convergence, which is determined by checking the criterion matrix C. Once the exemplars are identified, the final clusters are formed by assigning each data point to its nearest exemplar.