图谱动态｜学苑周刊 NO.168

图谱学苑 2024-01-17

177

本期将分享近期全球知识图谱相关

行业动态、会议课程、论文推荐

—--| 新闻动态 |--—

Gartner人工智能雷达图

Gartner2023年底发布的人工智能雷达图中Gartner新兴技术和趋势影响力雷达图显示，知识图谱已经位于生成式AI影响力雷达的中心区域。关于如何理解这个雷达图的简单说明：圆环代表范围，可以对技术或趋势从早期采用阶段发展到早期多数采用阶段所需的年数进行估计。新兴技术或者趋势雷达图上圆点的大小和颜色代表技术的质量，换言之就是该技术或趋势对现有产品和市场的影响力有多大。

https://s.yam.com/EyuHi

https://s.yam.com/ZolZd

—--| 会议讲座 |--—

ICSIM 2024

2024年第七届软件工程与信息管理国际会议（ICSIM 2024）将于2024年1月23-25日在斐济在线举行。

会议面向对会议主题特别感兴趣的学者、研究人员和专业人士. 它汇集了软件工程和信息管理领域的学者、研究人员和专业人士，使会议成为分享经验、促进跨行业和学术界合作以及评估全球新兴技术的完美平台。提交的论文将经过同行评审（双盲），被录用的论文将发表在 ACM 国际会议论文集（ISBN: 979-8-4007-0919-7）上，并被 Ei Compendex、Scopus、CPCI、IET 等检索. 主要数据库。

详情请访问：

https://nldml2024.org/

—--| 论文推荐 |--—

Densest Subgraph Discovery

本周推荐的是发表于SIGMOD 2023的论文：Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery，该文提出一种求解（近似）最稠密子图的算法，作者来自香港中文大学和皇家墨尔本理工大学。

最稠密子图问题（densest subgraph problem，DSP）在不同领域有广泛应用。各种应用中的不同要求导致不同场景下的DSP问题的密度（density）定义不一样。然而，现有的DSP算法难以扩展到有效又准确地处理这些变体。为了填补这个空白，该文首先将不同的密度度量统一到一个广义的密度定义中（该密度定义和其他的密度定义的关系如下图所示），然后进一步提出了一个新的模型，𝑐-core，来定位最稠密子图。

基于c-core定位来缩小搜索范围的算法如下图所示。

大量实验表明，该文的𝑐-core-based优化可以提供超过基线三个数量级的加速。此外，该文研究了DSP在顶点数目约束下的一个重要变体，即k-最稠密子图问题（densest-at-least-k-subgraph (Dal𝑘S) problem，Dal𝑘S）的近似问题。该文提出了一种基于图分解的算法（大致流程如下图所示）。

实验表明该算法很可能给出一个至少是最佳密度的0.8的解，而最先进的方法只能确保一个密度至少是最佳密度的0.5的解；且对于三分之一以上的所有可能的顶点数目约束，该算法可以返回至少达到最佳密度的0.99的解。

该论文链接https://dl.acm.org/doi/10.1145/3589314，代码链接https://github.com/Xyc-arch/Efficient-and-Effecive-algorithms-for-generalized-densest-subgraph-discovery，感兴趣的读者可以关注。