Temporal Graph Motif Counting: A Comparative Experimental Analysis

Temporal networks are a specific type of graphs where each edge is provided with a timestamp, capturing the dynamic nature of interactions over time. These graphs are widely used to model complex systems like communication networks, social interactions, and more. Counting small recurring patterns, known as motifs, in temporal networks is a challenging topic in scientific research. The objective of this work is to create an efficient benchmarking workflow that enables a fair comparison of motif counting algorithms for temporal graphs. Specifically, some of the state-of-the-art algorithms will be evaluated using different temporal networks from a variety of domains. The primary goal of this thesis is to develop the tools and methodologies needed to establish a robust test environment, refining the initial research question as practical challenges are addressed. This process involves designing the experiments and implementing the necessary frameworks to conduct comprehensive tests. The results will identify the most effective algorithm for specific types of temporal networks and highlight the strengths and weaknesses of each tested algorithm. The evaluation of the algorithms will be based on their execution time and memory usage. The tests will be performed on motifs of various sizes and with diverse topological structures. Furthermore, for algorithms that support a parallel implementation, we will assess their scalability and performance improvements when executed in parallel environments.