当前位置:

首页 > 业界资讯 > 无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖

无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖

谷歌博客放出新研究,求解无向图的最小割问题。1996年,美国计算机科学家DavidRKarger连同其他研究者在论文《Anewapproachtotheminimumcutproblem》中提出了一个令人惊讶的随机算法Karger算法,其在理论计算机科学中非常重要,尤其适用于大规模图的近似最小割问题。Karger算法可以在时间为O(mlog^3n)的图中找到一个最小割点,他们将这个时间称之为近线性时间,意思是线性乘以一个多对数因子。在谷歌刚刚更新的一篇博客中,他们介绍了之前发布的一篇论文《Determin

谷歌博客放出新研究,求解无向图的最小割问题。

1996 年, 美国计算机科学家 David R Karger 连同其他研究者在论文《 A new approach to the minimum cut problem》中提出了一个令人惊讶的随机算法 Karger 算法,其在理论计算机科学中非常重要,尤其适用于大规模图的近似最小割问题。

Karger 算法可以在时间为 O (m log^3n) 的图中找到一个最小割点,他们将这个时间称之为近线性时间,意思是线性乘以一个多对数因子。

在谷歌刚刚更新的一篇博客中,他们介绍了之前发布的一篇论文《 Deterministic Near-Linear Time Minimum Cut in Weighted Graphs 》,研究获得了 ACM-SIAM SODA24 最佳论文奖。文章详细阐述了一个几乎是线性时间内(而不是近线性时间)运行的新算法,这个算法是确定性的,能够可靠地找到正确的最小割,改进了之前可能无法保证结果正确或只适用于简单图的算法。可以说这是自 Karger 著名的随机化算法以来的重大发现。
无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖
  • 论文地址:https://arxiv.org/pdf/2401.05627.pdf
  • 论文标题:Deterministic Near-Linear Time Minimum Cut in Weighted Graphs

注:最小割问题(通常称为最小割)是关于图连通性的基本结构问题,它一般关注的是断开网络最简单的方法是什么?在图论中,去掉其中所有边能使一张网络流图不再连通(即分成两个子图)的边集称为图的割,一张图上最小的割称为最小割。
无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖
                               一张图及其两个割:红色点线标出了一个包含三条边的割,绿色划线则表示了这张图的一个最小割(包含两条边)。

方法介绍

关于最小割问题,Karger 在 1996 年开创性的给出了一个近乎线性的时间随机算法,该算法能够以较高的概率找到最小割,并且该工作还给出了一个关键见解,即存在一个更小的图,它在很大程度上保留了所有割的大小。

这个发现是很有用的,因为可以使用较小的图作为输入来运行较慢的算法,并且较慢的运行时间(就较小的图的大小而言)仍然可以与原始(较大)图的大小接近线性。

事实上,关于最小割问题的许多结构发现都是沿着这个方向进行的。

谷歌是这样做的,从具有 n 个节点的图 G 开始,然后依据论文《 Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs 》(作者为 Benzur、Karger)提出的割保留稀疏化方法,证明了可以构造一个边数更少的稀疏加权图 G',且在这个图上,几乎所有割的大小与原图 G 中相应割的大小大致相同。

这个概念可以通过以下例子来说明:原始图由两个通过单一边连接的完全图组成,而稀疏化后的图边数更少,但边的权重更大,同时所有割的大小大致得以保留。

无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖

为了构建这种较稀疏的图,Benzur 和 Karger 采用了独立采样边的方法。在这种方法中,图 G 中的每条边都有一定概率被包含在图 G' 中,并且其在 G' 中的权重会根据采样概率的倒数进行放大(例如,如果一条原权重为 1 的边以 10% 的概率被包含,则其权重调整为 10)。结果表明,这种非常简单(几乎是线性时间)的方法具有很高的成功概率,可以构建出保持割的图稀疏化。

然而,Karger 算法是一种蒙特卡洛算法,即输出可能小概率不正确,并且除了与实际已知的最小割进行比较之外,没有已知的方法可以判断输出是否正确。

因此,研究人员一直在努力探索解决近线性时间确定性算法开放问题的方法。由于 cut-preserving 图稀疏化的构造是 Karger 算法中唯一随机的组成部分,因此一种方法是在近线性时间内找到稀疏化的确定性构造(也称为去随机化)。

2015 年,Kawarabayashi 和 Thorup 实现了一个重要的里程碑 —— 找到针对简单图(即每对节点之间至多有一条边且所有边权重等于 1 的图)的确定性近线性时间算法。

