Implementacija algoritma za paralelno strukturalno grupiranje grafova

master's thesis

• Title (english): Implementation of parallel structural graph clustering algorithm
• Author: Ana Mikić
• Mentor: Boris Vrdoljak (mentor)
• Committee member: Boris Vrdoljak (predsjednik povjerenstva)
• Committee member: Dalibor Krleža (član povjerenstva)
• Committee member: Mirta Baranović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Identifikacija grupa u skupu podataka u posljednje vrijeme sve više pronalazi svoju primjenu u raznim područjima. Omogućuje bolje shvaćanje podataka i veza među njima. Razvijen je niz algoritama za grupiranje podataka, a u radu je opisan i implementiran algoritam za paralelno strukturalno grupiranje grafova. Primjenjuje se nad velikim skupom ulaznih podataka, pri čemu je svaki podatak predstavljen pomoću grafa. Graf je skup čvorova povezanih bridovima te se koristi za prikaz objekata i odnosa među njima. Na početku rada je objašnjen pojam grupiranja, odnosno grupiranja grafova te su navedeni primjeri njihovog korištenja. Osim algoritama za strukturalno i paralelno strukturalno grupiranje grafova, opisan je i implementiran i algoritam za otkrivanje zajedničkih podgrafova niza grafova. Također su naglašene razlike između strukturalnog i paralelnog strukturalnog grupiranja grafova. Implementirani algoritmi su pokrenuti nad skupom koji sadrži 907 grafova, nakon čega je napravljena analiza dobivenih rezultata. Za uspješnu implementaciju paralelnog programa nužno je bilo upoznavanje s MPI standardom te konkretnom MPI implementacijom u programskom jeziku C#.

Abstract (english)

Identification of groups in a data set lately increasingly finds its application in various fields. It provides a better understanding of the data and the connections between them. A number of algorithms for grouping data have been developed, and an algorithm for parallel structural graph clustering has been described and implemented in this thesis. It is applied over a large input data set, with each piece of data represented by a graph. A graph is a set of nodes connected by edges and is used to represent objects and the relationships between them. At the beginning of the thesis, the concept of clustering, i.e., graph clustering is explained, and examples of their use are given. Besides the algorithms for structural and parallel structural graph clustering, graph-based substructure pattern mining has also been described and implemented. The differences between structural and parallel structural graph clustering have also been emphasized. The implemented algorithms were run over a set containing 907 graphs, after which an analysis of the obtained results was performed. For a successful implementation of the parallel program, it was necessary to get acquainted with the MPI standard and the particular MPI implementation in the C # programming language.

• Keywords: gSpan; pretraživanje u dubinu; DFS kod; leksikografski poredak; koeficijent sličnosti; zajednički podgraf; MPI; proces; strukturalno grupiranje grafova; paralelno strukturalno grupiranje grafova; grupa
• Keywords (english): gSpan; depth first search; DFS code; lexicographic order; simmilarity threshold; common subgraph; MPI; process; structural graph clustering; parallel structural graph clustering; cluster
• Language: croatian
• URN:NBN: urn:nbn:hr:168:304242
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 13:08:58