Hatlépésnyi távolságok

A Massachusetts Egyetem kutatói a hatlépésnyi távolságként elhíresült szociológiai elméletre magyarázattal szolgáló, a hálózati navigációban hatékony támogatást nyújtó algoritmust fejlesztettek. Algoritmusuk a Barabási Albert-László munkáiból ismert, a rövid távú emberi emlékezet működésében is fontos "kis világokba" kalauzol.

Az amhersti felsőoktatási intézmény két kutatója, David Jensen és Özgür Simsek által kidolgozott algoritmus különböző (ad hoc vezeték nélküli, p2p fájlmegosztó, WWW) hálózatokra, valamint a hatékonyabb üzenettovábbítás előnyeit kihasználó összes rendszerre alkalmazható. Szerteágazó feladatokat képes megoldani: figyelmeztet a vírusok elterjedésére, vészhelyzet esetén gördülékenyebbé teszi a gépek, a hálózat részei közötti kommunikációt. Legjobb teljesítményt a központ nélküli, struktúrájukat gyorsan változtató dinamikus rendszerekben nyújtja.

Az Omaha-Boston és a Wichita-Boston vonal

Jensen és Simsek munkáját Stanley Milgram hatvanas évek végén folytatott, az ismeretségi hálózatok szerkezetét elemző kutatásai inspirálták. A harvardi professzort az Egyesült Államokban tetszőlegesen kiválasztott két személy közötti távolság érdekelte: hány ismeretségi kapcsolaton keresztül lennének összeköthetők? Omahai (Nebraska) és wichitai (Kansas) lakosoknak azzal a kéréssel küldött levelet, hogy a kézbesített nyomtatványt speciális úton juttassák el a bostoni célszemélynek: amennyiben nem ismerik, ne közvetlenül neki, hanem olyan valakinek postázzák, aki valószínűbb, hogy kapcsolatban áll vele. A százhatvan levélből negyvenkettő érkezett meg; átlagosan öt és fél közvetítőre volt szükség.

Valamennyien össze vagyunk kapcsolva egymással, kis világban élünk - vonta le a következtetéseket Milgram. A kis világok jellemző vonása, hogy két tetszőleges pontjukat csak néhány lépés választja el egymástól.

Központ nélküli csomópontok

De miként vagyunk összekapcsolva, és a hálózatok mely tulajdonságai teszik hatékonnyá a navigációt? - tette fel a kérdést Jensen és Simsek. Lokálisak, decentralizáltak, azaz a sikeres keresést valamilyen szinten a helyi rendszer alapjait adó szerkezetnek is támogatnia kell. A Milgram-kísérletből kimutatták, hogy a hálózatokra is alkalmazható két emberi sajátosság (és kombinációjuk) komoly segítséget nyújt a kutakodásban: magunkhoz hasonló személyekkel szeretünk kapcsolatban állni, illetve egyesek inkább társas lények, mint mások. Figyelembe véve ezeket a tényezőket, egyrészt a kapcsolatok közösségeket teremtenek, másrészt a több ismeretséggel rendelkező személyek csomópont-szerepet töltenek be. Rajtuk keresztül érünk révbe. A hálózat-keresésben ez úgy érvényesül, hogy az algoritmus a célhoz vezető közvetlen kapcsolatok valószínűségét maximalizáló csomópontokat részesíti előnyben.

A cikk további része az Agent Portal oldalán olvasható.