该研究得出一个关键思路,即最小割和另一个重要的图结构(称为「low-conductance cut」)之间存在一些联系。这种联系对于后来在一般边权重图上去随机化 Karger 算法至关重要,并帮助谷歌得出了新算法。

最小割和 low-conductance cut 的对齐

图割 S 的 conductance 定义为 S 的 cut 大小与 S 的 volume 之比(假设 S 是切口的较小体积侧且非空),其中 S 的 volume 是 S 中节点的度数。

low-conductance 的 cut S 直观地捕获了网络中的瓶颈,因为只有少量边(相对于其 volume)将 S 连接到图的其余部分。图的 conductance 被定义为图中任何 cut 的最小 conductance,并且大 conductance 的图(也称为扩展图)被认为是良好连接的,因为内部没有瓶颈。
无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖
                              红色虚线表示 cut 大小为 2,较小的一侧(底部)volume 为 24,因此其 conductance 为 1/12,这也是图的 conductance。

Kawayabarashi 和 Thorup 观察到,在最小节点度数较大的简单图中,任何非平凡(即两侧至少有两个节点)最小割都必须具有 low conductance。根据这一观察,如果可以将图划分为连接良好的簇(cluster),则划分必须与每个非平凡最小割一致,因为每个簇必须完全位于每个 cut 的一侧。然后,将每个簇收缩为一个节点,并处理较小的图,其中原始图的所有非平凡最小割都完好无损。

然而,对于加权图,上述观察不再成立,并且简单图情况中使用的相同划分可能与非平凡最小割不完全一致。

如下图所示,Jason Li 2021 年观察到,这种划分仍然与非平凡最小割大致一致。特别地,对于非平凡最小割 S,存在与 S 相差不大的 cut S',使得 S' 与簇一致。Jason Li 进一步观察到,可以利用划分的这种特性来有效地去随机化 cut-preserving 图稀疏化的构造。

无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖

谷歌设计的新算法旨在构建一种划分,来制定最小割的用例。与 Jason Li 在之前的工作中使用的更通用的现成方法相比,谷歌的这项研究更加精确、更加快捷。新研究在保证精度的同时在运行时间上也进行了优化,最终实现了针对最小割问题的近线性时间确定性算法。

参考链接:https://research.google/blog/solving-the-minimum-cut-problem-for-undirected-graphs/
本文内容来源于互联网,如有侵权请联系删除。
作者最新文章
业界资讯 谷歌
相关文章 更多
苹果15plus怎么传照片到电脑 苹果15plus传照片到电脑方法
苹果15plus怎么传照片到电脑 苹果15plus传照片到电脑方法

手机早已成为中青年人的标配,不同年龄段对手机的需求其实差别不小。iPhone 15 Plus 作为当前热度颇高的机型,功能与服务覆盖得相当全面,能满足各类用户的需求。不过,有个实用问题很多人都会遇到——怎么把照片传到电脑上?今天就把两种主流方法掰开揉碎讲清楚,看完你就知道该怎么操作了。 方法一:数据

谷歌亲儿子优先升级!安卓17正式版推送:21款设备首发尝鲜
谷歌亲儿子优先升级!安卓17正式版推送:21款设备首发尝鲜

谷歌正式推送安卓17系统,首批覆盖Pixel6至10系列共21款机型。新功能包括长按应用气泡菜单、应用内存限制机制、精确/大致定位权限选择,以及遗失设备追踪的FindHub功能,进一步优化隐私与设备管理体验。

小米 MIUI不再支持自行安装谷歌GMS服务
小米 MIUI不再支持自行安装谷歌GMS服务

这几天,一些MIUI用户发现手机装不上谷歌GMS(谷歌移动服务)了。这事儿怎么说呢?小米社区里,多位认证为解答组的人员给出了统一回复:国内版MIUI出于合规原因,没有预置Google服务框架的机型,以后不再支持用户自己安装GMS服务。解答组还贴心地补了一句——如果真要用,可以去酷安搜相关教程。 受影

等了7年!Edge终于支持谷歌账号登录同步数据
等了7年!Edge终于支持谷歌账号登录同步数据

微软Edge浏览器计划于2026年7月直接支持谷歌账号登录,用户无需微软账号即可跨设备同步浏览器数据。此举为偏好Edge但不想使用微软账号的用户提供原生单点登录体验,无需再走间接路径。

小米MIXFold3如何安装谷歌 小米MIXFold3安装谷歌方法
小米MIXFold3如何安装谷歌 小米MIXFold3安装谷歌方法

