Application of Sub-Graph Isomorphism to Extract Reoccurring Structures from BPMN 2.0 Process Models

摘要

The state-of-art approaches in structural similarities of process models base their operations on behavioral data and text semantics. These data is usually missing from mock-up or obfuscated process models. This fact makes it complicated to apply current approaches on these types of models. We examine the problem of the automated detection of re-occurring structures in a collection of process models, when text semantics or behavioral data are missing. This problem is a case of (sub)graph isomorphism, which is mentioned as NP-complete in the literature. Since the process models are very special types of attributed directed graphs we are able to develop an approach that runs with logarithmic complexity. In this work we set the theoretical basis, develop a configurable approach for the detection of re-occurring structures in any process models collection, and validate it against a set of BPMN 2.0 models. We define two execution scenarios and discuss the relation of the execution times with the complexity of the comparisons. Finally, we analyze the detected structures, and propose the configurations that lead to optimal results.