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

摘要：

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

关键词：稠密子图;时序图;Top-k查询

所属期刊栏目：48

分类号：TP399(计算技术、计算机技术)

资助基金：国家重点研发计划项目2016YFCI401900

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

页数：共8页

页码：152-159