论文阅读:一种基于凸规划的高效有向最密子图发现方法 | SIGMOD 2022

论文概述

这篇论文的主题是研究如何在有向图中找到密度最高的子图,这个问题被称为有向最密子图(Directed Densest Subgraph, DDS)问题。该问题在许多应用中非常重要,如社交网络分析、社区发现、假粉丝检测等。论文提出了一种基于**凸规划(Convex Programming)**的方法来有效解决DDS问题,并设计了精确和近似算法,这些算法能够在大规模数据集上实现显着的性能提升。

在这里插入图片描述

问题定义

DDS问题的目标是在一个给定的有向图中找到一个子图,使其密度在所有子图中是最高的。具体来说,密度是指从一组顶点集 SSS 到另一组顶点集 TTT 的边的数量与这两组顶点数量的乘积的平方根之比。这个密度的计算涉及顶点和边的数量之间的非线性关係,这使得问题的求解具有挑战性。

现有方法的挑战

目前已有的DDS解决方案主要分为两类:基于最大流的精确算法和基于启发式或近似技术的近似算法。然而,这些方法在处理大规模数据集时面临着不同的挑战:

  • 精确算法:这些算法通常需要大量的计算资源,特别是在处理包含大量顶点和边的图时,其计算时间非常长,无法满足实际应用的需求。
  • 近似算法:儘管这些算法在效率上有所提升,但它们通常缺乏灵活性,无法提供可调的近似保证,这意味着在某些情况下,结果的质量可能难以控制。

作者的思路

1. 问题的重新表述

第一步是将DDS问题转化为一个可以用凸规划技术处理的形式。具体而言,作者提出了一个基于线性规划(Linear Programming, LP)的公式来重述DDS问题。这种转化允许使用已知的优化技术来求解该问题。

2. 使用对偶理论的创新

在转化为线性规划后,作者利用对偶理论来提高算法的效率。通过解对偶问题,作者能够推断原问题的解,这样做的好处是对偶问题通常比原问题更容易解,并且可以揭示一些有用的结构特性。

在这里插入图片描述

3. 分治策略的应用

为了应对大规模图数据,作者採用了分治策略。通过将问题拆分为更小的子问题来减少计算量,然后逐步解决这些子问题,最终合併结果以得到全局解。

在这里插入图片描述

算法设计

1. 精确算法(CP-Exact)

作者设计了CP-Exact精确算法。该算法利用分治策略和对偶理论来高效地求解线性规划问题。它首先通过分治策略减少需要解的线性规划问题的数量,然后使用Frank-Wolfe算法(一种迭代优化技术)来解对偶问题,最终得到精确的DDS解。

2. 近似算法(CP-Approx)

除了精确算法,作者还设计了CP-Approx近似算法。这个算法通过利用对偶问题中的**鸿沟(duality gap)**进行近似估算,从而在保证一定精度的前提下,大幅减少计算时间。CP-Approx特别适合处理超大规模的图数据,能在更短的时间内找到接近最佳解的近似解。

理论分析

作者详细分析了这些算法的时间複杂度近似保证。CP-Exact算法在理论上比现有的精确算法更高效,特别是在处理大规模图时,而CP-Approx算法则提供了灵活的近似保证,允许用户在计算精度和效率之间进行调整。

实验结果

作者在八个不同类型的大规模图数据集上对其算法进行了实验测试。结果显示,CP-Exact算法在精确性和计算速度上大幅优于现有算法,尤其是在处理包含数十亿条边的图时展示了卓越的性能。CP-Approx算法在近似效果上也比现有算法快了多达五个数量级。

近似算法:

在这里插入图片描述

这张图片包含了两个图表,用于比较不同近似算法的效率和实际近似比率。

**上图(Figure 5)**展示了不同近似算法在多个数据集上的运行时间,以毫秒(ms)为单位。三种算法分别为: CP-Approx(橙色) Core-Approx(白色) VW-Approx(蓝色) 图中可以看出,CP-Approx算法在大多数数据集上运行时间最短,而VW-Approx算法在某些数据集上运行时间较长,甚至在部分数据集上显示出无穷大(Inf.)的结果。

**下图(Figure 6)**展示了这些算法的实际近似比率,近似比率越接近1,表示算法结果越接近真实值。三种算法的近似比率在不同数据集上的表现各有不同,总体来说CP-Approx和VW-Approx的近似比率相对稳定,而Core-Approx在某些数据集上表现出较大的波动(例如在OF数据集上)。

精确算法:
在这里插入图片描述

