更改

[[File:affinitypropagation_figure_3.png|center|600px]]

[[File:affinitypropagation_figure_3.png|center|600px]]

kmeans方法中，相似性矩阵是对称的，即s(i,j)=s(j,i)，但是AP并没有这个要求。后者甚至适用于不满足三角关系的情况。在2007年的论文中，作者分析的美国和加拿大的航班网络（网络也可以看做是一个相似性矩阵，相似性权重为网络连边上的流量或者别的统计量，本案例中是一个城市到另一个城市的飞行时间）。在这个网络里，相似性是城市之间的飞行时间，这个变量是不满足三角关系的。例如A->B的平均飞行时间不一定就小于A->C+C->B的平均飞行时间（因为前者可能会没有直达飞机而要中途在别处转机，而且地球是一个球体）。在这个案例中，AP给出了很好的划分结果。

kmeans方法中，相似性矩阵是对称的，即<math>\s(i,j)</math>=:<math>\s(j,i)</math>，但是AP并没有这个要求。后者甚至适用于不满足三角关系的情况。在2007年的论文中，作者分析的美国和加拿大的航班网络（网络也可以看做是一个相似性矩阵，相似性权重为网络连边上的流量或者别的统计量，本案例中是一个城市到另一个城市的飞行时间）。在这个网络里，相似性是城市之间的飞行时间，这个变量是不满足三角关系的。例如A->B的平均飞行时间不一定就小于A->C+C->B的平均飞行时间（因为前者可能会没有直达飞机而要中途在别处转机，而且地球是一个球体）。在这个案例中，AP给出了很好的划分结果。

===适用于稀疏的相似性矩阵===

===适用于稀疏的相似性矩阵===