Huba
18 °C
34 °C

Hatlépésnyi távolságok

2005.10.09. 12:40
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.
A 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.

#alt#

A két aspektust az eddigi kutatások során külön-külön kezelték, együttes, egyazon - valószínűségelméleti alapokon nyugvó - algoritmusban történő alkalmazásuk Jensen és Simsek érdeme. Úgy tűnik, hatékony a kombináció, mert "várható-érték navigáció"-nak (expected-value navigation) nevezett fejlesztésük a csomópontok közötti legrövidebb utakra a központi hálózat felépítésének ismerete nélkül is rátalál.

Telefonszámok

Hasonló kis világokban mozog, mint az agy előhomloki (prefrontális) kortex részén található, például a telefonszámok fejbentartásakor használt rövid távú memória működését biztosító idegsejt-hálózatok. Az Északnyugati Egyetemen (Evanson, Illinois) végzett kísérletek kimutatták, hogy a két stabil állapot között átkapcsoló, szomszédos neuronok egymást aktiválják, így a hálózat legtávolabbi részei között is létesíthető kapcsolat. A második aktiváló impulzus pedig kikapcsolja a rendszert.

Az elmélet sokak szerint a számítógép-hálózatok és a rövid távú memória mellett a világegyetem, a biológia, vagy a társadalmi és gazdasági élet egyéb kérdéseit is megválaszolja.