大规模动态图中不稳定子结构挖掘算法研究

With the development of information technology, more and more large graphs have emerged in various applications. These graphs are always dynamic, i.e., they evolve over time. Therefore, knowledge mining from dynamic graphs becomes very important. This project targets at mining unstable sub-structures from large dynamic graphs. An unstable sub-structure is a special kind of sub-graph or vertex subset in which the relationships between vertices change frequently most. Mining unstable sub-structures is of great significance in real applications such as the social network and the intelligent transportation. However, there is no work on this problem so far to our best knowledge. This project conducts research on the semantic definitions of the unstable sub-structures, the basic operation algorithms and the unstable sub-structure mining algorithms on large dynamic graphs. First, we propose several reasonable models for unstable sub-structures. Second, we study what kind of the basic operations to be involved in mining unstable sub-structures and then we develop the efficient basic operation algorithms. Finally, we develop the efficient algorithms for mining unstable sub-structures with the basic operations. This project also builds a prototype system to confirm the effectiveness and efficiency for the unstable sub-structure mining algorithms.

随着信息科技的高速发展，各个应用领域涌现出大量的大规模图数据。这些图数据往往是动态的，其无时无刻不在发生变化。因此，挖掘动态图知识就变得尤为重要。其中，挖掘动态图中的不稳定子结构是一个十分重要的问题。不稳定子结构是指图中的一类特定的子图或者顶点子集，其内部结构关系的变化频度或程度在整个动态图中是最为剧烈的。挖掘不稳定子结构在社会各个领域（如社交网络、智能交通）都有着十分重要的应用。然而，目前针对这一问题的研究还处于空白阶段，机遇和挑战并存。本项目将从不稳定子结构语义模型、动态图基本操作算法和不稳定子结构挖掘算法三个层面开展研究。首先，提出合理的不稳定子结构语义模型；然后，分析不稳定子结构挖掘所涉及的动态图基本操作，并设计高效的基本操作算法；最后，结合基本操作算法，设计高效的不稳定子结构挖掘算法。本项目还将开发一个通用的不稳定子结构挖掘原型系统，验证基础理论研究成果的有效性和可行性。

近年来，图数据作为一种用于反映实体对象之间复杂关系的良好数据类型，其规模呈现了爆炸性的增长趋势。然而在现实世界中，这些大规模的图数据无时无刻不在发生着变化。其中，挖掘动态图中的不稳定子结构是一个十分重要的问题。不稳定子结构是指图中的一类特定的子图或者顶点子集，其内部结构关系的变化频度或程度在整个动态图中是最为剧烈的。换言之，不稳定子结构内部的相互关系在整张图的动态变化过程中是最不稳定的。本课题从不稳定子结构语义模型、动态图基本操作算法和不稳定子结构挖掘算法三个层面开展研究。首先，提出合理的不稳定子结构语义模型；然后，分析不稳定子结构挖掘所涉及的动态图基本操作，并设计高效的基本操作算法；最后，结合基本操作算法，设计高效的不稳定子结构挖掘算法。本课题执行期间取得了良好的进展，多个研究成果在国内外高水平的学术会议和期刊发表。