Application of Genetic Algorithms for Finding Edit Distance between Process Models
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 ex...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2018-12-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/768 |
| _version_ | 1797877996087934976 |
|---|---|
| author | Anna A. Kalenkova Danil A. Kolesnikov |
| author_facet | Anna A. Kalenkova Danil A. Kolesnikov |
| author_sort | Anna A. Kalenkova |
| collection | DOAJ |
| description | 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). |
| first_indexed | 2024-04-10T02:25:45Z |
| format | Article |
| id | doaj.art-24428ee6740348958195e37c7ca25ffe |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:25:45Z |
| publishDate | 2018-12-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-24428ee6740348958195e37c7ca25ffe2023-03-13T08:07:29ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172018-12-0125671172510.18255/1818-1015-2018-6-711-725536Application of Genetic Algorithms for Finding Edit Distance between Process ModelsAnna A. Kalenkova0Danil A. Kolesnikov1Национальный исследовательский университет «Высшая школа экономики»Национальный исследовательский университет «Высшая школа экономики»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).https://www.mais-journal.ru/jour/article/view/768минимальное редакционное расстояние между графамиизвлечение и анализ процессовbpmn (business process model and notation)генетический алгоритм |
| spellingShingle | Anna A. Kalenkova Danil A. Kolesnikov Application of Genetic Algorithms for Finding Edit Distance between Process Models Моделирование и анализ информационных систем минимальное редакционное расстояние между графами извлечение и анализ процессов bpmn (business process model and notation) генетический алгоритм |
| title | Application of Genetic Algorithms for Finding Edit Distance between Process Models |
| title_full | Application of Genetic Algorithms for Finding Edit Distance between Process Models |
| title_fullStr | Application of Genetic Algorithms for Finding Edit Distance between Process Models |
| title_full_unstemmed | Application of Genetic Algorithms for Finding Edit Distance between Process Models |
| title_short | Application of Genetic Algorithms for Finding Edit Distance between Process Models |
| title_sort | application of genetic algorithms for finding edit distance between process models |
| topic | минимальное редакционное расстояние между графами извлечение и анализ процессов bpmn (business process model and notation) генетический алгоритм |
| url | https://www.mais-journal.ru/jour/article/view/768 |
| work_keys_str_mv | AT annaakalenkova applicationofgeneticalgorithmsforfindingeditdistancebetweenprocessmodels AT danilakolesnikov applicationofgeneticalgorithmsforfindingeditdistancebetweenprocessmodels |