这张图片包含两个表格,展示了CP-Exact算法在不同数据集上的统计数据和运行时间比较。

  • 表3(Table 3)展示了CP-Exact算法在不同数据集上的统计数据,包括:

    • Datasets:数据集的名称。
    • #c:表示进行计算时的c值的数量。
    • Avg #iterations:平均迭代次数。
    • Avg #edges:平均边数。
    • Product:计算得到的结果,通常表示为某种规模的度量(例如边数的乘积)。

    从表中可以看出,CP-Exact在不同数据集上的迭代次数和边数差异很大,尤其是在SK数据集上,平均边数达到407×10^7,显示了该算法处理大规模数据时的能力。

  • 表4(Table 4)展示了CP-Exact和CP-Exact-ab算法的运行时间比较,包括:

    • Dataset:数据集的名称。
    • CP-Exact:CP-Exact算法的运行时间,以秒为单位。
    • CP-Exact-ab:CP-Exact-ab算法的运行时间,以秒为单位。
    • Speedup:表示CP-Exact-ab相比CP-Exact的加速比率。

    表中显示,CP-Exact-ab在大多数数据集上都实现了显着的加速效果,例如在BA数据集上,加速比达到了472.71倍。然而,在某些数据集上,如SK数据集,可能无法计算或无法提供比较数据(NA)。

结论

这篇论文通过将DDS问题转化为线性规划问题,并利用对偶理论和分治策略,成功设计了高效的精确和近似算法,这些算法在大规模图数据的分析中展现出了强大的实用性和卓越的性能,为DDS问题的解决提供了重要的贡献。未来的研究可以考虑将这些方法应用于其他类型的图结构,如动态图或异质图,进一步扩展算法的适用范围。此外,还可以探索将这些技术整合到分佈式计算平台中,以处理更大规模的数据集。同时,研究如何进一步优化算法的性能,特别是在近似保证和计算效率之间找到更好的平衡,也是未来值得探索的重要方向。

论文地址:https://dl.acm.org/doi/abs/10.1145/3514221.3517837

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/400062.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

AI for reading ML paper

心流 心流 Kimi Kimi Humata Humata Bytez Bytez Chatgpt4 scholar 学术版chatgpt4,需要充值; 还有更多AI工具等待你发现;

sqlserver清理数据库日志并写作业定期执行

清理数据库日志最终sql: USE [master] GO ALTER DATABASE lsrz_zjwb_w SET RECOVERY SIMPLE WITH NO_WAIT GO ALTER DATABASE lsrz_zjwb_w SET RECOVERY SIMPLE --简单模式 GO USE lsrz_zjwb_w GO DBCC SHRINKFILE (Nlsrz_zjwb_log , 2, TRUNCATEONLY) --日志文件…

【网络】IO

IO 一、五种IO模型同步通信 vs 异步通信阻塞 vs 非阻塞 二、其他高级IO非阻塞IOSetNoBlockI/O多路转接之selectselect函数原型fd_set(位图)select代码select缺点poll(用select修改) I/O多路转接之epoll高级版改进select和poll的问…

企业如何组建安全稳定的跨国通信网络

当企业在海外设有分公司时,如何建立一个安全且稳定的跨国通信网络是一个关键问题。为了确保跨国通信的安全和稳定性,可以考虑以下几种方案。 首先,可以在分公司之间搭建虚拟专用网络。虚拟专用网络通过对传输数据进行加密,保护通信…

前端vue项目——打包部署(nginx中部署静态资源)

1、当前的开发方式 前端人员开发前端,后端人员开发后端的java工程,最终要将开发完毕的前端工程和后端工程分开部署在对应的服务器上(前端流行的nginx) 2、打包 (1)原理 (2) &#xf…

java实现七牛云内容审核功能,文本、图片和视频的内容审核(鉴黄、鉴暴恐、敏感人物)

目录 1、七牛云内容审核介绍 2、查看内容审核官方文档 2.1、文本内容审核 2.1.1、文本内容审核的请求示例 2.1.2、文本内容审核的返回示例 2.2、图片内容审核 2.2.1、请求参数 2.2.2、返回参数 2.3、视频内容审核 3、代码实现 3.1、前期代码准备 3.2、文本内容审核…

Scrapy框架进行数据采集详细实现

摘要 本项目是python课程的课程项目,在简要学习完python和爬虫相关的Scrapy框架后,基于这两者的运用最终完成了对于北京链家网站新房页面的信息进行爬取,并将爬取的数据存放于excel之中,可使用excel或者wps进行查看。 1 引言 1…

HYDRUS2D/3D模型技术教程

原文链接:HYDRUS2D/3D模型技术教程https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247612514&idx6&snadf080ddb3394d2f758fc269fa6ce9dc&chksmfa827985cdf5f093af1410f151e11fb6d4b39e7533f401624dc2a2375bdcc74b4b0f6160c58b&token1585…

