论文阅读报告: 在时间双向图上查询基于时间的的密集子图 | ICDE 2024

摘要

本文提出了一个新的模型(α, β, T)-core,用于在时间双向图上寻找凝聚子图。时间双向图中,不同实体之间的关系随着时间的推移而变化。为了提高查询效率,本文提出了顶点分区和时间分区的历史索引(VH-Index和TH-Index),并进一步提出了时间交集索引(TH*-Index)。实验结果表明,本文提出的模型和算法在多个真实数据集上表现出色。

什么是时间双向图

时间双向图(Temporal Bipartite Graph)是指在图中存在两类不同的顶点集合,并且这些顶点之间的关系(边)随着时间的推移而变化。每条边都有一个时间戳,表示该边在特定时间发生。时间双向图可以用于建模许多现实世界的应用场景,如用户-商品购买关系、作者-论文发表关系等。

时间双向图的构成

  1. 顶点集合
    • 上层顶点集(U):表示一种类型的实体。例如,在用户-商品购买网络中,上层顶点可以表示用户。
    • 下层顶点集(L):表示另一种类型的实体。例如,在用户-商品购买网络中,下层顶点可以表示商品。
  2. 边集合(E)
    • 边连接上层顶点和下层顶点,表示两种实体之间的关系。例如,用户购买商品。在时间双向图中,边带有时间戳,表示这种关系发生的时间。

举例说明

我们以一个简化的用户-商品购买网络为例,其中:

  • 顶点集U表示用户
  • 顶点集L表示商品
  • 边表示用户在某一时间购买某一商品
  • 每条边都有一个时间戳,表示购买时间

假设有以下用户和商品:

  • 用户U: {Alice, Bob, Carol}
  • 商品L: {Book, Pen, Notebook}

时间双向图的边集可以如下表示:

  • (Alice, Book, 2024-01-01): 表示Alice在2024年1月1日购买了Book

  • (Bob, Pen, 2024-01-03): 表示Bob在2024年1月3日购买了Pen

  • (Alice, Notebook, 2024-01-05): 表示Alice在2024年1月5日购买了Notebook

  • (Carol, Book, 2024-01-06): 表示Carol在2024年1月6日购买了Book

  • (Bob, Notebook, 2024-01-07): 表示Bob在2024年1月7日购买了Notebook

    在这里插入图片描述

研究背景

在许多现实世界的应用中,例如作者-论文网络、用户-物品网络等,不同实体之间的关系可以自然地表示为双向图。双向图由两类顶点和连接它们的边组成,这些边只在不同类别的顶点之间存在。在时间双向图中,边不仅连接不同类别的顶点,还带有时间戳,表示这种关系在某一特定时间发生或存在。随着时间的推移,这些关系会发生变化,形成时间双向图。传统的凝聚子图(密集子图)模型没有考虑时间维度,因此无法捕捉关系的动态变化。为了弥补这一不足,本文提出了时间双向图上的(α, β, T)-core模型。

研究问题

本文研究的问题是在时间双向图上找到满足给定度约束的最大子图。具体来说,给定时间窗口T=[ts, te],以及度约束α和β,目标是找到一个子图,使得在该时间窗口内,上层和下层顶点的度分别至少为α和β。

主要贡献

  1. 提出新的凝聚子图模型(α, β, T)-core:该模型结合了时间维度,能够捕捉关系的动态变化。
  2. 设计了高效的索引结构:包括顶点分区历史索引(VH-Index)、时间分区历史索引(TH-Index)和时间交集索引(TH*-Index),以提高查询效率。
  3. 开发了高效的构建和查询算法:提出了顺序和并行算法,用于高效构建时间交集索引。
  4. 实验验证:在10个真实数据集上进行了大量实验,验证了模型和算法的有效性和效率。

预备知识

本文使用了一些基本的数学符号和定义:

  • 时间双向图G(V, E):V表示顶点集,E表示带有时间戳的边集。
  • U(G)和L(G):分别表示上层和下层顶点集。
  • 快照G[ts, te]:表示在时间窗口[ts, te]内的子图。
  • 度和邻居:顶点u在图G中的度表示为deg(u, G),邻居集表示为N(u)。

