Implementacija algoritma za paralelno strukturalno grupiranje grafova

diplomski rad

• Naslov (engleski): Implementation of parallel structural graph clustering algorithm
• Autor: Ana Mikić
• Mentor: Boris Vrdoljak (mentor)
• Član povjerenstva: Boris Vrdoljak (predsjednik povjerenstva)
• Član povjerenstva: Dalibor Krleža (član povjerenstva)
• Član povjerenstva: Mirta Baranović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-07-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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#.

Sažetak (engleski)

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.

• Ključne riječi: 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
• Ključne riječi (engleski): gSpan; depth first search; DFS code; lexicographic order; simmilarity threshold; common subgraph; MPI; process; structural graph clustering; parallel structural graph clustering; cluster
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:304242
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 13:08:58