时序图中Top-k稠密子图查询算法研究

• 作者: 穆聪聪 王一舒 袁野 乔百友 马玉亮
• 来源期刊: 计算机科学
• 关键词: 稠密子图 时序图 Top-k查询
• 年，卷（期）: 2021,（10）
• 所属期刊栏目: 数据库&大数据&数据科学|Database & Big Data & Data Science
• 页码范围: 152-159
• 页数: 8页
• 分类号: TP399
• 语种: 中文
• DOI: 10.11896/jsjkx.201100005

摘要

稠密子图的查询是图分析领域的重要研究问题之一,在社交用户相关性分析、Web中社群分析等方面都有着广泛的应用.目前,关于稠密子图查询的研究工作主要基于静态图.而在实际应用中,时序信息会对稠密子图查询产生重要的影响,使得图拓扑结构随时间序列不断发生变化,包含的信息量也不断增加,使得已有的针对静态图的查找方法不再适用于时序图.因此,如何高效地在时序图上查找稠密子图仍然是一个挑战.为了解决上述挑战,首先规范化地定义了基于时序图的稠密子图查找问题;然后,根据图的拓扑结构和包含时间标签的边之间的相似度,提出一种基于阈值的近似查找算法DTS-base.为了加快算法的收敛速度,提出了一个基于快速计算最大相似度时间片的优化算法DTS-opt.最后,通过在真实数据集上的实验,证明了所提算法的高效性和可扩展性.