Multiplex gráfok mátrixalapú elemzése
A gráfok és gráfalgoritmusok az informatika legtö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. multiplex gráfok (más néven 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-iratok) származó gráfokon kiszámoltam őket.
szerző
-
Várhegyi Petra
Gazdaságinformatikus szak, mesterképzés
mesterképzés (MA/MSc)
