面向大规模时态图数据的社区搜索关键技术研究

Mining stable and persistent community structures from temporal graphs is a cutting-edge technology and has significant commercial value and social benefits. Recently, with the increasing scale of temporal graph data, community search is becoming more complex, thus needing a fast community search method to support it. This project first analyzes the challenges in current community search techniques for temporal graphs. Then, we propose a persistent k-core model. Based on this model, we mainly study the fast persistent k-core search techniques. Specifically, this project aims at solving the following three issues: study the persistent k-core model and its key properties; devise fast algorithm to find the persistent k-core; develop parallel search algorithm to identify the persistent k-core in large-scale temporal graph. Finally, we will integrate all the above techniques, and we plan to propose a persistent k-core search prototype system. The project is expected to produce high quality outputs, including more than ten high quality papers, more than three patents, as well as a self-developed persistent k-core search prototype system.

从时态图数据中挖掘稳定的、持久的社区结构是一项具有重大商业价值和社会效益的前沿技术。近年来，随着时态图数据的规模不断增大，社区搜索的复杂性越来越高，这就迫切需要提出一套快速的社区搜索方法加以支持。本项目深入分析了面向时态图数据的社区搜索技术所面临的挑战，提出了一种持久性k核的社区模型，在此基础上重点研究持久性k核的快速搜索技术。具体地，本项目旨在解决以下三个基本问题：提出持久性k核模型，并研究其关键属性；设计快速的持久性k核搜索算法；以及开发支持大规模时态图数据的持久性k核搜索的并行算法。集成以上技术，本项目最终将提出一套支持大规模时态图数据的持久性k核搜索原型系统。本项目预期产生具有国际影响的研究成果，包括高水平论文10篇以上，国内外发明专利2-3项，以及自主研发的持久性k核搜索原型系统。

近年来，面向时态图数据的社区挖掘已经成为了数据库和数据挖掘领域的研究热点。从时态图数据中挖掘稳定的、持久性出现的社区结构在社交网络分析、金融交易网络分析、电商网络分析等领域具有重要应用。本项目主要研究了面向大规模时态图数据的持久性社区搜索问题。首先，本项目提出了一种持久性k核的社区模型，该模型不仅能够刻画社区的稠密度，而且还能刻画社区的持久性。基于该模型，本项目设计了一套新颖的元区间分解技术。基于该技术，设计了一套度持久性k核的剪枝模型。通过计算该模型，可以对原始时态图数据进行大幅削减。最后，在削减后的时态图数据上，本项目开发了一套基于分支定界的回溯搜索技术来计算所有的持久性k核。相关的研究成果发表在数据库领域的CCF A类会议ICDE 2018上。其次，项目组还系统研究了面向时态图数据的周期子图搜索问题。首次提出了一种周期团的新型社区模型，并且开发了一套高效的周期团枚举算法。相关研究成果发表在数据库领域的CCF A类会议ICDE 2019，以及CCF A类期刊IEEE TKDE上。此外，在本项目的资助下，项目组针对不同图数据类型的社区搜索问题进行了深入研究，取得了一系列创新性成果。相关成果累计发表CCF A类会议SIGMOD、VLDB、ICDE，以及CCF A类期刊VLDB Journal和IEEE TKDE论文19篇，CCF B类会议CIKM和ICDM各1篇，CCF A类中文期刊论文2篇。申请中国发明专利12项，培养已毕业的硕士生6人，指导在读硕士生12人，博士生3人，在站博士后1人。超额完成了本项目预先制定的研究目标。