基于变迁图编辑距离的流程相似性算法

来源：计算机应用研究杂志2020年第4期北京时间：

作者：段瑞,方欢,方贤文,詹悦,

单位：安徽理工大学数学与大数据学院,安徽淮南232001；

摘要：为了提高从企业模型库中查询检索模型的效率，提出一种基于变迁图编辑距离的流程相似性算法。首先，给出了变迁图的概念及其生成方法；其次，提出边的长度概念，且删除和插入边的代价由该边的长度决定，基于此定义出图编辑操作及其代价，并用节点匹配算法计算最小图编辑距离；然后，给出两个过程模型的相似性概念和计算方法；最后，通过实验验证了算法的正确性且满足七条相似性性质，并验证了变迁图编辑距离满足四条距离性质。

关键词：Petri网,相似性度量,变迁图,图编辑距离,

基金资助：国家自然科学基金资助项目(61472003,61402011,61572035)；安徽省自然科学基金资助项目(1608085QF149)；安徽省高校优秀青年人才基金资助项目(gxyqZD2018038)；安徽省博士后基金资助项目(2018B288)；；