动态异质大图匹配模型及算法研究

项目名称： 动态异质大图匹配模型及算法研究

项目编号： No.61502349

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 自动化技术、计算机技术

项目作者： 祝园园

作者单位： 武汉大学

项目金额： 22万元

中文摘要： 图结构被广泛应用于多种领域，以描述事物之间的复杂关系。随着图的大量产生和积累，图处理技术成为众多学者和业界人士的研究热点。图匹配问题是图处理技术中的重要研究内容，其目标是确定两个图顶点之间的对应关系，以尽可能地保留它们的公共部分。目前很多应用领域的图数据呈现异质、大规模、动态变化的特性，而现有的图匹配算法主要针对静态同质图且计算复杂度过高，无法解决具有上述特性的异质大图匹配问题，这给研究者带来新的挑战和机遇。为此，本项目围绕动态异质大图匹配问题，从语义模型、匹配算法、动态更新三个方面，采用逐步推进的方式，依次研究异质大图匹配语义模型、语义模型约束下异质大图分布式匹配算法、异质大图匹配结果的动态更新方法，并研制动态异质大图匹配原型系统以验证基础理论研究成果的有效性和可行性。本项研究对于推动图处理技术的进一步发展以及满足应用领域对动态异质大图匹配的需求，具有重要的科学意义和应用价值。

中文关键词： 大图匹配；异质图；动态图；分布式计算

英文摘要： Graph has been prevalently used in a wide range of application domains to model the complicated relationships between data objects. With a large number of graphs generated and accumulated, graph processing has attracted great interests from both research and industrial communities. Graph matching is an important research topic in graph processing, with the aim of finding the node correspondences in two graphs to maximize the common part between these two graphs. In many applications, graphs are heterogeneous，large, and changing dynamically. Current solutions for graph matching problem are targeted at static graphs with very high computational complexity. Thus they cannot handle heterogeneous graphs as described above. To solve this problem, we study three sub-problems in heterogeneous graph matching, including heterogeneous graph matching model construction, heterogeneous graph matching algorithms, and dynamic maintenance of heterogeneous graph matching. We will also implement a prototype system for large-scale dynamic heterogeneous graph matching to verify the proposed theories and techniques.This project will make significant contribution for the further development of graph processing techniques and solving the problem occurred in many application domains.

英文关键词： large graph matching;heterogeneous graph;dynamic graph;distributed computation