大规模图数据的最大k边连通子图查询处理研究

Cohesive subgraph analysis and processing refers to querying or searching a subgraph with closely-connected vertices from a graph, which is a cutting-edge technology and has significant commercial value and social benefits. Recently, with the increasing scale of graph data, cohesive subgraph analysis and processing is becoming more complex, needing a fast cohesive subgraph query processing method to support it. In this project, we first analyze the challenges in current cohesive subgraph query processing techniques. Then, we adopt the maximal k-edge-connected subgraph as the cohesive subgraph model. Based on it, we mainly focus on developing the fast maximal k-edge-connected subgraph query processing techniques. Specifically, this project aims at solving the following three issues: the maximal k-edge-connected subgraph maintenance problem, the basic maximal k-edge-connected subgraph query processing problem, and the maximal k-edge-connected subgraph query processing for graph streaming data problem. Finally, we will integrate all the above techniques, and we plan to propose a maximal k-edge-connected subgraph query processing prototype system, which forms a foundation for maximal k-edge-connected subgraph based cohesive subgraph analysis and processing. The expected outputs of this project include more than ten high quality papers, as well as a self-developed maximal k-edge-connected subgraph query processing prototype system.

凝聚子图的分析处理是指从图数据中查询或者搜索顶点之间紧密相连的子图结构，是一项具有重大商业价值和社会效益的前沿技术。近年来，随着图数据规模的不断增大，凝聚子图分析处理的复杂性越来越高，这就迫切需要提出一套快速的凝聚子图查询处理方法加以支持。本项目深入分析当前凝聚子图查询处理所面临的挑战，计划采用最大k边连通子图的凝聚子图模型，在此基础上重点研究最大k边连通子图的快速查询处理技术。具体地，本项目旨在解决以下三个基本问题：面向图流数据的最大k边连通子图动态维护算法、最大k边连通子图的基本查询处理，以及支持图流数据的最大k边连通子图快速查询处理技术。集成以上技术，本项目将最终提出一套支持大规模图数据的最大k边连通子图查询处理原型系统，为基于最大k边连通子图的聚子图分析处理奠定基础。本项目预期产生具有国际影响的研究成果，包括高水平论文10篇以上，以及自主研发的最大k边连通子图查询处理原型系统。

近年来，凝聚子图的挖掘和搜索已经成为数据库和数据挖掘领域的一大研究热点。凝聚子图的挖掘和搜索对分析大规模社交网络中的社区探测、用户朋友圈子挖掘等具有重要意义。本项目主要研究了大规模图数据中的凝聚子图搜索问题。首先，本项目提出了一种基于k-核凝聚子图的影响社区模型，该模型不仅能够刻画子图的凝聚程度，而且还能够刻画该子图在网络中的重要性。基于这一模型，本项目开发了一种新型的树型索引结构，该索引结构可以用于支持快速的影响社区搜索。而且，本项目还提出了一种高效的索引维护技术，用于支持面向动态图数据的影响社区搜索。相关科研成果发表在数据库领域的CCF A类会议VLDB 2015以及CCF A类期刊VLDB Journal上。其次，本项目还开发了一种基于k-truss凝聚子图的影响社区模型，并提出了一种类似的树型索引结构用于支持快速的k-truss影响社区搜索，相关成果发表在CCF B类期刊Information Sciences上。再次，本项目提出了一种统一于k-核和k-truss的凝聚子图模型，并且设计了一种高效的凝聚子图搜索算法，相关研究成果发表在数据库领域的CCF C类会议WISE 2017上。最后，我们提出了一种局部稠密的凝聚子图模型，并且设计了一套高效的求解算法来计算局部稠密的凝聚子图，相关成果发表在数据挖掘领域的CCF A类会议KDD 2015上。 ..此外，在本项目的支持下，我们还研究了基于斯坦纳树的凝聚子图搜索算法，以及针对动态图数据的结构聚类等相关问题，相关成果发表在数据库领域CCF A类会议SIGMOD 2016以及CCF C类会议WISE 2017上。