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

收稿日期：2013-04-24

基金项目：国家自然科学基金（61173023）。

作者简介：杨雅君（1983-），男，黑龙江哈尔滨人，博士研究生，主要研究方向：挖掘算法；

高宏（1966-），女，黑龙江哈尔滨人，博士，教授，博士生导师，主要研究方向：图数据管理、海量数据管理、物联网数据管理；

李建中（1950-），男，黑龙江哈尔滨人，教授，博士生导师，主要研究方向：并行数据库、无线传感器网络、海量数据计算等。

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

杨雅君， 高宏， 李建中（哈尔滨工业大学 计算机科学与技术学院， 哈尔滨 150001）摘要：近年来，图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系。然而，在现实世界中，描述实体对象的图数据的结构和内容往往不是固定不变的，而是会随着时间的推移发生演绎与进化。目前，越来越多的研究者开始关注动态图数据方面的研究问题，也涌现除了很多优秀的研究工作。总结了近年来动态图上查询算法与挖掘算法方面的基础性研究工作，讨论了现有的工作和动态图研究的发展方向。

关键词：动态图； 查询算法； 挖掘算法

中图分类号：TP393 文献标识码：A文章编号：2095-2163（2013）04-0024-05

Survey on Querying and Mining Algorithms on Dynamic Graphs

YANG Yajun ， GAO Hong， LI Jianzhong

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001，China）

Abstract：Recently， graphs has been widely used to model the complexity relationships among various entities in real applications. However， the structure and the content in graphs to describe real entities are always changing with time evolving. Today， more and more research works focus on the dynamic graphs and there exist many excellent results. This paper summarizes the works about querying algorithm and mining algorithm on dynamic graphs in the past year， and also discusses the future work about dynamic graphs.

Key words：Dynamic Graphs； Querying Algorithm； Mining Algorithm

1动态图研究的背景和应用意义

随着信息科技与互联网的高速发展，各个应用领域的信息量都呈现了爆炸性的增长趋势。因此，不同应用领域各自关注的实体对象之间的关系也变得愈加庞大和复杂。在这些复杂关系的背后，往往蕴含着巨大的科学价值和商业价值。由此，吸引了诸多领域的研究者都开始专注于实体对象之间关系的研究，如计算生物学领域中，蛋白质和酶之间所发生的复杂的交互、调控与代谢关系的研究；社会学领域中，对不同社交网络中人与人之间交际关系的研究；商业领域中，对金融网络和货币流通网络中商业关系的研究；以及互联网搜索领域中，不同网页之间超链接关系的研究。在这些领域中，如果采用传统的关系数据库来管理数据对象之间的这些错综复杂的关系，会用到巨量且昂贵的连接操作。因此，利用传统的关系数据库来研究复杂的结构化数据并不具备现实可行性。“图”作为离散数学和计算机科学中基本的数据结构，可以有效地表示存在多种关联的数据以及内部具有一般性结构的数据。图中，每个顶点代表现实世界中的实体对象；两个不同顶点之间则可能会存在一条或多条边，由其代表不同实体之间存在的某种关系。针对这种形式的结构化的数据，研究者们将其称作“图数据”。

近年来，图数据已广泛地用于刻画现实世界中各类实体间的复杂关系。例如，传感器网络中的节点拓扑结构图；互联网领域中的页面超链接关系图；计算生物学中的蛋白质交互和基因调控网络；社交网络中（如新浪微博、微信等）用户之间交互关系图及～Email～通信关系图；物流学领域中的交通网络、物流网络等等。这些例子清楚地表示，图数据现已无处不在，因此，对图数据进行管理则成为一个迫切重要的问题。由于图数据具有的重大科学意义和巨大社会价值，数据领域内的顶级学术会议SIGMOD、VLDB、ICDE、KDD以及重要学术会议CIKM、EDBT、ICDM等均设有与图数据管理有关的研讨议程。

然而，在现实世界中，实体对象间的关系却每时每刻都在发生着变化。以社交网络为例，根据Facebook网站2010年的Yearbook报告，仅仅2010一年间，其用户就从3.37亿人增至5.85亿人，平均每秒新增7.9位用户，同时，平均每分钟，会发生47 553个好友关系的建立或解除。2011年，Google+在上线后的两周时间内，增长了1 000万的用户。同年，Twitter～平均每天都活跃着2亿的用户，并且发生着超过16亿次的交互。这些数据无不在显示与说明，现实世界中实体对象间的关系都无时无刻地经历着变化。因此，描述实体对象的图数据的结构和内容往往不是固定不变的，而是会随着时间的推移发生各种演绎与进化的。