Abstract: The commonly-used clustering algorithms have several drawbacks. Aiming to solve the above problems, an improved k-medoids algorithm was proposed based on the initial radius r, which is used for clustering using location data. The algorithm is actually a density-based clustering approach. The difference is that the k value depends on the radius r. Extensive experiments are conducted on real check-in data, and the results show that the improved k-mediods algorithm on the radius r is more stable. In addition, by comparing the sum of the square of distance between objects in the same cluster among different algorithms, the proposed algorithm can obtain better clustering results and convergence speed when applied to location based social networks. Compared to the traditional k-medoids algorithm, the cost has obviously reduced, as for and the degraded k-medoids algorithm, the cost can be reduced among 1.2% and 2%.

Key words: social networks, density-based clustering, k-medoids, check-in data, distance similarity