计算机应用研究

作者：邱珍,郑朝晖,

单位：苏州大学a.计算机科学与技术学院;b.江苏省网络空间安全工程实验室,江苏苏州215008；

关键词：图编辑距离,等价映射,映射编码,下界计算,图相似性搜索,

基金：江苏省高校自然科学研究项目(19KJA550002)；江苏省高校优势学科建设工程资助项目；；

在图相似性搜索问题中，图编辑距离是较为普遍的度量方法，其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题，提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分，以此计算映射编码来判断等价映射；然后定义映射完整性更新等价映射优先级，选出主映射参与扩展；其次，设计高效的启发式函数，提出基于映射编码的下界计算方法，快速得到最优映射。最后，将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明，该算法具有更好的搜索性能，在搜索空间上最大可降低49%，速度提升了约29%。

来源：2023年第2期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2023年第2期