Synthesis of Acyclic Models for Processes Without Repeating Events

Proceedings of the Institute for System Programming of the RAS. 2026. Vol. 38. No. 4(2) . P. 215–224.

Joulitov A.K., Lomazova I.A.

В майнинге процессов (process mining) графы непосредственного следования (Directly-Follows Graph, DFG) популярны благодаря своей простоте и наглядности. Однако, если процесс является ациклическим, но содержит параллельные события, стандартные алгоритмы построения DFG-моделей могут генерировать «ложные» циклы, которыe не представлены в журнале событий. Такие циклы мешают анализу информационных процессов, значительно снижая интерпретируемость и точность (precision) модели. Эта проблема рассматривалась в работе Н. Шаимова и др., где было предложено синтезировать DFG-модели без ложных циклов с помощью дублирования вершин графа. Задача эта не имеет единственного или лучшего решения, и предложенное ранее решение является эвристическим. Цель данной статьи – предложить альтернативный алгоритм синтеза ациклических DFG-моделей для процессов без повторяющихся событий и сравнить его с существующим на реальных и искусственных данных. Представленный в этой статье метод позволяет получить модель меньшего размера по сравнению с существующим решением, а также стабильно ведёт себя при построении моделей процессов с высокой степенью параллелизма. Также в работе доказано, что устранение ложных циклов ведет к экспоненциальному увеличению размера моделей для процессов с высокой степенью параллелизма.

Ключевые слова: майнинг процессов, графы непосредственного следования, process mining, automatic model synthesis, directly follows graphs, acyclic models, автоматический синтез моделей, ациклические модели

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Новые методы в исследовании формальных моделей вычислений, компьютерных систем и смежных задач теоретической информатики (2025)