大规模属性图上社团查询处理研究

Recently, community search over graphs has attracted significant attention and many algorithms have been developed for finding dense subgraphs from large graphs that contain given query nodes. In applications such as analysis of protein-protein interaction (PPI) networks, citation graphs, and collaboration networks, nodes tend to have attributes. Unfortunately, most previously developed community search algorithms ignore these attributes and result in communities with poor cohesion w.r.t. their node attributes. In this project, we study the problem of attributed-driven community search on big attributed graph, that is, given an undirected graph G where nodes are associated with attributes, and an input query Q consisting of nodes Vq and attributes Wq, find the communities containing Vq, in which most community members are densely inter-connected and have similar attributes. In addition, we investigate the attributed-driven community search problem in a graph streaming setting with frequent insertions and deletions of graph vertices, edges, and also attributes. Finally, we will integrate all the above techniques, and we plan to propose an attributed-driven community query processing prototype system, which forms a foundation for attributed-driven community search analysis and processing. The expected outputs of this project include more than eight high-quality papers, as well as a self-developed query processing prototype system.

现实网络中普遍存在大量的社团，他们一般以紧密的关系连接在一块。较于全局网络的社团确定问题，社团搜索拥有个性化查询和高效求解，最近得到大量关注和研究。但是目前大部分社团搜索还局限与紧密网络结构研究，未涉及到顶点带有属性的网络，例如蛋白质交互网络，文献互引图，合作网络。本项目研究大属性图上社团搜索问题，社团不仅在网络结构上紧密相连，在属性表现上非常一致。具体地，本项目旨在解决以下三个基本问题：有效的同属性社团模型设计、高效的同属性社团的查询处理，以及支持大属性图流数据的快速查询处理。集成以上技术，本项目将最终提出一套支持大规模属性图的社团查询处理原型系统，预期产生具有国际影响的研究成果，包括高水平论文8篇以上，为基于大属性图上社团查询处理分析处理奠定基础。

现实图数据中普遍存在大量以紧密关系结构连接的社团，社团搜索任务在于查找跟查询相关的社团。相比于另外一个社团确定问题，社团搜索并不需要进行全局图结构搜索，因而拥有个性化查询和高效求解等优点，在大规模图分析和可视化领域上具有广泛的应用。本项目研究大属性图上社团搜索，要求社团不仅在网络结构上紧密相连，在属性表现上非常一致。具体地，本项目解决三个社团搜索问题包括：有效的同属性社团模型设计、高效的同属性社团的查询处理，以及支持大属性图流数据的快速查询处理。我们提出多种高效的查询索引技术和针对不同查询条件的属性社团模型，还开发一套支持大规模属性图的社团查询处理原型系统。在本项目的支持下，项目组的相关工作包括撰写1部专著（大图上的社团搜索），发表论文20篇 （其中包括CCF A类会议期刊论文13篇，B类会议期刊论文5篇，C类会议期刊论文2篇），以及2项国际学术奖（WISE 2019 最佳论文奖 & ACM CIKM 2020 最佳论文提名奖）。