Többdimenziós gráfok elemzése

OData támogatás
Konzulens:
Marton József Ernő
Távközlési és Médiainformatikai Tanszék

A gráfok és gráfalgoritmusok az informatika több területén is használatosak. Gráfalgoritmusokat alkalmaznak például a routerek hálózati forgalomirányításhoz, az operációs rendszerek folyamatok ütemezéséhez, és a logisztikában is jelentős szerepük van. Ezen túl gráfalgoritmusok segítségével számos olyan probléma megoldható, amely a tudomány több területén (pl. biológia, társadalomtudományok) is felmerülnek.

Viszonylag újabb kutatási terület a hálózatkutatás, amely a gráfok topológiai sajátosságaival foglalkozik. Gráfok jellemzésére számos metrika létezik, amelyek segítségével jobban megérthetjük a gráfreprezentáció alapjául szolgáló rendszereket is. Hagyományosan a hálózatkutatás homogén, típus nélküli gráfokkal foglalkozik, nem különbözteti meg egyes csomópontok és élek típusát. Kevésbé kutatott terület az ún. többdimenzós gráfok (más néven multiplex vagy heterogén hálózatok) vizsgálata. Ezek többféle típusú élt különböztetnek meg lehetőséget adva komplexebb szemantikai kapcsolatrendszerek modellezésére és a gráfok mélyebb elemzésére.

A metrikák egy csoportja a gráf klaszterezettségét írja le, amelyhez háromszögek keresésére van szükség. Ez típus nélküli gráfok esetén is számításigényes művelet, amely nem skálázódik jól, típusok bevezetése pedig még komplexebbé teszi a számításokat. Ennek egy lehetséges megoldása az lehet, ha a gráfok szomszédossági mátrixát használjuk és ezeken definiáljuk a metrikákat.

Dolgozatomban célom, hogy a szomszédossági mátrixokat felhasználva hatékonyabbá tegyem néhány számításigényes multiplex metrika számítását. Ehhez implementáltam őket a gráfok szomszédossági mátrixán mátrixműveleteket végezve, majd oknyomozói újságírók által közzétett adathalmazokból (pl. Panama- és Paradise-iratok) származó gráfokon kiszámíttattam őket. A klaszterezettséget leíró metrikák számításában karakterisztikus teljesítményjavulást értem el a naiv megközelítéshez képest. Egy kb. 450 000 csúcsú gráfon az egyik ilyen metrika számítása kb. 15-ször gyorsabb lett a lineáris algebrai megközelítéssel.

Letölthető fájlok

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