田朝霞 张 俊 陈 旭 曲贤菲

(大连海事大学信息科学技术学院 辽宁 大连 116026)

0 引 言

当今，动态性已经成为建模为图和网络的数据分析系统和应用程序的明显特征，如社交网络分析、生物数据分析、推荐系统和路径规划[1]。因此，动态网络引起了行业和学术界的重视，实际上，通常使用动态网络的各种替代术语，如时态网络、动态图、演化网络、时间依赖图和图流等[1-2]。现实世界的网络本质上是动态变化的，实体(节点)不断建立新的关系(边)，移除旧的关系。分析网络的时间维度可以提供有关其结构和功能的有价值的见解，例如，可以揭示时间模式、概念漂移、周期性和时间事件等[3]。

稠密子图发现是一个基本的图挖掘问题，已经成为广泛的数据分析任务中的原语，如社区检测[4]、事件检测[5]、链接垃圾邮件检测[6]和计算生物学[7]等。在理论计算机科学中已经广泛研究了稠密子图发现问题，由于该问题与实际应用的相关性，在社区数据挖掘中引起了相当大的关注。社交网络中紧密连接的用户可能对应于社区，也就是有相似兴趣或与同一组织(例如大学或公司)相关联的用户组。突然在推文中共同出现的城市、个人和公司名称等实体可能表明涉及相应实体的事件正在发生[2]。

在现实应用中，图数据会随时间发生动态变化，也就是所谓的时态图，时态图有两种变化形式：一种是图的拓扑结构变化，图中的节点和边随时间发生插入和删除，从而导致图的结构发生变化；……