Local graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most (local) graph clustering algorithms is to find a vertex set of low conductance, there has been a sequence of recent studies that highlight the importance of the inter-connection between clusters when analysing real-world datasets. Following this line of research, in this work we study local algorithms for finding a pair of vertex sets defined with respect to their inter-connection and their relationship with the rest of the graph. The key to our analysis is a new reduction technique that relates the structure of multiple sets to a single vertex set in the reduced graph. Among many potential applications, we show that our algorithms successfully recover densely connected clusters in the Interstate Disputes Dataset and the US Migration Dataset.


翻译:本地图集是分析大型图集的重要算法技术,并广泛应用于数据科学的许多研究领域。虽然大多数(本地)图集算法的目标是找到一组低导力的顶点,但最近的一系列研究显示,在分析真实世界数据集时,各组之间相互联系的重要性。根据这一研究方针,我们研究当地算法,以寻找一对因彼此连接及其与图中其余部分的关系而确定的顶点。我们分析的关键是一种新的缩小技术,将多组结构与减少的图集中的单一顶点联系起来。在很多潜在应用中,我们显示我们的算法成功地恢复了国家间争端数据集和美国迁移数据集中的密集连接组。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【经典书】算法C语言实现,Algorithms in C. 672页pdf
专知会员服务
81+阅读 · 2020年8月13日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
152+阅读 · 2019年10月12日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
计算机经典算法回顾与展望——机器学习与数据挖掘
中国计算机学会
5+阅读 · 2019年10月11日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
Arxiv
0+阅读 · 2021年8月2日
Arxiv
0+阅读 · 2021年8月1日
Optimization for deep learning: theory and algorithms
Arxiv
104+阅读 · 2019年12月19日
Meta-Learning to Cluster
Arxiv
17+阅读 · 2019年10月30日
Arxiv
15+阅读 · 2019年6月25日
VIP会员
相关资讯
计算机经典算法回顾与展望——机器学习与数据挖掘
中国计算机学会
5+阅读 · 2019年10月11日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
Top
微信扫码咨询专知VIP会员