Affinity Propagation is unsupervised clustering that never asks you for K. Every point starts as a potential exemplar (cluster center) for every other point, and two matrices of real-valued messages are passed between all pairs of points until the network settles on a small set of exemplars and an assignment of every other point to one of them. This 2D version runs the exact same update equations as the 3D point-cloud edition — only the geometry the points sit in has changed, from three coordinates to two.
Similarity: s(i,k) = -||x_i - x_k||², s(k,k) = preference
Responsibility: r(i,k) ← s(i,k) - max_{k'≠k} [ a(i,k') + s(i,k') ]
(how well-suited k is to be i's exemplar, vs rivals)
Availability: a(i,k) ← min[ 0, r(k,k) + Σ_{i'∉{i,k}} max(0, r(i',k)) ] (i≠k)
a(k,k) ← Σ_{i'≠k} max(0, r(i',k))
(how appropriate it would be for i to pick k, given
how many other points already want k as their exemplar)
Update rule: every message is damped: m ← λ·m_old + (1-λ)·m_new
Decision: point i's exemplar = argmax_k [ a(i,k) + r(i,k) ].
If that is i itself, i becomes an exemplar.
The two message types compete: responsibilities let candidate exemplars fight for members, availabilities let members fight for the best-supported exemplar. Iterating this exchange is mathematically a form of loopy belief propagation on a factor graph — no gradient descent, no random restarts, no K fixed in advance.
- Preference — the self-similarity s(k,k) every point starts with. Set low (very negative) and few points are self-attractive enough to become exemplars, so you get few clusters; raise it and many points compete to be their own center, so you get more, smaller clusters.
- Damping λ — without damping, responsibility/availability updates oscillate; λ close to 1 makes convergence slow but stable, λ near 0.5 converges fast but can diverge on hard inputs.
- Convergence — tracked here as the largest single message change per step; once assignments stop changing for a run of iterations the status reads Converged.
Real-world relevance: Affinity Propagation is used when the "right" number of clusters is unknown and must be discovered from the data itself — image exemplar selection, gene-expression grouping, and text-summary sentence selection are classic applications.