A survey of graph-based algorithms for discovering business processes

(1) * Riyanarto Sarno Mail (Institut Teknologi Sepuluh Nopember, Indonesia)
(2) Kelly Rossa Sungkono Mail (Institut Teknologi Sepuluh Nopember, Indonesia)
*corresponding author


Algorithms of process discovery help analysts to understand business processes and problems in a system by creating a process model based on a log of the system. There are existing algorithms of process discovery, namely graph-based. Of all algorithms, there are algorithms that process graph-database to depict a process model. Those algorithms claimed that those have less time complexity because of the graph-database ability to store relationships. This research analyses graph-based algorithms by measuring the time complexity and performance metrics and comparing them with a widely used algorithm, i.e. Alpha Miner and its expansion. Other than that, this research also gives outline explanations about graph-based algorithms and their focus issues. Based on the evaluations, the graph-based algorithm has high performance and less time complexity than Alpha Miner algorithm.


Survey; Graph database; Process discovery; Quality




Article metrics

Abstract views : 1709 | PDF views : 258




Full Text



[1] R. Sarno and K. R. Sungkono, “Coupled Hidden Markov Model for Process Discovery of Non-Free Choice and Invisible Prime Tasks,” Procedia Comput. Sci., vol. 124, pp. 134–141, 2018, doi: 10.1016/j.procs.2017.12.139.

[2] R. Sarno and K. R. Sungkono, “Coupled Hidden Markov Model for Process Mining of Invisible Prime Tasks,” Int. Rev. Comput. Softw., vol. 11, no. 6, pp. 539–547, 2016, doi: 10.15866/irecos.v11i6.9555.

[3] R. Sarno and K. R. Sungkono, “Hidden Markov Model for Process Mining of Parallel Business Processes,” Int. Rev. Comput. Softw., vol. 11, no. 4, pp. 290–300, 2016, doi: 10.15866/irecos.v11i4.8700.

[4] K. R. Sungkono and R. Sarno, “Constructing Control-Flow Patterns Containing Invisible Task and Non-Free Choice Based on Declarative Model,” Int. J. Innov. Comput. Inf. Control, vol. 14, no. 4, 2018, available at: 10.24507/ijicic.14.04.1285.

[5] S. K. L. M. vanden Broucke and J. De Weerdt, “Fodina: A robust and flexible heuristic process discovery technique,” Decis. Support Syst., vol. 100, pp. 109–118, 2017, doi: 10.1016/j.dss.2017.04.005.

[6] R. Conforti, M. Dumas, L. García-Bañuelos, and M. La Rosa, “BPMN Miner: Automated discovery of BPMN process models with hierarchical structure,” Inf. Syst., vol. 56, pp. 284–303, 2016, doi: 10.1016/j.is.2015.07.004.

[7] F. M. Maggi, C. Di Ciccio, C. Di Francescomarino, and T. Kala, “Parallel algorithms for the automated discovery of declarative process models,” Inf. Syst., vol. 74, pp. 136–152, 2018, doi: 10.1016/j.is.2017.12.002.

[8] D. Chapela-Campa, M. Mucientes, and M. Lama, “Mining Frequent Patterns in Process Models,” Inf. Sci., vol. 472, pp. 235-257, 2019, doi: 10.1016/j.ins.2018.09.011.

[9] K. R. Sungkono and R. Sarno, “Patterns of fraud detection using coupled Hidden Markov Model,” in 2017 3rd International Conference on Science in Information Technology (ICSITech), 2017, pp. 235–240, doi: 10.1109/ICSITech.2017.8257117.

[10] R. Sarno, R. D. Dewandono, T. Ahmad, M. F. Naufal, and F. Sinaga, “Hybrid Association Rule Learning and Process mining for Fraud Detection,” IAENG Int. J. Comput. Sci., vol. 42, no. 2, pp. 59–72, 2015, available at: Google Scholar.

[11] S. Huda, R. Sarno, T. Ahmad, and H. A. Santoso, “Identification of Process-based Fraud Patterns in Credit Application,” in 2014 2nd International Conference on Information and Communication Technology (ICoICT), 2014, pp. 84–89, doi: 10.1109/ICoICT.2014.6914045.

[12] A. S. Osses, L. Q. Da Silva, B. F. Cobo, and M. Arias, “Business process analysis in advertising: An extension to a methodology based on process mining projects,” in Computer Science Society (SCCC), 2016 35th International Conference of the Chilean, 2016, pp. 1–12, doi: 10.1109/sccc.2016.7836000.

