## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
For any \(n=2k\), it is possible to have a behavior graph isomorphic to the graph \(K_{k,k}\), which thus has a number of edges quadratic in the number of vertices. Finally, behavior graphs are built from all the traces in the event log with either algorithm, while the execution time is measured. All results in this section are presented as the mean of the measurements for 10 runs of the corresponding experiment. In the diagrams, we will label with \"TrRed\" the naive method using the transitive reduction, and with \"Improved\" the faster algorithm illustrated in this paper. Additionally, the data series for the novel method are labeled with the relative variation in running time for each specific data point in the experiment, expressed in percentage. To answer \(Q1\), the first experiment inspects how the efficiency of the two algorithms scales with log dimension in number of traces. We generate logs with a fixed uncertainty percentage of \(p=0.5\), and trace length of \(l=20\). The number of traces in the uncertain log progressively scales from \(n=1000\) to \(n=10{,}000\). As shown in Figure 11, our proposed algorithm outperforms the baseline algorithm, showing a much smaller slope in computation time. As anticipated by the theoretical analysis, the computing time to build behavior graphs increases linearly with the number of traces in the event log for both methods; in the novel method, the constant factors are much smaller, thus producing the speedup that we can observe in the graph. Please note that in this experiment the novel method requires between 18% and 26% of the time with respect to the baseline method. The second experiment is designed to answer \(Q2\). We analyze the effect of the trace length on the total time needed for behavior graph creation. Therefore, we created logs with \(n=100\) traces of increasing lengths in number of events, and added uncertain timestamps to events with \(p=0.5\). The results, illustrated in Figure 12, meet our expectations: the computation time of the baseline method scales much worse than the computation time required by our new technique, due to its cubic asymptotic time complexity. This confirms the results of the analysis of the asymptotic time complexity analysis detailed in Section 5. We can notice an order-of-magnitude increase in speed. At trace length \(l=600\), the new algorithm computes the graphs in only 0.35% of the time required by the baseline algorithm. Table 4.0 Time in seconds for the creation of the behavior graphs for synthetic logs with traces of length \(l=20\) events and \(p=0.5\) of uncertain events, with increasing number of traces \(n\). The solid blue line indicates the time needed for the naive construction; the dashed red line shows the building time of the improved algorithm, and is labeled with the relative time variation (in percentage). The next experiment tackles \(Q3\), by inspecting the difference in execution time for the two algorithms in function of the percentage of events with an uncertain timestamp in the event log. Keeping constant the values \(n=100\) and \(l=100\), we progressively increased the percentage \(p\) of events with an uncertain timestamp and measured computation time. As presented in Figure 13, the time required for behavior graph construction remains almost constant for our proposed algorithm, while it is very slightly decreasing for the baseline algorithm. This behavior is expected, and is justified by the fact that the worst-case scenario for the baseline algorithm is a trace that has no uncertainty on the timestamp: in that case, the behavior graph is simply a chain of nodes representing the total order in a sequence of events with certain timestamps, thus the transitive reduction needs to find and remove a higher number of edges from the directed graph. This worst-case scenario occurs at \(p=0\), explaining why the computation time needed by the transitive reduction is at its highest.