Parallel and Distributed Motif Discovery in Temporal Networks - A feasibility study applying thread parallelism and community structure

Abstract

Temporal networks are used to model complex systems in topics such as epidemiology, finance, and computer networks. Motifs are subgraphs of a directed graph that are representative of the structure of that particular graph. Motifs have been extended to temporal networks. Motif discovery is a computationally hard problem; in fact sub-problems are NP-hard problems. In this thesis, we explore state-of-theart temporal network motif discovery algorithms, and how they can be parallelized on a multi-threaded system and distributed across multiple systems. We select Kovanen’s definition of temporal network motif. We implement a simple approach to thread parallelism to demonstrate the potential for parallelism of the algorithm, and find that the parallelizable proportion p > 0.89, which implies great potential for parallelism. We utilize community structure of the graph the temporal network represents to divide the network into work packages for distributed computation. In doing so, we encounter and report numerous challenges in distribution of the exact solution approach.