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

"基于变迁图编辑距离的流程相似性算法" 本文主要探讨了一种新的流程相似性算法，该算法是基于变迁图编辑距离的。在企业模型库中查询和检索模型时，这种算法能够提高效率。文章首先介绍了变迁图的概念，它是流程建模的一种表示方式，通过对活动和转换关系的抽象，能有效地描述业务流程。变迁图的生成方法包括从流程模型（如Petri网）中提取关键元素，如活动和控制流，然后构建出反映这些元素相互关系的图结构。 接下来，文章提出了边的长度概念，这是衡量图编辑操作代价的基础。边的长度可以表示两个活动之间的相对复杂性或时间消耗。删除和插入边的代价取决于边的长度，这使得算法能够更精细地量化图形结构的变化。基于这一思想，定义了图编辑操作（如删除、插入和替换节点或边）及其相应的代价函数。此外，文章还阐述了一种节点匹配算法，用于计算两个变迁图之间的最小图编辑距离，即最小化将一个图转换成另一个图所需的代价。 随后，作者给出了过程模型相似性的定义，这是一种衡量两个流程模型之间相似程度的度量。该定义考虑了模型的结构和行为特征，并提供了计算两个模型相似性的具体方法。相似性计算不仅基于最小图编辑距离，还可能涉及其他因素，如活动的语义相似性和顺序关系的保留。 在实证研究部分，该算法的正确性和有效性得到了验证。通过一系列实验，证明了算法满足七条相似性性质，这些性质反映了算法在处理不同情况下的合理性和一致性。此外，还证明了变迁图编辑距离满足四条距离性质，这些性质确保了距离度量的合理性，如对称性、三角不等式等。 文章的作者团队由几位在Petri网理论与应用、业务流程管理系统以及可信软件领域的专家组成。他们的研究得到了多项国家级和省级基金的支持，包括国家自然科学基金和安徽省的科研基金项目。 这篇论文提供了一种新颖的流程相似性度量方法，它基于变迁图编辑距离，旨在优化企业模型库中的模型检索效率。通过引入边的长度和精心设计的图编辑操作，该算法能够更精确地评估流程模型之间的相似性，对于业务流程分析、模型重用和过程改进具有重要的实践意义。