Hálózatok, útvonalak és entrópia
„– Mondja bátyám, mennyire van a legközelebbi falu? – Légvonalban 5 km, de tudok egy rövidebb utat az erdőn keresztül” – az ismert vicc akár a mottója is lehetne az MTA-BME Információs Rendszerek Modellezése kutatócsoport és a BME Villamosmérnöki és Informatikai Kar Távközlési és Médiainformatikai Tanszék munkatársai által végzett kutatásoknak. Eredményeikről a közelmúltban két rangos szakfolyóiratban számoltak be.
Rétvári Gábor és Gulyás András kutatócsoportjai az egyik tanulmányt a kommunikációs rendszerek és számítógép hálózatok egyik legrangosabb kiadványában, az IEEE/ACM Transactions on Networking folyóiratban közölték.
A szerzők a cikkben a nagyvolumenű számítógéphálózatok (large-scale computer networks) skálázhatósági kérdéseit tárgyalják a széles körben alkalmazott ún. csomópontonkénti útvonalirányítási paradigma (hop-by-hop routing) memóriaigényének szempontjából. A kutatók drámaian új megközelítése az, hogy az útvonalválasztó berendezések (router) továbbítási tábláit (forwarding tables) olyan karaktersorozatokká alakították át, amelyek az információelmélet eszközeivel vizsgálhatók. Kimutatták, hogy információelméleti entrópia alapú mértékek segítségével igazolható és a gyakorlatban jól megközelíthető becslések adhatók az útvonalválasztáshoz szükséges memória mennyiségére. A vizsgálatok elvezettek a memóriaigény szempontjából optimális címtér tervezéséhez, amelyre a szerzők általános hálózati topológiákra alkalmazható heurisztikát dolgoztak ki. Az eredmények fontos gyakorlati következménye, hogy a valóságban előforduló hálózati topológiák esetén az optimalizált címkiosztás segítségével a továbbítási táblák nagyságrendekkel kisebb méretre tömöríthetők úgy, hogy a bennük történő keresés hatékonysága érdemben nem változik.
A másik tanulmányban a szerzők interdiszciplináris vizekre eveztek, az emberi tájékozódást vizsgálták hálózattudományi eszközökkel. Az eredményeket a Nature Publishing Group-hoz tartozó Scientific Reports közölte. A publikáció eredeti angol címe: The role of detours in individual human navigation patterns of complex networks. A vizsgálatok alapjául egy korábban kifejlesztett mobil applikáció, a fit-fat-cat szolgált. Ez egy olyan angol nyelvű szójáték-alkalmazás, amelyben a felhasználó feladata, hogy egy hárombetűs szóból eljusson egy másikba úgy, hogy egy lépésben csak egyetlen betűt változtat meg és minden közbenső lépésben is létező szó keletkezzen. A játék mentén a hárombetűs szavak egy olyan hálózatot alkotnak (ld. illusztráció), amelyben a játékosok útvonalakat tanulnak meg és ezek alapján tájékozódnak. A kutatók a vizsgálatok alapján kimutatták, hogy a játékosok egyedi hierarchikus “vázat” alakítanak ki a tájékozódáshoz, és ezek köré rendeződnek azok az útvonalak, amelyeket a megoldáshoz használnak. Ezek az útvonalak általában “kerülőutak”, azaz hosszabbak, mint az elméletileg legrövidebb utak, és ez a tulajdonság a tanulási fázis után is megmarad. Azonban ezen kerülő utak rendszere a tájékozódást a komplex hálózatban nagymértékben leegyszerűsítheti a legrövidebb útvonalak rendszeréhez képest. Ezt alátámasztják a szerzők azon információelméleti számításai is, amelyekből kiderül, hogy egy csomópontban a következő lépés meghatározásához szükséges információ átlagos mennyisége egy nagyságrenddel kisebb kerülőutak használatával mintha a legrövidebb utakat használnánk.
A kutatási eredmények Rétvári Gábor és Gulyás András nemrég beadott MTA doktori pályázatának is részét képezik.
A hárombetűs angol szavak (1010 db) hálózata. Két szó össze van kötve, ha egy betű cseréjével el lehet jutni az egyikből a másikba.
