Given a pre-computed distance matrix, obtained from arbitrary samples, such as graphs, I am currently looking for efficient clustering algorithms to deal with distance matrices, so that the algorithm indicates which sample indices (index from 0 to matrix_length-1, as each line corresponds to a distance from sample to all others) are the best clusters centers.
I have already implemented "fast k-medoids", from Park and Jun.
MeanShift can be implemented for this as well, but I am not sure if it could use ball trees or kd-trees to efficiently allow the algorithm to find nearest neighbors efficiently. To implement MeanShift for distance matrices, there is need for computing a "center" from some samples, which can be considered as the sample which minimizes the sum of distances to all others.
The problem on later ideia is how to calculate 'centers', because the samples doesn't belong to a n-dimensional space. KD-tree or ball-tree can be used in such scenario?
Edit: if it helps, I have a MeanShift that deals with distances matrices: https://github.com/icarocd/parallel-meanshift