小米MIXFold3未预装谷歌服务,需手动安装:先下载谷歌服务框架并开启未知来源,再安装GooglePlay商店并登录账号。但设备不支持完整GMS,部分应用可能有兼容性问题。

安卓手机忘记解锁密码怎么办?3招教你打开手机
安卓手机忘记解锁密码怎么办?3招教你打开手机

安卓手机忘记密码时,可通过三种方式解锁:一、开启USB调试后,用ADB命令删除密码文件;二、连续错误输入五次,利用绑定的谷歌账号重置;三、使用刷机软件清除锁屏密码。

提升流畅度:谷歌安卓17给App内存占用套上“紧箍咒”
提升流畅度:谷歌安卓17给App内存占用套上“紧箍咒”

安卓17引入四项重要安全改进:包括主动终止内存异常应用、新增本地网络权限防止设备扫描、强制动态加载库只读防止恶意注入、默认启用证书透明度防止伪造证书,全面提升系统安全。

接连两位大咖出走,谷歌到底出了什么BUG?
接连两位大咖出走,谷歌到底出了什么BUG?

不到一周内,谷歌两位核心人物诺姆·沙泽尔与约翰·江珀相继离职。谷歌在AIAgent领域明显落后,产品线混乱,Antigravity2.0表现差强人意。尽管评测分数领先,但任务交付能力不足,组织架构的割裂是根本原因。

存储算力日益短缺,谷歌开始探索让旧手机组队做AI服务器了
存储算力日益短缺,谷歌开始探索让旧手机组队做AI服务器了

谷歌与加州大学圣地亚哥分校利用2000台退役Pixel手机,去除电池和外壳后组成分布式服务器集群。该方案将手机主板分组联网,提供边缘计算能力,缓解算力与存储短缺,但受限于可靠性和维护成本,无法替代传统数据中心。

谷歌浏览器怎么自定义头像
谷歌浏览器怎么自定义头像

谷歌浏览器(chrome)凭借流畅的使用体验和丰富的拓展功能,成为了全球用户使用率最高的浏览器之一,不少用户会用它的多配置文件功能区分工作、生活账号,或是多人共用设备时划分使用空间,自定义头像不仅能满足个性化审美,还能快速区分不同账号,方便识别。很多新用户还不清楚具体的操作方法,接下来就分场景详细说

查看更多
精品专题 更多
装机必备
装机必备

正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

Windows
Windows

正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

macOS软件
macOS软件

正软商城macOS软件专区,精选适用于Mac电脑的办公、设计、影音、效率、开发和系统工具,提供软件功能介绍、macOS兼容版本、正版授权及购买下载服务。

Mac软件 更多
灵活计算器
灵活计算器
macOS/iOS/Android

灵活计算器是一款笔记式算数应用,支持实时计算、动态关联和云端同步功能。记录、整理和输出之间的过渡会更自然,适合长期写作、做笔记或持续沉淀个人内容。

赤友清理大师
赤友清理大师
macOS

赤友清理大师是一款为 Mac 设计的智能清理优化工具,可精准扫描垃圾、大文件、重复文件等,释放磁盘空间。做扫描整理、文字提取和表格转换时,它能把识别后的处理步骤接得更顺,资料录入这类场景会省下不少时间。

极度公式
极度公式
Windows/macOS/Linux

极度公式是一款跨平台专业LaTeX公式识别编辑软件,支持OCR公式识别和多平台编辑。和使用说明,避免使用,享受完整功能与稳定支持。做扫描整理、文字提取和表格转换时,它能把识别后的处理步骤接得更顺,资料录入这类场景会省下不少时间。

WINDOWS 更多
Windows 10
Windows 10
Windows

Windows 10 是一款微软推出的经典操作系统,拥有硬件兼容性与多任务处理能力。它更偏向把系统状态查看和常用调节动作放在一起,适合需要持续观察和微调设备状态的场景。

极度公式
极度公式
Windows/macOS/Linux

极度公式是一款跨平台专业LaTeX公式识别编辑软件,支持OCR公式识别和多平台编辑。和使用说明,避免使用,享受完整功能与稳定支持。做扫描整理、文字提取和表格转换时,它能把识别后的处理步骤接得更顺,资料录入这类场景会省下不少时间。

密码键盘
密码键盘
Windows/macOS/iOS/Android

密码键盘是一款兼具安全性与便捷性的高效密码管理器。日常使用里的持续防护和信息管理会更突出,适合把安全控制放进长期使用流程中的场景。