Community detection becomes an important problem with the booming of social networks. As an excellent clustering algorithm, Mean-Shift can not be applied directly to community detection, since Mean-Shift can only handle data with coordinates, while the data in the community detection problem is mostly represented by a graph that can be treated as data with a distance matrix (or similarity matrix). Fortunately, a new clustering algorithm called Medoid-Shift is proposed. 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.


翻译:社区检测是随着社交网络的兴起成为一个重要问题。优秀的聚类算法Mean-Shift不能直接应用于社区检测,因为Mean-Shift只能处理具有坐标的数据,而社区检测问题中的数据大多数是由可以视为具有距离矩阵(或相似性矩阵)的数据表示的图表。幸运的是,提出了一种新的聚类算法Medoid-Shift。Medoid-Shift算法保留了Mean-Shift的优点,可用于基于距离矩阵的问题,例如社区检测。Medoid-Shift算法的一个缺点是,由距离参数定义的邻域区域可能没有数据点。为了更好地处理社区检测问题,在本文中提出了一种名为修订Medoid-Shift(RMS)的新算法。在寻找下一个中心点的过程中,RMS算法基于由KNN定义的邻域,而原始的Medoid-Shift算法基于由距离参数定义的邻域。由于由KNN定义的邻域在邻域中的数据点数量方面比距离参数定义的邻域更稳定,因此RMS算法可能会更平滑地收敛。在RMS方法中,每个数据点都朝向在由KNN定义的邻域中的介质移动。在移位的迭代过程之后,每个数据点都会收敛到一个群集中心,收敛到相同中心的数据点将被分组到同一群集中。

0
下载
关闭预览

相关内容

【ICDM 2022教程】图挖掘中的公平性:度量、算法和应用
专知会员服务
27+阅读 · 2022年12月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
一文带你浏览Graph Transformers
PaperWeekly
1+阅读 · 2022年7月8日
LibRec 精选:推荐系统的常用数据集
LibRec智能推荐
17+阅读 · 2019年2月15日
掌握图神经网络GNN基本,看这篇文章就够了
新智元
163+阅读 · 2019年2月14日
论文笔记之Feature Selective Networks for Object Detection
统计学习与视觉计算组
21+阅读 · 2018年7月26日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
Relation Networks for Object Detection 论文笔记
统计学习与视觉计算组
16+阅读 · 2018年4月18日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
1+阅读 · 2023年6月5日
Arxiv
0+阅读 · 2023年6月2日
Arxiv
13+阅读 · 2022年10月27日
Arxiv
38+阅读 · 2020年3月10日
Arxiv
12+阅读 · 2019年3月14日
A Comprehensive Survey on Graph Neural Networks
Arxiv
13+阅读 · 2019年3月10日
VIP会员
相关VIP内容
【ICDM 2022教程】图挖掘中的公平性:度量、算法和应用
专知会员服务
27+阅读 · 2022年12月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
一文带你浏览Graph Transformers
PaperWeekly
1+阅读 · 2022年7月8日
LibRec 精选:推荐系统的常用数据集
LibRec智能推荐
17+阅读 · 2019年2月15日
掌握图神经网络GNN基本,看这篇文章就够了
新智元
163+阅读 · 2019年2月14日
论文笔记之Feature Selective Networks for Object Detection
统计学习与视觉计算组
21+阅读 · 2018年7月26日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
Relation Networks for Object Detection 论文笔记
统计学习与视觉计算组
16+阅读 · 2018年4月18日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员