动态图数据上查询与挖掘算法的研究综述

2017年02月16日

读论文《动态图数据上查询与挖掘算法的研究综述》总结

1.综述

图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系。对于图数据模型的研究很久也很多,但主要是集中在静态图模型的研究。而现实应用中,图数据的结构和内容是会随着时间的推移发生演绎与进化。以下将从动态图数据模型上的查询算法与挖掘算法方面进行讨论。

2.研究背景和应用意义

2.1 背景

图数据已广泛地用于刻画现实世界中各类实体间的复杂关系,然而,在现实世界中,实体对象间的关系却每时每刻都 在发生着变化。传统静态图数据上各类问题的解决算法却无法应用于动态图数据上各类问题的高效解决。对动态图数据的相关查询与挖掘算法研究有着重要意义。

2.2 什么是图数据

“图”作为离散数学和计算机科学中基本的数据结构,可以有效地表示存在多种关联的数据以及内部具有一般性结构的数据”图中,每个顶点代表现实世界中的实体对象;两个不同顶点之间则可能会存在一条或多条边,由其代表不同实体之间存在的某种关系。

2.3 什么是动态图

又叫演绎图(evolving graph),是指会随时间而发生变化的图模型或者图数据。动态图可以根据变化形式分为: (1)结构变化,图中拓扑结构发生变化; (2)内容变化,图中顶点和边所代表数据对象内容、或者图中某一个特点对象的评价方式发生变化。

2.4 动态图研究存在的主要问题

传统静态图数据上各类问题的解决算法却无法应用于动态图数据上各类问题的高效解决:

(1)传统的静态图模型无法描述图数据随时间发生演绎与进化的情况;

(2)传统的静态图数据模型上的各类问题的定义在动态图数据模型上不再适用;

(3)图数据的动态性使得各类问题的计算复杂性大大增加,原有静态图上的各类方法将无法有效地解决这些问题;

(4)现有的动态数据管理的研究主要集中于数据流和传统关系数据的动态维护,但却无法处理结构复杂的图数据。

必须提出更为优质的方法能够随着时间变化高效地维护图结构,并且能够实时返回用户所需要的结果或者从动态图数据中挖掘得到更加实用的知识。

3.动态图伤的查询与挖掘算法研究工作

3.1 基于结构变化的动态图上的研究工作

过去几年间,研究者们对拓扑结构关系变化的动态图相关研究开展了大量效果卓著的工作。

3.1.1 图的经典问题在动态图上的研究

3.1.1.1 动态图上最短路径问题的研究

动态图上最短路径问题相关工作主要表现在: 当图的拓扑结构发生变化,即顶点和边发生插入和删除时,如何维护指定的顶点之间的最短路径;以及当图的拓扑结构发生变化,如何为任意图中两个顶点实时并迅速地找到两者之间的最短路径。

文献【1,2】 研究了平面图(Planar Graph) 上的最短路径维护问题;

文献【3】和文献【4】研究了非加权图上最短路径的维护问题;

文献【5】给出一个全局动态的算法FMN 来计算动态图上的单源最短路径问题,全局动态 (Fully Dynamic) 是指图中的顶点和边允许发生删除与插入。与全局动态对应的是衰减动态 (Decremental Dynamic) ,却只是允许图中发生顶点和边的删除操作;

文献【6】中给出了一个全局动态算法SWSF-FP来维护动态图上的最短路径,该工作要解决的是和文献【5】中相同 的问题;

文献【7】中对SWSF-FP算法进行了改进,并提出一个基于Dijkstra的算法的更新最短路径树,使得SWSF-FP算法可以用于具有多重边的动态图上;

文献【8】中提出了一个为图序列中每一个快照计算两点间最短路径的基本框架FVF;

文献【9】中首次给出了计算动态图中所有顶点对之间最短路径的全局动态算法;

文献【10】中则给出了一个改进的算法用于维护动态图中所有顶点对的最短路径。

3.1.1.2 动态图上最小生成树问题的研究

文献【11】中给出了一个全局动态的算法来维护动态图上的最小生成树,该方法利用了图分解理论将图划分成一组连通图的集合。当图中的边发生动态更新时( 插入或者删除) ,只有集合中的一部分连通图会受到影响。因此,算法将这部分连通图在最小生成树上的对应部分更新即可。

文献【12】采用Sparsification技术对文献【11】中的工作进行了改进,使得对每次边的更新,维护最小生成树的时间复杂度能够降至
文献【13】给出了一个最坏情况下时间复杂度为的全局动态算法,当动态图中的边每次发生更新时( 插入或者删除) ,该算法用于维护最小生成树的平摊时间即为,而回答最小生成树的查询却只需要的时间。

3.1.1.3 动态图上k连通分支问题的研究

文献【14】首次研究了动态图上连通分支(k = 1)的动态维护问题;

文献【15】首次提出了一个部分动态算法用于维护2-顶点连通分支;

文献【16】中研究了并行环境下动态图上对的k连通分支的维护问题,并给出一系列的理论结果;

