# Community Detection Using Revised Medoid-Shift Based on KNN

arXiv: https://arxiv.org/abs/2304.09512 · HTML: https://mlsanity.com/paper/2304.09512/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 27 references that are in the map.
- First posted on arXiv 19 Apr 2023.

## Builds on (most cited first, 4 of 4)

- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [GEMSEC: Graph Embedding with Self Clustering](https://mlsanity.com/paper/1802.03997/) (2018)
- [EdMot: An Edge Enhancement Approach for Motif-aware Community Detection](https://mlsanity.com/paper/1906.04560/) (2019)

## Built on by (most cited first, 5 of 5)

- [A Comprehensive Review of Community Detection in Graphs](https://mlsanity.com/paper/2309.11798/) (2023)
- [CAF-YOLO: A Robust Framework for Multi-Scale Lesion Detection in Biomedical Imagery](https://mlsanity.com/paper/2408.01897/) (2024)
- [CCSRP: Robust Pruning of Spiking Neural Networks through Cooperative Coevolution](https://mlsanity.com/paper/2408.00794/) (2024)
- [Case-based reasoning approach for diagnostic screening of children with developmental delays](https://mlsanity.com/paper/2408.02073/) (2024)
- [DDNet: Deformable Convolution and Dense FPN for Surface Defect Detection in Recycled Books](https://mlsanity.com/paper/2409.04958/) (2024)

## Abstract (arXiv)

Community detection becomes an important problem with the booming of social networks. The Medoid-Shift algorithm preserves the benefits of Mean-Shift and can be applied to problems based on distance matrix, such as community detection. One drawback of the Medoid-Shift algorithm is that there may be no data points within the neighborhood region defined by a distance parameter. To deal with the community detection problem better, a new algorithm called Revised Medoid-Shift (RMS) in this work is thus proposed. During the process of finding the next medoid, the RMS algorithm is based on a neighborhood defined by KNN, while the original Medoid-Shift is based on a neighborhood defined by a distance parameter. Since the neighborhood defined by KNN is more stable than the one defined by the distance parameter in terms of the number of data points within the neighborhood, the RMS algorithm may converge more smoothly. In the RMS method, each of the data points is shifted towards a medoid within the neighborhood defined by KNN. After the iterative process of shifting, each of the data point converges into a cluster center, and the data points converging into the same center are grouped into the same cluster. The RMS algorithm is tested on two kinds of datasets including community datasets with known ground truth partition and community datasets without ground truth partition respectively. The experiment results show sthat the proposed RMS algorithm generally produces betster results than Medoid-Shift and some state-of-the-art together with most classic community detection algorithms on different kinds of community detection datasets.