## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
The total running time for the novel construction method is then \(\mathcal{O}(1)+\mathcal{O}(n^{2})=\mathcal{O}(n^{2})\) time in the worst-case scenario. We can also obtain a lower bound for the complexity in the worst-case scenario by analyzing the possible size of the output. The complete directed bipartite graph with \(n\) vertices, usually indicated with \(K_{\frac{n}{2},\frac{n}{2}}\), is a DAG that has \((\frac{n}{4})^{2}=\mathcal{O}(n^{2})\) edges. It is easy to see that the complete bipartite graph fulfills the requirements to be a behavior graph: it is in fact acyclic, and no edge can be removed without changing the reachability of the graph--specifically, it is equivalent to its transitive reduction. We can show that a behavior graph with such a shape exists employing a simple construction: a trace composed by \(n\) events with timestamps such that the first \(\frac{n}{2}\) events all have overlapping timestamps, the last \(\frac{n}{2}\) also all have overlapping timestamps, and the maximum timestamp of each of the first \(\frac{n}{2}\) is smaller than the minimum timestamp of each of the last \(\frac{n}{2}\) events. The construction, together with an example, is illustrated in Figure 10. Since lines 11-30 of the algorithm build this graph with \(\mathcal{O}(n^{2})\) edges, the algorithm runs in \(\Omega(n^{2})\) time, and thus also in \(\Theta(n^{2})\) time. This also proves the asymptotic optimality of the algorithm: no algorithm to build behavior graphs can run in less than \(\Theta(n^{2})\) time in the worst-case scenario. ## 6 Experimental Results

The formal definition of our novel construction method for the behavior graph was used to show its asymptotic speedup with respect to the construction using the transitive reduction. To empirically confirm this improvement, we built a set of experiments to measure the gain in speed and memory usage. ### Performance of Behavior Graph Construction

In this section, we will show a comparison between the running time of the naive behavior graph construction--which employs the transitive reduction--versus the improved method detailed throughout the paper. The experiments are set to investigate the difference in performance between the two algorithms, and most importantly how this difference scales when the size of the event log increases, as well as the amount of events in the log that have uncertain timestamps. In designing the experiments, we took into consideration the following research questions:

* \(Q1\): how does the computation time of the two methods compare when run on logs with an increasing number of traces? * \(Q2\): how does the computation time of the two methods compare when run on logs with increasing trace lengths? * \(Q3\): how does the computation time of the two methods compare when run on logs with increasing percentages of events with uncertain timestamps? * \(Q4\): what degree of reduction in memory consumption for the representation of an uncertain log can we attain with the novel method? * \(Q5\): do the answers obtained for \(Q3\) hold when simulating uncertainty on real-life event data? Both the baseline algorithm based on transitive reduction [2] and the new algorithm for the construction of the behavior graph are implemented in Python, within the PROVED project. The implementation of both methods is available online, as well as the full code for the experiments presented here (see the reference in Section 1). For each series of experiments exploring \(Q1\) through \(Q4\), we generate a synthetic event log with a number \(n\) of traces of length \(l\) (in number of events belonging to the trace). Uncertainty on timestamps is then artificially added to the events in the log. A specific percentage \(p\) of the events in the event log will have an uncertain timestamp, causing it to overlap with an adjacent event. Figure 10: Construction of the class of behavior graphs isomorphic to a complete bipartite graph and an instantiated example.