[13] Z. He, Y. Du, L. U. Wang, L. Qi, and H. Sun, “An Alpha-FL Algorithm for Discovering Free Loop Structures From Incomplete Event Logs,” IEEE Access, vol. 6, pp. 27895–27901, 2018, doi: 10.1109/ACCESS.2018.2840818.

[14] S. Akshay, L. Helouet, and R. Phawade, “Combining Free Choice and Time in Petri Nets,” in Proceedings of the International Workshop on Temporal Representation and Reasoning, 2016, vol. 2016–Decem, pp. 120–129, doi: 10.1109/TIME.2016.20.

[15] L. Wen, W. M. P. van der Aalst, J. Wang, and J. Sun, “Mining process models with non-free-choice constructs,” Data Min. Knowl. Discov., vol. 15, no. 2, pp. 145–180, 2007, doi: 10.1007/s10618-007-0065-y.

[16] Q. Guo, L. Wen, J. Wang, Z. Yan, and P. S. Yu, “Mining Invisible Tasks in Non-free-choice Constructs,” 2015, pp. 109–125, doi: 10.1007/978-3-319-23063-4_7.

[17] A. P. Kurniati, G. Kusuma, and G. Wisudiawan, “Implementing Heuristic Miner for Different Types of Event Logs,” vol. 11, no. 8, pp. 5523–5529, 2016, available at: Google Scholar.