索引的基本思想

  1. 顶点分区历史索引(VH-Index)

    • 基本思想:存储每个顶点在不同时间窗口内的状态,以便快速检索满足(α, β, T)-core条件的顶点。
    • 实现方式:对于每个顶点u,VH-Index存储所有可能的(α, β, T)-core组合的时间窗口。
  2. 时间分区历史索引(TH-Index)

    • 基本思想:通过按时间存储顶点,减少查询过程中需要访问的顶点数量。
    • 实现方式:TH-Index按时间分区存储顶点,将每个时间窗口内的(α, β, T)-core顶点集合存储在一起。
  3. 时间交集索引(TH-Index)*:

    • 基本思想:结合VH-Index和TH-Index的优点,既减少存储空间,又提高查询效率。
    • 实现方式:通过存储代表性的时间点,减少冗余信息的存储,并在查询时进行交集计算。

索引的构建

  1. 顶点分区历史索引(VH-Index)

    • 步骤:
      1. 对于每个顶点u和每个可能的α、β组合,计算u在不同时间窗口内的状态。
      2. 存储每个顶点在不同时间窗口内的状态,以便快速查询。
    • 构建算法:
      • 通过对图进行多次遍历,依次计算每个顶点在各个时间窗口内的(α, β, T)-core状态,并将这些状态存储在VH-Index中。
  2. 时间分区历史索引(TH-Index)

    • 步骤:

      1. 按时间窗口对图进行分割,计算每个时间窗口内的(α, β, T)-core顶点集合。
      2. 存储这些顶点集合,以便快速查询。
    • 构建算法:

      • 对于每个时间窗口,计算(α, β, T)-core,并将结果存储在相应的时间分区中。

        在这里插入图片描述

  3. 时间交集索引(TH-Index)*:

    • 步骤:
      1. 选取代表性的时间点,计算这些时间点内的(α, β, T)-core。
      2. 存储这些代表性时间点的结果,减少冗余信息。
      3. 在查询时,通过这些代表性时间点进行交集计算,快速得到查询结果。
    • 构建算法:
      • 通过逐步增加时间窗口的大小,计算并存储代表性时间点的(α, β, T)-core,并将结果存储在TH*-Index中。

查询

  1. 基于顶点分区历史索引(VH-Index)的查询
    • 步骤:

      1. 根据查询参数α、β和时间窗口T=[ts, te],在VH-Index中查找每个顶点u的状态。
      2. 通过二分搜索找到满足条件的时间窗口,收集符合条件的顶点。
    • 算法

      def query_vh_index(VH_Index, alpha, beta, ts, te):result = set()for vertex in VH_Index:time_windows = VH_Index[vertex][alpha][beta]for window in time_windows:if window.start >= ts and window.end <= te:result.add(vertex)return result
      
  2. 基于时间分区历史索引(TH-Index)的查询
  • 步骤:
    1. 根据查询参数α、β和时间窗口T=[ts, te],在TH-Index中查找相应时间窗口内的顶点集合。
    2. 通过二分搜索找到符合条件的顶点集合,返回结果。
  • 算法
def query_th_index(TH_Index, alpha, beta, ts, te):result = set()for t in range(ts, te + 1):if TH_Index[alpha][beta][t]:result.update(TH_Index[alpha][beta][t])return result
  1. 基于时间交集索引(TH*-Index)的查询
  • 步骤:

    1. 根据查询参数α、β和时间窗口T=[ts, te],分别在TH*-Index的前向索引和后向索引中查找符合条件的顶点集合。
    2. 计算前向索引和后向索引的交集,得到最终结果。
  • 算法

    def query_th_star_index(TH_Star_Index, alpha, beta, ts, te):forward_result = set()backward_result = set()# 查询前向索引for t in range(ts, TH_Star_Index.max_time):if TH_Star_Index.forward[alpha][beta][t]:forward_result.update(TH_Star_Index.forward[alpha][beta][t])# 查询后向索引for t in range(te, -1, -1):if TH_Star_Index.backward[alpha][beta][t]:backward_result.update(TH_Star_Index.backward[alpha][beta][t])# 计算交集return forward_result.intersection(backward_result)
    

实验结果

  1. 实验设置:实验在10个真实数据集上进行,评估模型和算法的性能。

  2. 结果分析:结果表明,提出的模型和算法在不同数据集上的表现优异,查询效率和索引构建时间均有显著提升。

    在这里插入图片描述

    图7展示了不同数据集上构建TH*-Index的内存使用情况和时间成本。黑色柱状图表示原始图的大小,白色柱状图表示TH*-Index的大小,折线图(带三角形标记)表示构建TH*-Index所需的时间。可以观察到,大多数情况下,TH*-Index的大小显著大于原始图的大小,这表明索引构建会增加内存开销。同时,构建TH*-Index的时间随数据集大小的增加而显著增加,尤其是在较大的数据集(如RU)上,构建时间超过了10^5秒。尽管构建TH*-Index需要较大的内存和时间成本,但它显著提高了查询效率,特别是在需要频繁查询的大规模时间双向图上。因此,对于这些场景,构建TH*-Index是值得的,而在较小数据集或查询频率较低的场景下,则需要权衡索引构建的必要性。

    在这里插入图片描述

