基于独立路径的流程差别检测算法

Difference detection algorithm for process models based on independent path

为了解决流程差别检测问题,提出一种基于圈复杂度和独立路径的流程差别检测算法。算法利用圈复杂度衡量流程的复杂度,并计算流程的独立路径。一个流程的独立路径数量与圈复杂度相等。然后通过KM算法将两个流程之间的独立路径进行最优匹配,使匹配后的独立路径的相似度最大,两个流程之间的独立路径的编辑操作即为流程之间的差别。通过大量实验证明了算法在有效性上能达到实际使用要求,并且能够在1s内完成流程差别检测。

To solve the detecting difference in business process management, a process differential detection algorithm based on circle complexity and independent path was proposed, which measured the process complexity by circle complexity and calculated the independent paths of the process. The number of independent paths for a process model was equal to circle complexity. To maximize the similarity of independent paths between two process models, KM algorithm was utilized to match independent paths optimally. Eventually, the edition operation sequence of independent paths between two process models was the difference between two process models. Extensive experiments were carried out to prove that the algorithm could achieve the practical requirement in terms of accuracy and detect differences within 1 second.