Affinity Propagation Clustering
Also known as: affinity propagation clustering, message-passing clustering, exemplar-based clustering, yakınlık yayılımı kümeleme
Affinity propagation, introduced by Brendan Frey and Delbert Dueck in 2007, is a clustering algorithm that identifies representative 'exemplars' among the data by exchanging messages between every pair of points until a consistent set of clusters emerges. Unlike k-means it does not require the number of clusters to be specified in advance — that number arises from the data and a 'preference' parameter — and it works directly from pairwise similarities, which need not be a metric.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use affinity propagation when you do not know the number of clusters in advance, want actual data points (exemplars) as cluster representatives rather than synthetic centroids, or only have pairwise similarities that may be non-metric or asymmetric. It suits moderate-sized datasets in image, document, and bioinformatics clustering, and gives reproducible results (no random initialization). Its principal drawback is scalability: it stores and updates an N × N message matrix, costing roughly quadratic memory and time, so it does not suit very large datasets. Results are sensitive to the preference parameter (which controls cluster count) and to damping for convergence, and the algorithm can oscillate without adequate damping. For large data or known k, k-means or DBSCAN are more practical.
Strengths & limitations
- Determines the number of clusters automatically from the data and preference.
- Uses real data points as exemplars, aiding interpretability.
- Works from arbitrary pairwise similarities, including non-metric ones.
- Deterministic given inputs — no sensitivity to random initialization.
- Quadratic memory and time in the number of points, limiting scalability.
- Results depend strongly on the preference parameter that controls cluster count.
- Can fail to converge or oscillate without sufficient message damping.
- Assumes a meaningful similarity matrix and can struggle with clusters of very different sizes/densities.
Frequently asked
How does affinity propagation choose the number of clusters?
It does not take the number of clusters as input. Instead, the 'preference' value on the diagonal of the similarity matrix controls how readily points become exemplars: higher preferences produce more clusters. The actual count emerges from the message-passing process, so tuning the preference (e.g., from the median similarity) is how you influence it.
What is an exemplar?
An exemplar is an actual data point chosen to represent a cluster — every other point in the cluster is assigned to it. Unlike k-means centroids, which are averages that may not correspond to any real observation, exemplars are real data points, which aids interpretability.
Why is affinity propagation slow on large datasets?
It maintains and updates responsibility and availability messages between all pairs of points, so it needs an N × N matrix and roughly quadratic time and memory. This makes it impractical for very large N; k-means, mini-batch variants, or DBSCAN are better choices at scale.
Sources
- Frey, B. J., & Dueck, D. (2007). Clustering by passing messages between data points. Science, 315(5814), 972–976. DOI: 10.1126/science.1136800 ↗
How to cite this page
ScholarGate. (2026, June 2). Affinity Propagation Clustering. ScholarGate. https://scholargate.app/en/machine-learning/affinity-propagation
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- DBSCANMachine learning↔ compare
- Hierarchical ClusteringMachine learning↔ compare
- K-Means ClusteringMachine learning↔ compare
- Spectral ClusteringMachine learning↔ compare