Efficient Comparison of Process Models using Tabu Search Algorithm

Skobtsov A., Kalenkova A. A.

Companies from various domains record their operational
behavior in a form of event logs. These event logs can be analyzed and
relevant process models representing the real companies’ behavior can be
discovered. One of the main advantages of the process discovery methods
is that they commonly produce models in a form of graphs which can be
easily visualized giving an intuitive view of the executed processes. Moreover,
the graph-based representation opens new challenging perspectives
for the application of graph comparison methods to find and explicitly visualize
differences between discovered process models (representing real
behavior) and reference process models (representing expected behavior).
Another important area where graph comparison algorithms can be
used is the recognition of process modeling patterns. Unfortunately, exact
graph comparison algorithms are computationally expensive. In this
paper, we adapt an inexact tabu search algorithm to find differences between
BPMN (Business Process Model and Notation) models. The tabu
search and greedy algorithms were implemented within the BPMNDiffViz
tool and were tested on BPMN models discovered from synthetic
and real-life event logs. It was experimentally shown that inexact tabu
search algorithm allows to find a solution which is close to the optimal
in most of the cases. At the same, its computational complexity is significantly
lower than the complexity of the exact A search algorithm
investigated earlier.

Keywords: process mining, BPMN, conformance checking, graph edit distance, Tabu search

Publication based on the results of: Synthesis, recovery, conformance checking, and other methods for the analysis of process models and distributed information systems (2019)

In book

Proceedings of the MACSPro Workshop 2019

Vol. 2478: CEUR Workshop Proceedings. , CEUR-WS.org, 2019.