اندازه گیری مشابهت شبکه جریان کاری مبتنی بر روابط همجواری گذاری

Many activities in business process management, such as process retrieval, process mining, and process integration, need to determine the similarity or the distance between two processes. Although several approaches have recently been proposed to measure the similarity between business processes, neither the definitions of the similarity notion between processes nor the measure methods have gained wide recognition. In this paper, we define the similarity and the distance based on firing sequences in the context of workflow nets (WF-nets) as the unified reference concepts. However, to many WF-nets, either the number of full firing sequences or the length of a single firing sequence is infinite. Since transition adjacency relations (TARs) can be seen as the genes of the firing sequences which describe transition orders appearing in all possible firing sequences, we propose a practical similarity definition based on the TAR sets of two processes. It is formally shown that the corresponding distance measure between processes is a metric. An algorithm using model reduction techniques for the efficient computation of the measure is also presented. Experimental results involving comparison of different measures on artificial processes and evaluations on clustering real-life processes validate our approach.

Nowadays, process-aware information systems, such as WFM (Workflow Management system), SCM (Supply Chain Management), PDM (Product Data Management system) and ERP (Enterprise Resource Planning) have been widely adopted in industry to offer generic modeling and enactment capabilities for structured business processes [12]. Business processes accumulated in various information systems have become important intellectual assets which represent the real-life business handling procedures of the organizations. A deep insight into these business processes and their mutual relationship is necessary to business management activities. There are many applications in business process management that require measuring the similarity between business processes, such as process retrieval, process mining, and process integration. For example, the task items of a workflow process in Teamcenter PDM [25] is established before the control-flow structure. Therefore, different workflow designers may construct different processes with the same set of task items. We need to determine whether the behaviors of these models are equivalent or not, and how different their behaviors are in case of inequivalence. Another example is China CNR Corporation Limited [10] which is a newly regrouped company which has more than 20 subsidiary companies. Before the corporation was established, most of these subsidiary companies independently deployed ERP systems with a total of more than 200,000 process models. Now, CNR needs to integrate these ERP systems. How to group or cluster these processes is a big problem. Measuring the similarity between process models automatically will be helpful in tackling these challenges. Researchers working on formal methods have proposed a variety of equivalence notions to compare the behaviors between processes, such as trace equivalence, bisimulation, and branching bisimulation [21], [15] and [19]. However, these equivalence notions can only tell a binary answer, i.e., equivalence or inequivalence. If we measure the similarity between processes based on equivalence notions, e.g., mapping equivalence to 1 and inequivalence to 0, such a measure is not very useful because it cannot distinguish between complete difference and slight difference of process behaviors. As to Fig. 1, we investigate process behaviors in the context of trace semantics. The firing sequences of Processes N1N1, N2N2, and N3N3 are {ABD,ACD}{ABD,ACD}, {ABCD,ACBD}{ABCD,ACBD}, and {ABCD,ACBD}{ABCD,ACBD}, respectively. The firing sequences of Process N4N4 cannot be enumerated one by one (i.e., infinite) because there is a loop structure in Process N4N4. Intuitively, these models are similar in some sense. However, with the trace equivalence notion, we cannot tell the degree of similarity between them except that Processes N2N2 and N3N3 are equivalent.Recent literature has proposed different approaches to quantifying the similarity between business processes [2], [18] and [11]. Although firing sequences are a good representation of the behavior of a process, they are neither possible (e.g., with loop structures) nor practical due to the high complexity of exploring state space of concurrent models [14]. Therefore, the proposed approaches for measuring similarity are all based on substitute representations, such as on causal footprints [11] or observed behavior [18] in the context of different definitions of the similarity notion. However, the results of these similarity measures cannot be compared with each other because they lack a unified definition of the similarity between processes. In this paper, we define the similarity and the distance between two business processes on full firing sequences of the processes as the unified reference concepts. However, the full firing sequences of a process are not always available. For example, to a WF-net with loop structures, either the number of full firing sequences or the length of a single firing sequence is infinite. Considering that transition adjacency relations (TARs) can be seen as the genes of the firing sequences because the TAR set can specify the exact behavior of a large category of processes (e.g., SWF-nets) [6], we define a computable similarity based on the TAR set. The TAR set describes transition orders that appear in all possible firing sequences (one directly follows the other). For example, the TAR sets of Processes N1N1, N2N2, N3N3 and N4N4 are {AB,AC,BD,CD}{AB,AC,BD,CD}, {AB,AC,BC,CB,BD,CD}{AB,AC,BC,CB,BD,CD}, {AB,AC,BC,CB,BD,CD}{AB,AC,BC,CB,BD,CD} and {AB,AC,BC,CB,BB,CC,BD,CD}{AB,AC,BC,CB,BB,CC,BD,CD}, respectively, as shown in Fig. 2. We can see that the TAR set of Process N4N4 is finite despite of its infinite firing sequences. The TAR set has three features. Firstly, the TAR set represents the essence of the firing sequences of a process. Secondly, for any processes with a finite number of tasks, the cardinality of the TAR set is finite. Thirdly, the TAR set of a WF-net can be generated in less time than that of a full firing sequence generation. At the same time, the corresponding distance measure between business processes is also defined. The distance measure is proved to be a metric which can be used in a wide range of applications.This paper makes three contributions: firstly, it presents a definition of the similarity (and the distance) between processes based on firing sequences as a unified reference concept; secondly, it proposes a similarity measure (and distance measure) based on transition adjacency relation set; thirdly, both distance measures are proved to be metrics. The remainder of this paper is organized as follows. Section 2 introduces some basic concepts used throughout the paper. Section 3 describes the details of our approach to measuring similarity between business processes. Section 4 proposes an algorithm intended to decrease the time required for the TAR set generation. Section 5 shows the experimental results. Section 6 discusses the related work, and Section 7 concludes the paper and outlines future work.

In the present paper, we propose a new similarity measure between business processes based on the transition adjacency relation set (TAR). We also define a reference similarity based on firing sequences of two processes to serve as a unified concept so that different similarity measures can be compared with each other. An advantage of the new similarity is that it is consistent with the reference similarity, but less rigid and lower in computation cost. The corresponding distance measure is proved to be a metric so that it can be used in a wide range of applications. Similarity measure between business processes benefits a lot of applications, such as process model retrieval, process mining, and process integration in modern enterprises. Although the approach is based on WF-nets, it can be applied to any process modeling language with executable semantics, e.g., by transforming to WF-nets. Our future work will address other open problems on similarity measure between real-life processes, e.g., processes with different label alphabets, and process model clustering based on the distance metric, etc.