王一舒 袁 野 刘 萌 王国仁

1(东北大学计算机科学与工程学院 沈阳 110004) 2 (北京理工大学计算机学院 北京 100081) (yishuwang@stumail.neu.edu.cn)

近年来，随着语义网络(semantic Web)、社交网络(social networks)、生物网络(biological networks)等新兴领域的飞速发展，数据的结构越来越复杂，数据量呈几何状增长，并且这种增长趋势还在不断的持续[1].图(graph)作为一种特殊的数据存储模型，在大规模数据中的应用越来越广泛，实现对复杂数据的存储和分析.图作为一种抽象的数据类型，从概念上可以分2种类型：有向图(directed graph)和无向图(undirected graph).每个图数据结构包含了一组顶点(vertices)用来表示对象，顶点间由有向或者无向的边(edges)连接，用来表示对象与对象之间的二元关系.在实际应用中，图的顶点和边上常常带有特定的信息，像标签或者数字属性等(如长度、花销等).例如，用图来表示一个城市之间的到达关系，其中每个顶点表示一个城市，若2个顶点之间存在边，则表示2个城市之间是可以直接到达的，在这种情况下，边上会有用来表示2个城市之间距离信息的标签.随着图上的研究不断深入，研究者们发现有些网络会随着时间不断变化，例如在上面的例子中，若在边上加上表示时间的标签，那么就可以表示该城市的公交车辆运输网络，边上的时间表示这条道路上公交车的起始时间.如何在这类随时间变化的图上进行查询处理与挖掘工作成为了当前热门的研究领域，为了更好地为这类随时间变化的图构建模型，研究者们提出了一种新型的图模……