论文分享 | Fuzz4All: 基于大语言模型的通用模糊测试

大语言模型是当前最受关注的研究热点,基于其生成和理解能力,对现有领域在提升性能和效果上做更多尝试。分享一篇发表于2024年ICSE会议的论文Fuzz4All,它组合多个大语言模型以非常轻量且黑盒的方式,实现了一种跨语言和软件的通用模…

适合所有人的生成式人工智能-学习先导课

欢迎来到为所有人提供的生成式人工智能课(generative AI )。自ChatGPT发布以来,人工智能特别是生成式人工智能引起了许多个人、企业和政府的关注。 这是一项非常颠覆性的技术,已经在改变许多人的学习和工作方式。许多开发者认为生成式AI将使许多人得以赋…

[240812] X-CMD 发布 v0.4.5:更新 gtb、cd、chat、hashdir 模块功能

目录 📃Changelog✨ gtb✨ cd✨ chat✨ hashdir 📃Changelog ✨ gtb 调整了 fzf 预览窗口中书籍文本的显示效果,通过识别文本中的特殊字符、日期、章节标题等信息,为其赋予不同的颜色。 ✨ cd cd 模块新增功能:在找…

RS®ZN-Z8x 开关矩阵

R&SZN-Z8x 开关矩阵 专为多端口矢量网络分析仪测量而设计 R&SZN-Z8x 开关矩阵经过优化设计,专门用于罗德与施瓦茨的矢量网络分析仪。这款经济高效的多方位解决方案可用于多端口设备或多个设备的简单和复杂的测量任务。开关矩阵支持宽频率范围&#xff0…

【论文阅读】YOLOv10: Real-Time End-to-End Object Detection

题目:YOLOv10: Real-Time End-to-End Object Detection 作者:Ao Wang Hui Chen∗ Lihao Liu Kai Chen Zijia Lin Jungong Han Guiguang Ding∗ 清华大学的 motivation: 作者觉得YOLO系列的NMS和某些结构非常的耗时,提出NMS-free和一些列高效…

Qt编译配置OpenCV+opencv_contrib(使用cmake)

本文使用环境 OpenCV: 4.7.0 cmake: 3.30.2 Qt: 5.12.1一、配置环境变量 安装好OpenCV、Qt、cmake后,应配置好一下环境变量: 二、编译OpenCV 打开cmake,编译的源码路径选择opencv文件夹中的sources目录,在opencv文件夹下新建一…

视频汇聚平台智能边缘分析一体机分析平台摄像头异常位移算法识别检测

智能边缘分析一体机在摄像头异常位移检测方面扮演着关键角色,它利用先进的图像处理技术和机器学习算法来实时监测摄像头状态,判断是否发生了非预期的位移。下面是智能边缘分析一体机如何检测摄像头异常位移的详细步骤: 1. 图像帧对比&#x…

SpringBoot中生成条形码的方案实战

​ 博客主页: 南来_北往 系列专栏:Spring Boot实战 ZXing库介绍 ZXing库是一个用于解析和生成多种格式的一维和二维条形码的开源Java库。 ZXing(“zebra crossing”的缩写)库提供了多种条形码格式的支持,包括但不限于QR码、…

Vue3 el-tabs 切换记录选项卡,离开前提示

最近做了一个项目,tabs选项卡 需要在离开当前的选中的项时进行提示并且当取消时定位原位置。 看效果图 当我进行编辑时 触发编辑 但是没有进行保存即提示信息。取消后返回原tabs ,否则确认后进入下个tab。 上代码 tab 一般默认会有一个值,一把是第一…

经典算法题总结:二叉树篇

二叉树解题的思维模式分两类: 是否可以通过遍历一遍二叉树得到答案?如果可以,用一个 traverse 函数配合外部变量来实现,这叫「遍历」的思维模式。是否可以定义一个递归函数,通过子问题(子树)的…

如何平衡冷数据(历史库)的成本与性能?| OceanBase应用实践

随着数据量的迅猛增长,企业和组织在数据库管理方面遭遇的挑战愈发凸显。数据库性能逐渐下滑、存储成本节节攀升,以及数据运维复杂性的增加,这些挑战使得DBA和开发者在数据管理上面临更大的压力。 为了应对这些挑战,对数据生命周期…

Jeecgboot3.6.3的vue3版本的一种flowable动态增加一个用户任务节点的方法(三)后端代码实现

因为这个项目license问题无法开源,更多技术支持与服务请加入我的知识星球。 这部分主要讲后端实现部分 1、增加一个AddTaskVo 类型,提供新增任务需要的数据结构 import io.swagger.annotations.ApiModel; import io.swagger.annotations.ApiModelProperty; import lombok.D…