El agrupamiento es una tarea fundamental en la minería de datos. El agrupamiento por propagación de afinidad (APC) es una técnica de agrupamiento efectiva y eficiente que se ha aplicado en varios dominios. APC propaga información de forma iterativa entre muestras de afinidad, actualiza la matriz de responsabilidad y la matriz de disponibilidad, y utiliza estas matrices para elegir centros de agrupamiento (o ejemplares) de los respectivos grupos. Sin embargo, dado que principalmente utiliza la distancia euclidiana negativa entre ejemplares y muestras como la similitud entre ellos, es difícil identificar grupos con estructuras complejas. Por lo tanto, el rendimiento de APC se deteriora en muestras distribuidas con estructuras complejas. Para mitigar este problema, proponemos una mejora de APC basada en una similitud basada en caminos (APC-PS). APC-PS utiliza en primer lugar la distancia euclidiana negativa para encontrar ejemplares de grupos. Luego, emplea la similitud basada en caminos para medir la similitud entre ejemplares y muestras, y para explorar la estructura subyacente de los grupos. A continuación, asigna muestras que no son ejemplares a sus respectivos grupos mediante esa similitud. Nuestro estudio empírico en conjuntos de datos sintéticos y de UCI muestra que el propuesto APC-PS supera significativamente al APC original y a otros enfoques relacionados.