[18] R. Sarno, W. A. Wibowo, Kartini, Y. A. Effendi, and K. R. Sungkono, “Determining Model Using Non-Linear Heuristics Miner and Control-Flow Pattern,” TELKOMNIKA (Telecommunication, Comput. Electron. Control., vol. 14, no. 1, pp. 349–360, 2016, doi: 10.12928/telkomnika.v14i1.3257.

[19] Z. Yan et al., “Decomposed and parallel process discovery: A framework and application,” Futur. Gener. Comput. Syst., vol. 98, pp. 392–405, 2019, doi: 10.1016/j.future.2019.03.048.

[20] K. R. Sungkono and R. Sarno, “CHMM for discovering intentional process model from event logs by considering sequence of activities,” in 2017 4th International Conference on Electrical Engineering, Computer Science and Informatics (EECSI), 2017, pp. 1–6, doi: https://doi.org/10.1109/EECSI.2017.8239194.

[21] R. Sarno, K. R. Sungkono, and R. Septiarakhman, “Graph-Based Approach for Modeling and Matching Parallel Business Processes,” Int. Inf. Inst. (Tokyo). Inf., vol. 21, no. 5, pp. 1603--1614, 2018, available at: Google Scholar.

[22] R. Sarno, K. R. Sungkono, R. Johanes, and D. Sunaryono, “Graph-Based Algorithms for Discovering A Process Model Containing Invisible Tasks,” Intell. Networks Syst. Soc., vol. 12, no. 2, pp. 85–94, 2019, available at: Google Scholar.

[23] S. Velampalli and M. V Jonnalagedda, “Graph based knowledge discovery using MapReduce and SUBDUE algorithm,” Data Knowl. Eng., vol. 111, pp. 103–113, 2017, doi: 10.1016/j.datak.2017.08.001.

[24] Q. Zhang, X. Song, Y. Yang, H. Ma, and R. Shibasaki, “Visual graph mining for graph matching,” Comput. Vis. Image Underst., vol. 178, pp. 16–29, 2019, doi: 10.1016/j.cviu.2018.11.002.

[25] M. Iğde, Y. Kavurucu, and A. Mutlu, “Graph Representation of Relational Database for Concept Discovery,” Procedia - Soc. Behav. Sci., vol. 195, pp. 1981–1989, 2015, doi: 10.1016/j.sbspro.2015.06.212.

[26] P. Braun, A. Cuzzocrea, C. K. Leung, A. G. M. Pazdor, and K. Tran, “Knowledge Discovery from Social Graph Data,” Procedia Comput. Sci., vol. 96, pp. 682–691, 2016, doi: 10.1016/j.procs.2016.08.250.

[27] Z. Mohammadpoory, M. Nasrolahzadeh, N. Mahmoodian, and J. Haddadnia, “Automatic identification of diabetic retinopathy stages by using fundus images and visibility graph method,” Measurement, vol. 140, pp. 133–141, 2019, doi: 10.1016/j.measurement.2019.02.089.

[28] Z. Chen, B. Jiang, J. Tang, and B. Luo, “Image Set Representation and Classification with Attributed Covariate-Relation Graph Model and Graph Sparse Representation Classification,” Neurocomputing, vol. 226, pp. 262–268, 2017, doi: 10.1016/j.neucom.2016.12.004.

[29] R. Zhu, F. Dornaika, and Y. Ruichek, “Joint graph based embedding and feature weighting for image classification,” Pattern Recognit., vol. 93, pp. 458–469, 2019, doi: 10.1016/j.patcog.2019.05.004.

[30] H. Yuan, J. Li, L. L. Lai, and Y. Y. Tang, “Graph-based multiple rank regression for image classification,” Neurocomputing, vol. 315, pp. 394–404, 2018, doi: 10.1016/j.neucom.2018.07.032.

[31] Y. Shao, N. Sang, C. Gao, and L. Ma, “Spatial and class structure regularized sparse representation graph for semi-supervised hyperspectral image classification,” Pattern Recognit., vol. 81, pp. 81–94, 2018, doi: 10.1016/j.patcog.2018.03.027.

[32] J. C. A. M. Buijs, B. F. Van Dongen, and W. M. P. van Der Aalst, “On the role of fitness, precision, generalization and simplicity in process discovery,” in OTM Conferences (1), 2012, vol. 7565, no. 1, pp. 305–322, doi: 10.1007/978-3-642-33606-5_19.

[33] A. K. A. De Medeiros, B. F. Van Dongen, W. M. P. van der Aalst, and A. J. M. M. Weijters, “Process mining: Extending the α-algorithm to mine short loops,” Eindhoven Univ. Technol. Eindhoven, pp. 1–25, 2004, doi: 10.1016/j.is.2011.01.003.

[34] L. Wen, J. Wang, W. M. P. van der Aalst, B. Huang, and J. Sun, “Mining process models with prime invisible tasks,” Data Knowl. Eng., vol. 69, no. 10, pp. 999–1021, Oct. 2010, doi: 10.1016/j.datak.2010.06.001.

[35] W. M. P. Van Der Aalst and A. H. M. Hofstede, “YAWL : yet another workflow language,” vol. 30, pp. 245–275, 2005, doi: 10.1016/j.is.2004.02.002.

[36] E. Börger, “Approaches to modeling business processes : a critical analysis of BPMN , workflow patterns and YAWL,” pp. 305–318, 2012, doi: 10.1007/s10270-011-0214-z.

[37] R. Sarno, Y. A. Effendi, and F. Haryadita, “Modified Time-Based Heuristics Miner for Parallel Business Processes,” Int. Rev. Comput. Softw., vol. 11, no. 3, pp. 249–260, 2016, doi: 10.15866/irecos.v11i3.8717.

[38] R. Sarno, Kartini, W. A. Wibowo, and A. Solichah, “Time based Discovery of parallel business processes,” Proceeding - 2015 Int. Conf. Comput. Control. Informatics Its Appl. Emerg. Trends Era Internet Things, IC3INA 2015, pp. 28–33, 2016, doi: 10.1109/IC3INA.2015.7377741.

[39] W. M. P. van der Aalst, T. Weijters, and L. Maruster, “Workflow mining: discovering process models from event logs,” IEEE Trans. Knowl. Data Eng., vol. 16, no. 9, pp. 1128–1142, Sep. 2004, doi: 10.1109/TKDE.2004.47.

[40] A. Rozinat, R. S. Mans, M. Song, and W. M. P. van der Aalst, “Discovering colored Petri nets from event logs,” Int. J. Softw. Tools Technol. Transf., vol. 10, no. 1, 2008, doi: 10.1007/s10009-007-0051-0.

[41] R. Sarno, B. A. Sanjoyo, I. Mukhlash, and H. M. Astuti, “Petri Net model of ERP business process variation for small and medium enterprises,” J. Theor. Appl. Inf. Technol., vol. 54, no. 1, pp. 31–38, 2013, available at: Google Scholar.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

International Journal of Advances in Intelligent Informatics
ISSN 2442-6571  (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: info@ijain.org (paper handling issues)
   andri.pranolo.id@ieee.org (publication issues)

View IJAIN Stats

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0