Parallel and Distributed Motif Discovery in Temporal Networks - A feasibility study applying thread parallelism and community structure
| dc.contributor.author | Marton, Stefan | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för data och informationsteknik | sv |
| dc.contributor.department | Chalmers University of Technology / Department of Computer Science and Engineering | en |
| dc.contributor.examiner | Damaschke, Peter | |
| dc.contributor.supervisor | Hassan, Ahmed Ali-Eldin | |
| dc.date.accessioned | 2025-01-13T09:31:45Z | |
| dc.date.available | 2025-01-13T09:31:45Z | |
| dc.date.issued | 2024 | |
| dc.date.submitted | ||
| dc.description.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. | |
| dc.identifier.coursecode | DATX05 | |
| dc.identifier.uri | http://hdl.handle.net/20.500.12380/309076 | |
| dc.language.iso | eng | |
| dc.setspec.uppsok | Technology | |
| dc.subject | temporal network | |
| dc.subject | motif | |
| dc.subject | temporal motif | |
| dc.subject | parallel computing | |
| dc.subject | distributed computing | |
| dc.title | Parallel and Distributed Motif Discovery in Temporal Networks - A feasibility study applying thread parallelism and community structure | |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.degree | Master's Thesis | en |
| dc.type.uppsok | H | |
| local.programme | Computer science – algorithms, languages and logic (MPALG), MSc |