全文总字数：1600字

1. 研究目的与意义及国内外研究现状

图数据库是一种以图论为理论基础,描述并存储图中节点及其之间的关系的特定数据库。图能够表达更加丰富的语义，在社交网络、生物等领域有着广泛的应用，但这种丰富的语义也增加了数据结构的复杂性及挖掘令人感兴趣的子图的难度。社交网络的不断发展要求图分析技术快速准确，而子图匹配是图数据库的一个基本问题，它是一种计算、评估图差异性的方式，它的主要目标是发现两个图中部分或全部节点及边的映射关系，通过这种映射关系的紧密程度来判断两个图的相似程度。利用算法快速准确找到社交网络中的任意子图对于提高社交网络的分析效率尤为重要。本课题就社交网络中的子图匹配算法进行研究，期望通过对各种子图匹配算法的比较研究，寻找到高效的处理方法。

国内外研究现状

总体来说，现有的子图匹配算法大致有2步：首先是计算图的相似性矩阵，然后基于这个矩阵进行匹配。根据目前的研究情况，计算图的相似性矩阵方法大致分为2类:(1)计算所得结果是规范化的单一相似sim（g,g1）；(2)计算所得结果是代表第一个图中的点i和第二个图中每个点j相似性的一组xij。而匹配大多数依赖于特征向量，这些特征向量保留了很多有用的信息例如属性的差异性。常见的算法有基于信息熵的子图匹配等。

2. 研究的基本内容

本课题主要是对已有的子图匹配算法进行比较研究， 要研究内容包括：

（1）了解现有的子图匹配算法，对于其存在的几大类算法的应用场景及特点进行分析研究。随着图数据库的不断发展，许多图匹配算法被提出，而每个算法都有其各自的特点及适用领域，通过研究，希望能够对几大类算法的特点有所掌握。

（2）针对目前已有的许多子图匹配算法，选取其中比较典型的2-3种算法进行重点研究，通过研究掌握算法原理，能够构建图数据库，编码实现这几种算法，并进行实验测试，了解各个典型算法的特点，并就这几种算法进行比较。

3. 实施方案、进度安排及预期效果

实行方案及进度：

2015年12月：资料收集，完成任务书和开题报告，了解子图匹配算法的几大门类，确定2-3种典型的匹配算法以进行下一步研究；

2016年1月~2月（开学前）：学习几种典型的子图匹配算法；

4. 参考文献

[1]georgios kollias,olaf schenk,ananth grama and madan sathe.fast parallel algorithm for graph similarity and matching. in computer science technical reports,2012.

[2] d. e. drake and s. hougardy. linear time local improvements for weighted matchings in graphs. in wea’03 proceedings of the 2nd international con-ference on experimental and efficient algorithms,2003.

[3]d. gregor and a. lumsdaine. the parallel bgl: a generic library for distributed graph computations. in in parallel object-oriented scientific computing (poosc. citeseer, 2005.