Geodesic
Application of genetic algorithms for finding edit distance between process models
Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 6, pp. 711-725.

Voir la notice de l'article provenant de la source Math-Net.Ru

Finding graph-edit distance (graph similarity) is an important task in many computer science areas, such as image analysis, machine learning, chemicalinformatics. Recently, with the development of process mining techniques, it became important to adapt and apply existing graph analysis methods to examine process models (annotated graphs) discovered from event data. In particular, finding graph-edit distance techniques can be used to reveal patterns (subprocesses), compare discovered process models. As it was shown experimentally and theoretically justified, exact methods for finding graph-edit distances between discovered process models (and graphs in general) are computationally expensive and can be applied to small models only. In this paper, we present and assess accuracy and performance characteristics of an inexact genetic algorithm applied to find distances between process models discovered from event logs. In particular, we find distances between BPMN (Business Process Model and Notation) models discovered from event logs by using different process discovery algorithms. We show that the genetic algorithm allows us to dramatically reduce the time of comparison and produces results which are close to the optimal solutions (minimal graph edit distances calculated by the exact search algorithm).
Keywords: minimal graph edit distance, process mining, BPMN (Business Process Model and Notation), genetic algorithm. 
@article{MAIS_2018_25_6_a7,
     author = {A. A. Kalenkova and D. A. Kolesnikov},
     title = {Application of genetic algorithms for finding edit distance between process models},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {711--725},
     publisher = {mathdoc},
     volume = {25},
     number = {6},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2018_25_6_a7/}
}
TY  - JOUR
AU  - A. A. Kalenkova
AU  - D. A. Kolesnikov
TI  - Application of genetic algorithms for finding edit distance between process models
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2018
SP  - 711
EP  - 725
VL  - 25
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2018_25_6_a7/
LA  - ru
ID  - MAIS_2018_25_6_a7
ER  - 
%0 Journal Article
%A A. A. Kalenkova
%A D. A. Kolesnikov
%T Application of genetic algorithms for finding edit distance between process models
%J Modelirovanie i analiz informacionnyh sistem
%D 2018
%P 711-725
%V 25
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2018_25_6_a7/
%G ru
%F MAIS_2018_25_6_a7
A. A. Kalenkova; D. A. Kolesnikov. Application of genetic algorithms for finding edit distance between process models. Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 6, pp. 711-725. http://geodesic.mathdoc.fr/item/MAIS_2018_25_6_a7/

[1] Van der Aalst W. M. P., Process Mining — Data Science in Action, Second Edition, Springer, 2016

[2] Van der Aalst W. M. P., Weijters T., Maruster L., “Workflow Mining: Discovering Process Models from Event Logs”, IEEE Transactions on Knowledge and Data Engineering, 16:9 (2004), 1128–1142 | DOI

[3] Leemans S. J. J., Fahland D., van der Aalst W. M. P., “Discovering Block-Structured Process Models from Incomplete Event Logs”, Application and Theory of Petri Nets and Concurrency, Lecture Notes in Computer Science, 8489, Springer, 2014, 91–110 | DOI | MR | Zbl

[4] Kalenkova A. A., Ageev A. A., Lomazova I. A., van der Aalst W. M. P., “E-Government Services: Comparing Real and Expected User Behavior”, Business Process Management Workshops, Springer International Publishing, 2018, 484–496 | DOI

[5] Garey M. R., Johnson D. S., Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman Co., 1990 | MR

[6] Ivanov S. Y., Kalenkova A. A., van der Aalst W. M. P., “BPMNDiffViz: A Tool for BPMN Models Comparison”, Proceedings of the BPM Demo Session 2015 Co-located with the 13th International Conference on Business Process Management, BPM 2015 (Innsbruck, Austria, September 2, 2015), CEUR-WS.org, 2015, 35–39

[7] Hart P. E, Nilsson N. J, Raphael B., “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, 4:2 (1968), 100–107, IEEE | DOI

[8] Business Process Model and Notation (BPMN), Object Management Group, formal/2013-12-09, 2013

[9] Cross A. D. J., Wilson R. C., Hancock E. R., “Inexact Graph Matching Using Genetic Search”, Pattern Recognition, 30:6 (1997), 953–970 | DOI

[10] Riesen K., Fischer A., Bunke H., “Improving Approximate Graph Edit Distance Using Genetic Algorithms”, Structural, Syntactic, and Statistical Pattern Recognition, Springer, Berlin–Heidelberg, 2014, 63–72

[11] Kalenkova A. A., van der Aalst W. M. P., Lomazova I. A., Rubin V. A., “Process Mining Using BPMN: Relating Event Logs and Process Models”, Software Systems Modeling, 16:4 (2017), 1019–1048 | DOI

[12] Levenshtein V. I., “Binary Codes Capable of Correcting Deletions, Insertions and Reversals”, Soviet Physics Doklady, 10 (1966), 707 | MR

[13] Gladkov L. A., Kureichik V. V., Kureichik V. M., Genetic Algorithms, Fizmatlit, M., 2010, 368 pp. (in Russian)