Nagy gráfokon zajló folyamatok modellezése és szimulációja.

OData támogatás
Konzulens:
Dr. Katona Gyula
Számítástudományi és Információelméleti Tanszék

Az alkalmazásokban előforduló nagy méretű, "valós" hálózatokat reprezentáló gráfok több speciális tulajdonsággal is rendelkeznek, amelyeket az egyszerű véletlen gráfok nem elégítenek ki. (Ilyen például a kisvilág-tulajdonság vagy a skálafüggetlenség.) Ezek miatt a tulajdonságok miatt ilyen jellegű véletlen gráfok generálásához speciális módszerekre van szükség, mint például a dolgozatban részletesen ismertetett Barabási-Albert modell.

A valós hipergráfok generálásának témaköre kevésbé kutatott terület, mint a valós gráfoké. A dolgozatban kétféle megközelítést mutatok be: az egyik egy gráf közösségeinek megkeresésén alapszik, a másik közvetlenül generálja a hipergráfot. A közösségek megkeresésére többfajta módszert használtam: maximális klikkek listázása (Bron-Kerbosch algoritmus), k-klikk perkoláció (Palla), szigorú klikk feltételen alapuló iteratív k-klikk perkoláció (Zahoránszky), normált klikk perkoláció (Zubcsek). A különböző módon generált hipergráfok fokszám- és élméret eloszlását megvizsgáltam és értékeltem.

A dolgozatban bemutatok egy egyszerű, gráf alapú járványterjedési modellt és annak hipergráfokra történő általánosítását, valamint a modellek implementációját. A különböző módszerekkel generált gráfok és hipergráfok esetén megvizsgáltam és értékeltem a szimuláció eredményeit.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.