结论

本文提出了第一个适用于时间双向图的凝聚子图模型(α, β, T)-core,并设计了高效的索引结构和算法。通过大量实验验证,本文提出的方法在实际应用中具有很高的效率和实用性。未来的研究方向可以包括进一步优化索引结构和算法,以处理更大规模的时间双向图。此外,可以探索该模型在更多实际应用中的潜力,例如社交网络中的社区检测、电子商务中的推荐系统、以及生物网络中的功能模块识别等。这些应用可以利用本文提出的模型和算法,来有效地分析和挖掘数据中的动态关系,从而提供更有价值的见解和服务。

论文地址:https://www.researchgate.net/publication/382506975_Querying_Historical_Cohesive_Subgraphs_Over_Temporal_Bipartite_Graphs

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

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

相关文章

Java学习Day24:基础篇14:多线程

1.程序、进程和线程 程序 进程 进程(process)是程序的一次执行过程&#xff0c;或是一个正在执行的程序。是一个动态的过程&#xff1a;有它自身的产 生、存在和消亡的过程。 如&#xff1a; 运行中的QQ运行中的音乐播放器视频播放器等&#xff1b;程序是静态的&#xff0c…

【大模型从入门到精通13】openAI API 构建和评估大型语言模型(LLM)应用1

这里写目录标题 构建和评估大型语言模型&#xff08;LLM&#xff09;应用开发性能评估指标从开发到部署高风险应用LLM应用开发的最佳实践和建议从小处着手快速迭代自动化测试根据应用需求定制评估考虑伦理影响 构建和评估大型语言模型&#xff08;LLM&#xff09;应用 开发和部…

Sqli-labs-master靶场--布尔盲注

目录 1、布尔盲注 2、布尔盲注的流程&#xff08;以靶场less-8为例&#xff09; 2.1输入id尝试是否存在注入点 2.1.1通过以上尝试&#xff0c;联想到可能是布尔盲注 2.2猜测数据库长度 2.3获取数据库名 2.3.1python脚本获取 代码&#xff1a; 获取结果为&#xff1a; …

Hive SQL ——窗口函数源码阅读

前言 使用Starrocks引擎中的窗口函数 row_number() over( )对10亿的数据集进行去重操作&#xff0c;BE内存溢出问题频发&#xff08;忘记当时指定的BE内存上限是多少了.....&#xff09;&#xff0c;此时才意识到&#xff0c;开窗操作&#xff0c;如果使用 不当&#xff0c;反而…

1. js混淆-源码乱码

目录 调试干扰参数逆向 调试干扰 打开开发者工具&#xff0c;首先会进入 setInterval 生成的 debugger 将 uzt.js uyt.js 内容替换 将这两个文件的内容置空&#xff0c;并刷新页面就可以正常调试了 参数逆向 点击翻页&#xff0c;可以发现 https://match.yuanrenxue.cn/api…

Arduino导入实例程序的过程,实例包文件却编译显示缺失文件

参考中实例程序中的readme.txt 导入方式 下面是文档中的使用方式 1.基本信息&#xff1a; 本例程是基于Arduino进行开发的&#xff0c;例程均在E-Paper ESP8266 Driver Board上进行了验证;2.基本使用&#xff1a;方法1&#xff1a;将整个esp8266-waveshare-epd文件夹复制到C…

【Go】通过反射解析对象tag信息,实现简易ORM

反射是运行时&#xff0c;需要在运行时解析类型信息&#xff0c;编译期无法优化这些操作&#xff0c;因此比编译时已知类型信息的直接调用效率要低。 package mainimport ("fmt""reflect""strings" )type Person struct {Name string json:&quo…

PicGo + gitee 免费搭建个人图床

目录 1 图床概念2 使用gitee和PicGo搭建图床流程2.1 下载安装PicGo工具 3 图片上传错误处理3.1 PicGo客户端提示404错误信息图片上传失败3.2 PicGo客户端提示400错误信息图片上传失败 1 图床概念 ​ "图床"是一个网络术语&#xff0c;它指的是一种用于存储和托管图片…

理解张量拼接(torch.cat)

