We consider a variant of the clustering problem for a complete weighted graph. The aim is to partition the nodes into clusters maximizing the sum of the edge weights within the clusters. This problem is known as the clique partitioning problem, being NP-hard in the general case of having edge weights of different signs. We propose a new method of estimating an upper bound of the objective function that we combine with the classical branch-and-bound technique to find the exact solution. We evaluate our approach on a broad range of random graphs and real-world networks. The proposed approach provided tighter upper bounds and achieved significant convergence speed improvements compared to known alternative methods.


翻译:我们为完整的加权图表考虑组别问题的变体。 目的是将节点分成组, 使组群中边缘重量的总和最大化。 这个问题被称为分层分割问题, 在有不同标志的边缘重量的一般情况下, 这个问题是NP硬的。 我们提出了一种新的方法来估计目标功能的上层界限, 即我们与传统分支和约束技术相结合, 以找到确切的解决办法。 我们评估了我们对于范围广泛的随机图和真实世界网络的做法。 与已知的替代方法相比, 拟议的方法提供了更严格的上层界限, 并实现了显著的趋同速度改进。

0
下载
关闭预览

相关内容

专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
52+阅读 · 2020年11月3日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年12月3日
Arxiv
0+阅读 · 2021年12月3日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员