大规模时序图中持续性稠密子图搜索算法研究

摘要：

时序图是一种边上带有时间戳的图结构,其中边上的时间戳表示该边出现时间,即图随时间变化不断变化.图数据中的稠密子图挖掘问题具有非常强烈的现实意义.目前,时序图中大多数现有的工作都集中在稠密子图检测问题,该问题目标是找到时序图中所有的目标子图.然而,当时序图的规模过大时,这一问题将变得极其复杂且收效甚微.旨在研究在时序图中长期被忽视的稠密子图搜索问题.具体来讲,给定一个图中的查询顶点,目标是找到一个在一段时间内持续存在且包含该查询点的稠密子图,即该子图满足时间持续性.从全局削减和局部扩展两种不同的思路出发,设计两种不同的高效稠密子图搜索算法,用以应对不同的应用场景.在四个真实世界网络中的大量实验,验证了提出算法的高效性.

关键词：时序图;持续性稠密子图;高效搜索算法

所属期刊栏目：58

分类号：T39

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;北京市教委科技项目;北方工业大学科研启动经费

在线出版日期：2022-02-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：119-126