拼接 维度顺序&#xff1a;对于 3D 张量&#xff0c;通常可以理解为 (深度, 行, 列) 或 (批次, 行, 列)。 选择一个dim进行拼接的时候其他两个维度大小要相等 对于三维张量&#xff0c;理解 torch.cat 的 dim 参数确实变得更加抽象&#xff0c;但原理是相同的。让我们通过一…

算法力扣刷题记录 六十九【动态规划基础及509. 斐波那契数】

前言 调整一下做题顺序&#xff0c;多个章节同步进行&#xff0c;穿插练习。可以在各章节的专栏中找同一类。 记录 六十九【动态规划基础】。 一、动态规划理论基础学习 参考学习链接 二、509. 斐波那契数 2.1 题目阅读 斐波那契数 &#xff08;通常用 F(n) 表示&#x…

html+css+js网页设计 中国移动5个页面(带js)

htmlcssjs网页设计 中国移动5个页面&#xff08;带js&#xff09; 网页作品代码简单&#xff0c;可使用任意HTML编辑软件&#xff08;如&#xff1a;Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等操作&#xf…

Cpp中的this指针--复习记录

1.什么是this指针? 每个类都有一个this指针&#xff0c;我们的非静态成员函数可以通过这个this指针来操作对象的成员属性。this指针存储的就是类的实例的地址&#xff0c;this指针时时刻刻指向的都是这个实例对象本身。 由下图可知: 我在主函数中栈上创建了一个类的实例(由操…

【Python-实操】LabelMe to YOLOv8 Converter

LabelMe to YOLOv8 Converter 这是一个 Python 脚本&#xff0c;用于将 LabelMe 标注工具导出的 JSON 文件转换为 YOLOv8 格式的标注文件&#xff0c;并同时在图像上绘制标注的多边形。 功能 读取 LabelMe JSON 文件。解码并显示图像。从 classes.txt 文件加载类别标签。将多…

Java | Leetcode Java题解之第327题区间和的个数

题目&#xff1a; 题解&#xff1a; class Solution {public int countRangeSum(int[] nums, int lower, int upper) {long sum 0;long[] preSum new long[nums.length 1];for (int i 0; i < nums.length; i) {sum nums[i];preSum[i 1] sum;}BalancedTree treap ne…

Java参数传递

Java参数传递 一、 方法重载 一个类中可以存在多个同名的方法&#xff0c;只要这些方法的参数列表不同即可。 参数列表不同&#xff1a;参数个数或者参数类型不同方法重载与修饰符、返回值类型等统统无关&#xff0c;只看参数列表 二、 可变个数的形参 从Java5.0开始&…

陶瓷材质的防静电架空地板越来越受欢迎的原因

目前市面上的陶瓷防静电架空地板主要分为两种&#xff1a;钢基和硫酸钙基。前者是以全钢冲孔裸板作为板基&#xff0c;经粘接、固定整型和灌浆的方式加工而成&#xff0c;后者是以复合硫酸钙板为基材&#xff0c;表面粘接防静电陶瓷砖&#xff0c;四周导电PVC边条封边。近年来陶…

【C++】vector 的模拟实现

&#x1f4e2;博客主页&#xff1a;https://blog.csdn.net/2301_779549673 &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01; &#x1f4e2;本文由 JohnKi 原创&#xff0c;首发于 CSDN&#x1f649; &#x1f4e2;未来很长&#…

02_快速启动 Demo 创建 Electron 项目、electron-forge 搭建一个 electron 项目、手动创建electron项目

快速启动 Demo 创建 Electron 项目 一、克隆一个仓库、快速启动一个项目二、electron-forge 搭建一个 electron 项目三、手动搭建一个 electron 项目四、开发工具中配置 Eslint 一、克隆一个仓库、快速启动一个项目 要使用 git 的话首先电脑上面需要安装 git //克隆示例项目的…

Qt3D给圆环等立体图形添加纹理图片

添加纹理图片&#xff0c;首先需要自己找一个纹理图&#xff0c;当然了&#xff0c;随便什么图片都行。 创建3D图形的主要步骤查看另一篇文章。 这里主要代码如下&#xff1a; 使用QTextureLoader加载图片&#xff0c;图片路径需为qrc:/的路径。 auto *planeTransform1 ne…

嵌入式学习day13(C高级Linux命令)

一丶进程管理命令 1.grep 功能&#xff1a;从文件中查找字符串 格式&#xff1a;grep "要查找的字符串" 文件名 精确查找&#xff1a;grep "\<要查找的字符串\>" 文件名 结合ps以及管道&#xff1a;ps -ef | grep a.out: 从进程信息中查找带…