Parallel and Distributed Motif Discovery in Temporal Networks - A feasibility study applying thread parallelism and community structure
Ladda ner
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Program
Computer science – algorithms, languages and logic (MPALG), MSc
Publicerad
2024
Författare
Marton, Stefan
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
temporal network , motif , temporal motif , parallel computing , distributed computing