文献【17】中提出一个抽象化模型用于描述图的连通结构,该模型能够有效地反应动态图中连通结构的变化,并能回答图中任意两个顶点是否属于同一个5-连通分支。

3.1.2 动态图上子图模式挖掘的研究

子图模式挖掘是图挖掘中一类十分重要的问题,目前,动态图上关于子图模式的研究主要集中两方面: 动态图上频繁子图模式挖掘和动态图上紧密子图挖掘。

动态图上的频繁子图模式挖掘是指在一个图的演绎过程中( 或者演绎图序列中) 找到具有相同变化过程的子图。

文献【18】将图中每一个顶点上或者每一条边上的一次变化称为一次“原子操作”,图序列中任意两个连续子图之间的 变化可用一系列的原子操作来表达。提出了名为GTRACE方法来计算序列中具有相同操作顺序的原子操作序列,并将其转化为动态图上的频繁子图模式。

文献【19】提出一种基于约束的挖掘算法来计算动态图上具有相同进化模式的频繁子图,其目的是根据用户给出的两种约束参数: 紧密度参数和频繁度参数,在动态图序列中找到足够紧密并且足够频繁的具有相同变化模式的子图。

文献【20】提出了在动态图序列中寻找一种新的模式,即图中的某几部分区域会以一定相关的方式发生进化。

文献【21】研究了如何在动态图集合中挖掘频繁子图模式”在该问题中,动态图集合是指一些图的集合,集合中的每一张图均会随时间发生变化。其目的是在这些动态图集合中找到一组具有相同演变模式的频繁子图“该问题与图数据 库中频繁子图模式挖掘的问题相类似”。

文献【22】研究了在动态图序列中挖掘具有相同变化模式的频繁树结构的问题。

文献【23】中考虑了如何在多项式时间内计算得到周期性或者近似周期性的子图变化模式。

文献【24,25】则研究了如何在社会网络的进化过程中找到满足一定进化规律的团体组织。

3.1.3 动态图上变化探测相关问题的研究

文献【26】和文献【27】利用熵等信息论方法,适当分割图流,并在每一个流片段中发现相对高度互连的结点社团(community)。

文献【26】提出了一种动态张量分析的方法,将图的动态演变抽象为一个较小核心张量流和其对应图的映射矩阵。

文献【27】提出了GraphScope方法用于在大规模的动态演变图上发现联系紧密的社团(community) ,并探测这些社团发生显著变化的时间。

文献【28,29】提出了三种不同的代价函数,如最大公共子图,来检测图数据流在何时发生了显著改变。

文献【30】提出了在图数据流中计算图与图之间距离的优化方法。

3.2 基于内容变化的动态图上的研究工作

基于内容变化的动态图是指:图上顶点和边上的权值会随着时间发生变化。目前,关于内容变化的动态图方面的探讨主要集中于时间依赖图上最短路径的研究。

文献【31-33】研究了离散时间模型下的时间依赖最短路径查询。

文献【33】将出发时间区间平滑地离散为多个时间点,并依据这这些时间点将图中顶点和边复制多次。因此,时间依赖图就转化为一个规模增大的静态图。

文献【31】给出方法如何在这个静态图上完成最短路径查询。只是这一基于离散时间模型的方法并不能回答连续时间模型下的最短路径查询问题。

文献【32】中,图上每一条边均被赋予一组聚集属性,该聚集属性表示了这条边在不同时刻呈现的状态。

文献【34-38】研究了连续时间模型下的最短路径查询问题。

文献【34】提出了一种基于Bellman-Ford算法思想的求解方法。对图中任意顶点,该方法迭代计算到达该顶点的最早时刻,并利用这些中间结果,最终计算可得到达终点的最早时刻。最后,根据该时刻找到旅行时间最短的结果路径。

文献【35】提出了道路网中的速度流模型,该模型下,图中每条边的通过速度可以用一个分段线性的函数表示。该文提出一个基于Dijkstra算法思想的方法计算速度流模型下的最快路径查询问题。

文献【36】则给出了一种基于A*算法的扩展算法”该算法的主要思想是用一个优先队列维护所有待扩展的路径。对任意一个顶点,起点到这个顶点的最早到达时间函数就维护在优先队列中,该算法通过该顶点到终点的欧氏距离和网络中的最大速度,实现从顶点到终点的时间预估。算法根据预估时间弹出队列元素,并找到起点到终点的最短旅行时间路径。

文献【37】介绍了如何应用数据挖掘的方法找到各种条件下描述道路通过速度的模型。

文献【38】是目前最有效的解决TDSP问题的方法。该方法采用两阶段搜索策略:第一阶段,用优先队列更新图中所有顶点最早到达的时间函数,并最终计算出终点的最早到达时间函数。第二阶段,根据终点的最早到达时间函数找到旅行时间最小的路径。

文献【39】研究了时间依赖图下,具有时间限制的代价最优路径的查询问题,并给出了一个有效的两阶段算法计算时间限制下的代价最优路径。


版权声明:本文为博主原创文章,转载请注明出处 本文总阅读量