基于consR的并行图匹配方法

来源：计算机技术与发展杂志2015年第07期北京时间：

作者：田豪爽;戴东波;张惠然;谢江

摘要：随着社交网络、生物网络规模的迅速扩大,能够快速、高效地实现对这些网络的匹配、查询等工作已经成为许多应用领域的迫切需求。给定两个网络图,图匹配的过程即为对图G1中的每个节点在图G2中找到唯一一个相对应的最为相似的节点,使得给定的两个图的匹配边的数量最多。文中基于大图匹配方法consR,进行了两方面的优化：当图的节点数目较少时,优化了图G1、G2的相似性矩阵计算策略,从而使得图匹配的计算更加快捷；当图的节点数目较大时,针对匹配过程中最为耗时的步骤进行并行优化处理。实验结果表明,在与consR方法计算出的匹配结果保持一致的情况下,一定程度上缩短了图匹配计算时间。

关键词：图匹配;consR算法;归并排序;并行化