Magyar Tudomány, 2006/11 1298. o.

Hálózatok



A hálózatok tudománya:

a társadalomtól a webig


Barabási Albert-László

az MTA külső tagja

University of Notre Dame, Indiana, USA

alb @ nd.edu


Amióta a National Science Foundation 1995-ben feladta az internet feletti gyámságot, úgy tűnik, a hálózat önálló életre kelt. Kis és nagy társaságok ezrei adnak hozzá állandóan router-eket és vonalakat, amelyek közül egyik sem köteles jelentést tenni a tevékenységéről. Ez a kontrollálatlan és decentralizált növekedés kutatókká változtatta a tervezőket. Valóban, miközben az utóbbi időkig minden internettel kapcsolatos kutatás jobb kommunikációs protokollok tervezésére koncentrált, a tudósok újabban egyre gyakrabban tesznek fel egy váratlan kérdést: Pontosan mit is alkottunk? Egy dolog világos: noha teljesen emberi tervezésű, mégis úgy tűnik, a web több közös vonást mutat egy sejttel vagy egy ökológiai rendszerrel, mint egy aprólékos gonddal megtervezett svájci órával. Számos különböző komponens - melyek mindegyike egy specializált feladatot hajt végre - járul hozzá egy hihetetlen sebességgel kibontakozó és változó rendszerhez. Mi pedig egyre inkább ráébredünk, hogy az internet és a WWW fejlődése megértésének hiánya nem számítástudományi kérdés, hanem egy olyan tudományos váz hiányából ered, amely a mögötte álló hálózat topológiáját jellemezné.

Hálózatok mindenhol vannak. Az agy axonok által összekötött idegsejtek hálózata, maguk a sejtek pedig biokémiai reakciók által összekötött molekulák hálózatai. A társadalmak szintén hálózatok, olyan emberek hálózatai, akiket a barátság, a családi kapcsolatok és szakmai kötelékek kötnek össze. Magasabb szinten a táplálékláncok és ökoszisztémák a fajok hálózataiként ábrázolhatók. A hálózatok átjárják a technológiát is: az internet, az elektromos hálózatok, valamint a szállítási rendszerek csupán néhány példa erre. Még a nyelv is, amit gondolataink közvetítésre használunk, önmagában véve nem más, mint szintaktikai kapcsolatokkal összekötött szavak hálózata.

Mégis, a mindent átható hálózatok fontosságának ellenére a tudósok kevéssé értették meg struktúrájukat és tulajdonságaikat. Hogyan eredményez rákot számos hibásan működő gén kölcsönhatása egy komplex genetikai hálózatban? Hogyan képes olyan gyorsan elterjedni bizonyos társadalmi és kommunikációs hálózatokon keresztül, betegségek és olyan számítógépes vírusok járványait okozva, mint például a Love Bug? Hogyan tud néhány hálózat még azután is tovább működni, hogy csomópontjaik túlnyomó többsége elromlott?

Az újabb keletű kutatások kezdték megválaszolni az ilyen kérdéseket (Barabási, 2003; Albert - Barabási, 2002; Pastor-Satorras - Vespignani, 2004; Barabási - Oltvai, 2004). Az elmúlt néhány év során különböző területeken dolgozó tudósok felfedezték, hogy a komplex hálózatok olyan alapvető szerkezettel jellemezhetők, amelyet egyetemes alapelvek irányítanak. Felfedeztük például, hogy számos hálózatot - a world wide webtől a sejt anyagcsererendszerén át a hollywoodi színészekig - viszonylag kisszámú csomópont ural, amelyek erősen kapcsolódnak más csomópontokhoz. Ezek a fontos csomópontok, a "középpontok" nagymértékben befolyásolhatják egy hálózat általános viselkedését, például figyelemreméltóan szilárddá tehetik véletlen hibákkal, azonban rendkívül sebezhetővé összehangolt támadásokkal szemben.


A véletlen hálózat paradigma


Több mint negyven évig a tudomány teljesen véletlenként kezelt minden komplex hálózatot. E paradigma gyökerei két magyar matematikus, Erdős Pál és Rényi Alfréd munkájából erednek, akik 1959-ben, a kommunikációban és az élettudományokban látható hálózatok leírása érdekében azt javasolták, hogy a hálózatokat véletlenszerűen kellene építenünk (Erdős - Rényi, 1959, 1960). A receptjük egyszerű volt: végy N csomópontot, és kösd össze L véletlenszerűen elhelyezett kapcsolattal. A modell egyszerűsége, valamint az Erdős és Rényi által javasolt kapcsolódó tételek némelyikének eleganciája új életre keltette a gráfelméletet, amely a matematika egy új - a véletlen hálózatokra fókuszáló - területének kialakulásához vezetett (Bollobás, 1985).

A véletlen hálózat elv egyik fontos előrejelzése, hogy annak ellenére, hogy véletlenszerűen helyezzük el a kapcsolatokat, az ebből származó hálózat mélyen demokratikus, hiszen a legtöbb csomópontot hozzávetőleg ugyanannyi kapcsolat jellemzi. Valóban, egy véletlen hálózatban a csomópontok egy harang alakú Poisson-eloszlást követnek, és rendkívül ritkán lehet olyan csomópontokat találni, amelyek jelentősen több vagy kevesebb kapcsolattal jellemezhetők, mint az átlagos csomópont. A véletlen hálózatokat exponenciális hálózatoknak is nevezik, mivel annak valószínűsége, hogy egy csomópont k másik csomóponthoz kapcsolódik, exponenciálisan csökken nagy k esetén (1. ábra). Az Erdős-Rényi-modell azonban felvet egy fontos kérdést: hisszük-e, hogy a természetben megfigyelt hálózatok igazán véletlenszerűek? Képes lenne-e az internet ezt a viszonylag gyors és láthatatlan szolgáltatást nyújtani nekünk, ha a számítógépek véletlenszerűen kapcsolódnának egymáshoz? Vagy, hogy egy szélsőségesebb példát vegyünk, képes lenne-e olvasni ezt a cikket, ha egy bizonyos pillanatban a testében levő kémiai anyagok úgy döntenének, hogy véletlenszerűen reagálnak egymásra, kikerülve a merev kémiai hálót, amelyhez rendes körülmények között alkalmazkodnak? A válasz ösztönösen nem - mindannyian érezzük, hogy minden komplex rendszer mögött létezik egy annak alapjául szolgáló hálózat nem véletlen topológiával. Így a mi feladatunk felkutatni a rendezettség jeleit a csomópontok és kapcsolatok millióinak ebben a látszólagos káoszában.


A world wide web és az internet mint komplex hálózatok


A WWW több mint egymilliárd dokumentumot tartalmaz, amelyek ennek a komplex hálónak a csomópontjait jelentik. URL-ek kötik össze őket, amelyek lehetővé teszik, hogy egyik dokumentumról egy másikhoz navigáljunk. A tulajdonságainak elemzése érdekében szükségünk van egy térképre, amelyik elárulja nekünk, hogyan kapcsolódnak egymáshoz az oldalak. Ezt az információt keresőgépek gyűjtik össze rutinszerűen, mint például a Google vagy az Alta Vista, ezek azonban gyakran vonakodnak megosztani ezeket kutatási célokra. Így hozzá kellett jutnunk a saját térképünkhöz. Pontosan ezt tettük 1998-ban - írtunk egy robotot vagy keresőrobotot, amelyik egy adott weblapról kiindulva összegyűjtött minden kimenő kapcsolatot, és követte azokat, hogy ellátogasson a vonatkozó oldalakra, és még több kapcsolatot gyűjtsön össze (Albert et al., 1999). Ezen az ismétlődő folyamaton keresztül feltérképeztük a web egy kis részletét.

Jelenleg körülbelül nyolcvan dokumentum létezik világszerte, amelyik a mi weblapunkra (www.nd.edu/~networks) mutat. Míg teljes ellenőrzést gyakorolunk a weblapunkról kimenő linkek kout száma felett, a bejövő linkek kin számáról mások döntenek, így ez jellemzi az oldal népszerűségét. A másik oldalon az internet maga routerek hálózata, amelyek adatkötegeket navigálnak egyik számítógéptől a másikig. A routerek különböző fizikai vagy drót nélküli kapcsolatokkal kötődnek egymáshoz, és különböző címtartományokba oszlanak. Annak valószínűsége, hogy egy weblapot kin vagy kout kapcsolat jellemez, hatványfüggvény alakú. Az eredmények egy több mint 325 000 weblapot tartalmazó mintán alapulnak, amelyet Hawoong Jeong gyűjtött.

Mivel a WWW irányított hálózat, minden dokumentum jellemezhető a kimenő (kout) és bejövő (kin) kapcsolatok számával. Az első általunk vizsgált mennyiség a kimenő (bejövő) fokszámeloszlás volt. P(k) a valószínűsége annak, hogy egy véletlenszerűen kiválasztott weblapot pontosan kout (kin) kapcsolat jellemzi. A véletlen gráfok elmélete által vezérelve azt vártuk, hogy P(k) Poisson-eloszlású. Így meglehetősen meglepő volt, amikor az adatok azt mutatták, hogy P(k) hatványfüggvény szerint csökkent,


ahol

Jelentős különbségek mutatkoznak a Poisson- vagy hatványfüggvény-eloszlású hálózatok között (amint azt az 1. ábra mutatja). Valóban, véletlen hálózatoknál a legtöbb csomópontnak hozzávetőleg ugyanakkora számú kapcsolata van, k ??k?, ahol ?k? az átlagos fokszámot jelöli. P(k) exponenciális csökkenése garantálja az olyan csomópontok hiányát, amelyeknek jelentősen több a kapcsolatuk, mint ?k?. Ezzel ellentétben, a hatványfüggvény-eloszlás magában foglalja, hogy a csupán kevés kapcsolattal bíró csomópontok nagy számban vannak jelen, azonban egy elhanyagolható kisebbségnek nagyon nagy számú kapcsolata van. A közúti térkép például, amelynél a városok a csomópontok és az országutak a kapcsolatok, egy exponenciális hálózat, mivel a legtöbb város 2-5 országút kereszteződésénél található. A másik oldalon a skálafüggetlen hálózatok inkább egy légiforgalmi irányító térképre hasonlítanak, amelyet divatos repülős magazinokban szokás bemutatni: a legtöbb repülőteret csupán egy kevés szállítmányozó szolgálja, azonban van néhány középpont, például Chicago vagy Frankfurt, amelyekből kapcsolatok indulnak majdnem minden másik egyesült államokbeli vagy európai repülőtérre. Így mint a kisebb repülőtereknek, a WWW-ben a dokumentumok többségének csupán kevés kapcsolata van. Ez a kevés kapcsolat nem elegendő a hálózat teljes összeköttetésének biztosítására, amely funkciót viszont néhány nagymértékben kapcsolódó középpont garantálja, a csomópontokat összetartva.

Amíg egy Poisson-eloszlásnál egy tipikus csomópontot k ???k? kapcsolat jellemez, az átlag, ?k?, nem különösebben fontos egy hatványfüggvény-eloszlás esetén. Egy belső skála ilyen hiánya arra ösztönzött minket, hogy a hatványfüggvény-eloszlású hálózatokat skálafüggetleneknek nevezzük (Barabási - Albert, 1999). A felfedezés, hogy a WWW skálafüggetlen hálózat, fontos kérdést vetett fel: kialakulhatna-e ilyen inhomogén topológia más komplex rendszerekben is? Erre a kérdésre mostanában váratlan irányból érkezett válasz: az internet felől. Az internet fizikai hálózatot alkot, amelynek csomópontjai routerek és címtartományok, míg a kapcsolatok a különböző fizikai útvonalakat jelölik, például telefonvonalakat, optikai kábeleket, amelyek összekötik őket. A kapcsolatok fizikai természetének megfelelően várható volt, hogy ez a hálózat különbözik a WWW-től, ahol egy link hozzáadása egy tetszőleges távoli oldalhoz olyan könnyű, mint hozzákapcsolódni a szomszéd szobában lévő számítógéphez. Sokak meglepetésére a hálózat mögötti internet, úgy tűnik, szintén hatványfüggvényszerű fokszámeloszlást követ. Ezt először három testvér figyelte meg, Michalis, Petros és Christos Faloutsos, számítógéptudósok Egyesült Államok-beli és kanadai egyetemeken, akik router- és domainszinten elemezték az internetet. Ezen esetek mindegyikében azt találták, hogy a fokszámeloszlás hatványfüggvényt követ ??=2,5 exponenssel a routerhálózat és ??=2,2 exponenssel a domaintérkép esetén, jelezve, hogy az internet huzalozását is számos, nagymértékben kapcsolódó középpont uralja (Faloutsos et al., 1999).


19 lépésnyi távolság


Stanley Milgram harvardi szociológus 1967-ben merész állítással lepte meg a világot: a társadalomban két személy tipikusan öt-hat kézfogásra van egymástól (Milgram, 1967). Vagyis, bolygónk hatmilliárd lakosa ellenére, "kisvilágban" élünk. A társadalmi hálózatok ilyen tulajdonsága "a hatlépésnyi távolságként" vált ismertté John Guare briliáns Broadway-színdarabja és filmje után (Guare, 1990). A szociológusok ismételten vitatták, hogy a társadalmi hálózatok csomópontjai kis halmazokba csoportosulnak, baráti és ismeretségi köröket jelölve, amelyekben minden csomópont hozzákapcsolódik minden más csomóponthoz, csupán gyér számú kapcsolattal kötődve a kinti világhoz (Granovetter, 1973). Míg az ilyen helyi csoportosulás és kisvilág-viselkedés megfelel ösztönös megérzéseinknek, előreláthatatlan volt, hogy ezek a jellegzetességek a társadalmi rendszereken túl is lényegesek lehetnek. A kérdés az: követi-e az internet és a WWW ezt a paradigmát? A helyes válaszhoz szükségünk van a web teljes térképére. Azonban, amint Steve Lawrence és Lee Giles 1998-ban megmutatták, még a legnagyobb keresőgépek is csupán a web 16 %-át fedik le (Lawrence - Giles, 1998, 1999). Ez az, ahol a statisztikus mechanika eszközei kapóra jönnek - a teljes web sajátságaira kell következtetnünk egy véges számú mintából.

Ennek érdekében elkészítettük a WWW kis modelljeit a számítógépen, biztosítva, hogy a kapcsolat eloszlása megegyezik a mért működési formával (Albert et al., 1999). A következő lépésként megállapítottuk a két csomópont közti legrövidebb távolságot, és átlagoltuk ezeket minden csomópont-párra, így megkapva a d átlagos csomópont-távolságot. Megismételve ezt különböző méretű hálózatokra, véges méretskálázást, a statisztikus mechanika egy standard eljárását alkalmazva arra a következtetésre jutottunk, hogy d a csomópontok N számától függ, mivel d = 0,35 + 2,06 × log(N). Amikor 1999-ben a WWW-nek 800 millió csomópontja volt, ez azt vetítette előre, hogy a két véletlenszerűen kiválasztott oldal közötti legkisebb tipikus távolság körülbelül 19 - feltételezve, hogy létezik ilyen útvonal, ami a web irányított természetének köszönhetően nem garantált. Egy IBM-Compaq-AltaVista együttműködésben készült, kiterjedt tanulmány ezután azt találta, hogy a 200 millió csomópontra ez a távolság 16 - nem túl messze a 17-től, amit a mi képletünk jövendölt egy ilyen méretű mintára (Broder et al., 2000). Ezek az eredmények tisztán megmutatták, hogy a WWW egy kisvilágot jelöl, azaz két weblap közti klikkelések tipikus száma 19, a több mint milliárd lap ellenére. És amint azt Lada Adamic a Stanford Egyetemről megmutatta, a WWW nagyfokú csoportosulást is felmutat, mivel annak valószínűsége, hogy egy adott csomópont két szomszédja összekapcsolódik, sokkal nagyobb egy csoportosulásmentes véletlen hálózat esetében várható értéknél (Damic - Huberman, 1999). Csoportunk eredményei azt mutatták, hogy az internet is hasonlóan működik - két router között a tipikus távolság kilenc, azaz egy köteg bármely routert el tud érni tíz ugráson belül (Yook et al., 2002), a hálózat pedig nagymértékben csoportosodott, mutatva, hogy a kisvilág-paradigma gyorsan átitatta a Föld újonnan fejlődő elektronikus bőrét.


Fejlődő hálózatok


Miért alakítanak ki olyan különböző rendszerek, mint az internet fizikai hálózata vagy a WWW virtuális hálója hasonló skálafüggetlen hálózatokat? Mostanában vezettük vissza a hatványfüggvény fokszám eloszlásának kialakulását két általános mechanizmusra, amelyek hiányoznak a klasszikus gráfmodellekből, de jelen vannak számos komplex hálózatban (Barabási - Albert, 1999). A hagyományos gráfelméleti modellek feltételezték, hogy az egy hálózatban található csomópontok száma rögzített. Ezzel ellentétben a WWW folyamatosan terjeszkedik új weblapok hozzáadásával, az internet pedig növekszik új routerek és kommunikációs kapcsolatok bevezetésével. Továbbá, míg a véletlen gráfoknál feltételezik, hogy a kapcsolatok véletlenszerűen oszlanak el, a legtöbb valódi hálózat preferenciális kapcsolódásról tesz bizonyságot: nagyobb a valószínűsége az olyan csomóponthoz való kapcsolódásnak, amelyiknek nagyszámú kapcsolata van. Valóban, nagyobb valószínűséggel kapcsoljuk weblapunkat a több kapcsolattal jellemezhető dokumentumokhoz a WWW-n, mivel ezek azok, amelyekről tudunk; a hálózati mérnökök hajlamosak az intézményüket olyan pontokon keresztül kapcsolni az internethez, ahol nagy a sávszélesség, amely szükségszerűen magában foglal nagyszámú egyéb fogyasztót vagy kapcsolatot. E két összetevőn alapulva létrehoztunk egy egyszerű modellt, amelyben minden időegységben egy új csomópont adódik a hálózathoz, a rendszerben jelen lévő csomópontok némelyikéhez kapcsolódva (2. ábra) (Barabási - Albert, 1999). Annak valószínűsége, ? (k), hogy egy új csomópont k linkkel kapcsolódik egy csomóponthoz, a preferenciális kapcsolódást követi,




ahol az összeg minden csomóponton átmegy. A numerikus szimulációk azt mutatják, hogy az ebből eredő hálózat valóban skálafüggetlen, és annak valószínűsége, hogy a csomópontnak k kapcsolata van, (1)-ből ? = 3 kitevővel számítható (Barabasi et al., 1999). Ez az egyszerű modell illusztrálja, hogyan vezet a növekedés és a preferenciális kapcsolódás együttesen a középpont-hierarchia megjelenéséhez: egy kapcsolatokban gazdag csomópont gyorsabban fogja növelni a kapcsolatainak számát, mint a többi csomópont, mivel a bejövő csomópontok nagyobb valószínűséggel kapcsolódnak hozzá. Ez "a gazdag még gazdagabbá válik" jelenség, amely sok versenyrendszerben jelen van.

A hálózatokat hagyományosan statikus dologként szemlélték, a modellező szerepe megtalálni annak módját, hogy állandó számú csomópont között úgy helyezze el a kapcsolatokat, hogy az eredményként létrejövő hálózat hasonlóan nézzen ki, mint a hálózat, amelyet modellezni kívánunk. Ezzel ellentétben a skálafüggetlen modell a hálózatot dinamikus rendszernek tekinti, magában foglalva a tényt, hogy önállóan áll össze, és csomópontok, valamint kapcsolatok hozzáadása és eltávolítása által alakul ki az időben. Az ilyen dinamikus megközelítés a fizikán alapuló modellezés hagyományát követi, amelynek célja megragadni a módot, ahogy a természet összeállította ezeket a hálózatokat. A várakozás e modellezési törekvések mögött az, hogy ha megragadjuk a kapcsolatok és csomópontok elhelyezését irányító mikroszkopikus folyamatokat, a strukturális elemek és a topológia ezekből következik. Ezenkívül a kialakuló hálózatok dinamikus rendszerekként való szemlélete lehetővé teszi számunkra, hogy analitikus módszerrel megjósoljuk számos tulajdonságukat.


Bose-Einstein-kondenzáció


A legtöbb komplex rendszerben a csomópontok különböznek a kapcsolatokért való versengés képességét tekintve. Néhány weblap például marketing és jó tartalom keveréke által rövid idő alatt nagyszámú linkre tesz szert, könnyedén felülmúlva kevésbé népszerű oldalakat, amelyek sokkal hosszabb ideje léteznek. Jó példa a Google keresőgép: viszonylag újonnan érkező, kiváló termékkel, kevesebb mint két év alatt a WWW egyik legtöbb kapcsolatát felmutató csomópontjává vált. Ez a kapcsolatok iránti versengés belefoglalható a skálafüggetlen modellbe, oly módon, hogy minden csomóponthoz egy fittséget rendelünk, amely annak képességét jellemzi a kapcsolatokért való versenyben más csomópontokkal szemben (Bianconi - Barabási, 2001a). Egy véletlenszerűen kiválasztott ?i fittség kijelölése minden i csomóponthoz a következőképpen módosítja a növekedési rátát (2) esetén


Az egyenlőtlen fittség által generált versengés multiskálázáshoz vezet: egy adott csomópont kapcsolatainak száma a következőképpen alakul: ki(t) ? t ????, ahol ??????-nel növekszik, lehetővé téve a nagy ?-jú fittebb csomópontok számára, hogy egy későbbi időpontban csatlakozzanak a hálózathoz, és felülkerekedjenek a régebbi, de kevésbé fitt csomópontok felett.

A fittségi verseny modelljei szoros kapcsolatban vannak a Bose-Einstein-kondenzációval, amely jelenleg az egyik legtöbbet vizsgált probléma a nagy sűrűségű anyag fizikájában. Valóban, mostanában fedeztük fel (Bianconi - Barabasi, 2001b), hogy a fittség modell pontosan leképezhető egy Bose-gázba, ha minden csomópontot kicserélünk ?i = e-??i szintű energiával. E térképezés szerint az i csomóponthoz kötődő kapcsolatokat az eI szintjén részecskékkel helyettesítjük, a Bose-gáz viselkedését pedig páratlan módon megszabja g(?) eloszlás, amelyből a fittség kiválasztódik. A g(?) működési formája várhatóan rendszerfüggő: egy hálózat esetén egy router vonzereje egy másik eloszlásból ered, mint a fogyasztókért versengő .com társaságok fittsége. A fittségi eloszlások széles osztályára kialakul a gazdag még gazdagabbá válik jelenség, amelyben, miközben a legfittebb csomópont több kapcsolatot szerez meg, mint kevésbé fitt megfelelői, nincs határozott győztes. A másik oldalon bizonyos fittségi eloszlások Bose-Einstein-kondenzációt eredményezhetnek, amelyek a hálózati nyelvben megegyeznek a győztes mindent visz jelenséggel: a legfittebb csomópont biztos nyertesként jelentkezik, kondenzációt alakítva ki azáltal, hogy megszerzi a kapcsolatok egy véges részletét, mely független a rendszer méretétől.


Az internet Achilles-sarka


Amint a világgazdaság növekvő mértékben válik függővé az internettől, egy gyakran kimondott aggodalom támad: fenn tudjuk-e tartani funkcionális voltát elkerülhetetlen hibák vagy gyakori hackertámadások közepette? A jó hír az, hogy mostanáig az internet meglehetősen rugalmasnak bizonyult a hibákkal szemben: miközben minden pillanatban a routerek mintegy 3 %-a nem működik, alig érzékelünk jelentősebb töréseket. A kérdés az, honnan származik ez a robusztusság? Jelentős hibatűrés van beépítve a csomagkapcsolást irányító protokollokba, de újabban megtudtuk, hogy a skálafüggetlen topológia szintén döntő szerepet játszik. A hibatűrés hálózati komponensének megismerésében segítséget kapunk a perkolációtól, a fizika egy sokat tanulmányozott területétől. A perkolációelmélet elárulja, hogy csomópontok véletlenszerű eltávolítása egy hálózatból inverz perkolációátmenetet fog eredményezni: fc-nek mint a csomópontok kritikus részletének eltávolításával a hálózatnak egymással nem kommunikáló csomópontok apró szigeteire kellene hullania. Meglepetésünkre a skálafüggetlen hálózatokon végzett szimulációk nem támogatták ezt az elképzelést (Albert et al., 2000): eltávolíthattuk a csomópontok akár 80 %-át, a megmaradó csomópontok még mindig szorosan kapcsolódó fürtöt alkottak. A rejtélyt Shlomo Havlin fedte fel munkatársaival a Bar-Ilan Egyetemen, kimutatva, hogy amíg ? kapcsolódási exponense kisebb, mint 3 (ami igaz a legtöbb valódi hálózatra, beleértve az internetet), a törés kritikus küszöbe fc=1 (Cohen et al., 2000, 2001). Ez bámulatos bemutatása annak, hogy a skálafüggetlen hálózatok nem tördelhetők darabokra a csomópontok véletlen eltávolításával. Ez a hibákkal szembeni extrém robusztusság az inhomogén hálózati topológiában gyökerezik: mivel sokkal több kis csomópont létezik, mint középpont, a véletlenszerű eltávolítás nagy valószínűséggel ezeket érinti majd. Azonban egy kis csomópont eltávolítása nem vált ki jelentősebb törést a hálózati topológiában, amint egy kis helyi repülőtér bezárásának is csekély befolyása van a nemzetközi légiforgalomra, ami megvilágítja a hálózat véletlen hibákkal szembeni robusztusságát. A rossz hír az, hogy az inhomogén topológiának hátulütői is vannak: a skálafüggetlen hálózatok meglehetősen sebezhetőek a támadásokkal szemben (Albert et al., 2000). Valóban, a legtöbb kapcsolattal bíró csomópontok egy apró törése darabokra törné a hálózatot. Ezek a felismerések felfedték a skálafüggetlen hálózatok alapvető topológiai sebezhetőségét: míg az internet várhatóan nem törik meg a routerek és vonalak véletlen hibái miatt, jól informált hackerek könnyedén alakíthatnak ki olyan szcenáriót, amely árthat a hálózatoknak.


Skálafüggetlen járványok


A skálafüggetlen hálózatokkal kapcsolatos ismeretek a számítógépes vírusok, betegségek és szeszélyek megértéséhez is tartalmaznak feltevéseket. A járványkutatók és marketingszakemberek által évtizedek óta behatóan tanulmányozott diffúziós elméletek kritikus küszöböt jósolnak valaminek a populáción keresztüli elterjedésére. Minden vírus, ami kevésbé virulens, mint a jól meghatározott küszöb, elkerülhetetlenül kihal, míg a küszöb felettiek exponenciálisan megsokszorozódnak, végső fokon áthatva az egész rendszert.

Újabban azonban Romualdo Pastor-Satorras, a barcelonai Unversidad Politčcnica de Catalunya és Allessandro Vespignani, a bloomingtoni Indiana Egyetem munkatársa meglepő következtetésre jutottak (Pastor-Satorras - Vespignani, 2001). Azt találták, hogy egy skálafüggetlen hálózatban a küszöb zéró. Vagyis minden vírus, még azok is, amelyek csak gyengén fertőzőek, el fognak terjedni, és fenn fognak maradni a rendszerben. Ez magyarázza, hogy a Love Bug, mostanáig a legkárosabb vírus, amelyik 2000-ben megtámadta a brit parlamentet, csupán a hetedik leggyakoribb vírus volt még egy évvel a bevezetése és feltételezett megsemmisítése után is. A meglepő viselkedés kulcsai a középpontok (hub). Mivel a középpontokból nagyszámú kapcsolat indul ki, legalább egy közülük hajlamos lesz megfertőződni bármely fertőzött csomópont által. Ha pedig egy középpont egyszer megfertőződik, szét fogja sugározni a vírust számos más oldalra, végső soron veszélyeztetve más középpontokat, amelyek aztán segítenek elterjeszteni a vírust az egész rendszerben.

Mivel a biológiai vírusok társadalmi hálózatokban terjednek, amelyek sok esetben skálafüggetleneknek bizonyulnak, ez az eredmény azt sugallja, hogy a tudósoknak egy második pillantást kellene vetniük a hálózati topológia és a járványok kölcsönhatásáról írt kutatási anyagokra. Különösen egy skálafüggetlen kapcsolathálózatban, a véletlen immunizálás hagyományos közegészségügyi megközelítése könnyedén eredménytelen maradhat, mivel valószínűleg figyelmen kívül hagy a középpontok közül néhányat. A skálafüggetlen hálózatokkal kapcsolatos kutatások egy alternatív megközelítést javasolnak: a középpontokat vagy a legtöbb kapcsolattal rendelkező egyéneket megcélozva, az immunizálásnak a populáció csupán egy kis töredékét kell elérnie (Dezső - Barabasi, 2002; Pastor-Satorras - Vespignani, 2002; Cohen et al., 2003). A középpontok meghatározása egy társadalmi hálózatban azonban sokkal nehezebb, mint más rendszertípusok, például az internet esetében. Mindazonáltal Reuven Cohen és Shlomo Havlin az izraeli Bar-Ilan Egyetemről a New York-i Clarkson Egyetemen dolgozó Daniel ben-Avrahammal együtt nemrégiben okos megoldást javasoltak (Cohen et al., 2003): tedd védetté véletlenszerűen kiválasztott egyének véletlen ismerőseinek egy kis részét - ez egy olyan eljárás, amely nagy valószínűséggel választja ki a középpontokat, mivel ők sok emberrel állnak ismeretségben. Ez a megközelítés azonban fontos etikai dilemmákat vet fel. Például, még ha meg is lehetne határozni a középpontokat, elsőbbséget kellene-e kapniuk az immunizációnál és a kezelésnél?

Számos üzleti kontextusban az emberek járványokat akarnak indítani, nem pedig megállítani. Sok vírus jellegű marketingkampány például kifejezetten megpróbál középpontokat megcélozni, hogy a lehető leggyorsabban elterjesszen egy terméket. Természetesen ez a stratégia nem új. A Pfizer gyógyszerészeti óriás által támogatott tanulmány egészen az 1950-es évekig visszamenően feltárta azt a fontos szerepet, amelyet a középpontok játszanak abban, hogy orvosok egy adott közössége milyen gyorsan vesz át egy új gyógyszert. Valóban, a marketingszakemberek egy ideje ösztönösen tudják, hogy bizonyos fogyasztók sokkal hatékonyabbak az új termékekkel kapcsolatos promóciós hírek terjesztésében. A skálafüggetlen hálózatokkal kapcsolatban újabban végzett munka azonban biztosítja a tudományos vázat és a matematikai eszközöket a jelenség precízebb vizsgálatához.


Perspektíva


Habár a skálafüggetlen hálózatok meglepően elterjedtek, léteznek kiemelkedő kivételek. Például a közúti hálózat és az elektromos hálózat az Egyesült Államokban nem skálafüggetlen. Más hálózatok esetén az adatok nem meggyőzőek. A kisszámú, megbízhatóan feltérképezett tápláléklánc, amely elárulja, hogyan élnek egymásból a fajok, nem tette lehetővé a tudósok számára, hogy világos következtetésre jussanak a hálózat típusát illetően. Az agy nagy léptékű kapcsolati térképének hiánya nem engedi meg, hogy megállapítsuk e kritikus hálózat természetét. Az anyagtudományban látható legtöbb hálózat, például a kristályrács, amely leírja a szilárd anyagokban lévő atomok közti kölcsönhatásokat, szintén nem skálafüggetlen, de minden atomnak azonos számú kapcsolata van más atomok felé, ami meglehetősen szabályos hálózati topológiához vezet.

Talán még fontosabbak az egyéb paraméterek, amelyek meghatározzák egy hálózat szerkezetét. Az egyik ilyen tulajdonság a hálózat átmérője vagy pályahossza: a legnagyobb számú ugrás, amely szükséges ahhoz, hogy bármely csomóponttól eljussunk bármely más csomóponthoz a lehető legrövidebb utat követve. A kis átmérőjű hálózatokat "kisvilág"-nak nevezik, és jelenleg sok kutatás vizsgálja ezt és más kapcsolódó jelenségeket, például a csomópontok csoportosulását és hierarchiáját.

Végezetül, megérteni egy hálózat szerkezetét csak a történet egy része. Például minden újabb kapcsolatnak egy csomóponthoz való adásakor megjelenhetnek túlzott károk, amelyek megakadályozhatnák, hogy bizonyos hálózatok, pl. az USA közúti rendszere, skálafüggetlené váljanak. A táplálékláncban néhány zsákmányt könnyebb megfogni, mint másokat, és ez a tény mélyreható befolyással bír az egész hálózatra. A társadalmi hálózatoknál a családtagokhoz fűződő kapcsolatok erősségüket tekintve sokban különböznek az ismerősökkel való kapcsolatoktól. Szállítási, transzmissziós és az internethez hasonló kommunikációs rendszerek esetén a specifikus kapcsolatok mentén jelentkező forgalmi torlódások jelentős tényezők.

Lényegében eleinte úgy tanulmányoztuk a komplex hálózatokat, hogy ez egyedi kapcsolataik és csomópontjaik részleteit figyelmen kívül hagytuk. Eltávolodva ezektől a sajátságoktól jobban meg tudtunk figyelni néhány szervező elvet a látszólag érthetetlen rendszerek mögött. Legvégül, az ebből a kísérletből származó tudás számos alapvető feltevés újragondolásához vezetett. A múltban például a kutatók véletlen hálózatként modellezték volna az internetet, hogy teszteljék, egy új forgalmi protokoll hogyan befolyásolná a rendszertorlódást. Azonban, amint most már tudjuk, az internet olyan viselkedésű skálafüggetlen rendszer, amely drámaian különbözik a véletlen hálózatokétól. Következésképpen a kutatók újraépítették a számítógépmodelleket, amelyeket az internet szimulálására használtak. Hasonlóképpen, a skálafüggetlen hálózatok tulajdonságainak ismerete felbecsülhetetlen lesz számos más területen, különösen ahogy túlhaladunk a hálózati topológiákon, hogy megvizsgáljuk az ezekben a komplex rendszerekben megtalálható bonyolult és gyakran nehezen megfogható dinamikát.

Az itt tárgyalt előnyök csupán a jéghegy csúcsát jelentik. A hálózatok az összetettség architektúráját ábrázolják. Azonban ahhoz, hogy teljesen megértsük a komplex rendszereket, e szerkezet mögé kell mennünk, és fel kell fednünk az alapvető dinamikus folyamatokat irányító törvényeket, például az internetes forgalomban vagy a sejt reakciókinetikájában. A legfontosabb, hogy meg kell értenünk, hogy a komplexitás, szerkezet és dinamika e két rétege hogyan alakul ki együtt. Ezek mind hatalmas kihívások a fizikusok, biológusok és matematikusok számára, új korszakot vezetve be, amelyet Stephen Hawking nemrég a "komplexitás századának" nevezett.


Kulcsszavak: skálafüggetlenség, világháló, Bose-Einstein-eloszlás


Angolból fordította: Arany Zsuzsanna



1. ábra * Véletlen és skálafüggetlen hálózatok. A véletlen hálózat fokszáma Poisson-eloszlást követ, amely alakját tekintve nagyon közel haranggörbe. Ekkor a legtöbb csomópontnak azonos számú kapcsolata van, és nem létezik kiemelkedően sok kapcsolatú csomópont (fent balra). Így a véletlen hálózat hasonló egy országos közúti hálózathoz, amelyben a csomópontok a városok, a kapcsolatok pedig az őket összekötő főútvonalak. Valóban, a legtöbb várost durván ugyanakkora számú közút szolgálja (lent balra). Ezzel ellentétben, egy skálafüggetlen hálózat hatványfüggvényű fokszámeloszlása előrevetíti, hogy a legtöbb csomópontból csupán kevés kapcsolat indul ki, amelyeket néhány nagymértékben összekapcsolt középpont tart össze (fent jobbra). Ez vizuálisan nagyon hasonló a légiközlekedési rendszerhez, amelyben nagyszámú kis repülőtér kapcsolódik egymáshoz néhány fő középpont által (lent jobbra). (Barabási, 2003 után)

2 ábra * Egy skálafüggetlen hálózat születése. A skálafüggetlen topológia természetes következménye a valódi hálózatok mindig terjeszkedő természetének. Két összekapcsolt csomópontból kiindulva (fent balra) minden panelen egy új csomópont (üres körként jelölve) adódik hozzá a hálózathoz. Amikor döntenek, hova kapcsolódjanak, a csomópontok előnyben részesítik a több kapcsolatú csomópontokhoz való kötődést. A növekedésnek és a preferenciális kapcsolódásnak köszönhetően kialakul néhány nagyszámú kapcsolattal jellemezhető középpont (Barabási, 2003 után).


IRODALOM

Adamic, L. A. - Huberman, B. A. (1999): Growth Dynamics of the World Wide Web. Nature. 401, 131.

Albert Réka - Jeong, H. - Barabási A.-L. (2000): The Internet's Achilles' Heel: Error - Attack Tolerance in Complex Networks. Nature. 406, 378.

Albert Réka - Barabási A.-L. (2002): Statistical Mechanics of Complex Networks, Review of Modern Physics. 74, 47-97.

Albert Réka - Jeong, H. - Barabási A.-L. (1999): Diameter of the World Wide Web. Nature. 401, 130-131.

Barabasi Albert-László (2001): The Physics of the Web. Physics World. 33-38.

Barabasi Albert-László (2003): Linked: The New Science of Networks. Plume Books, MA

Barabási Albert-László - Albert Réka (1999): Emergence of Scaling in Random Networks, Science. 286, 509-512.

Barabási Albert-László - Oltvai Zoltán N. (2004): Network Biology: Understanding the Cells's Functional Organization. Nature Reviews Genetics. 5, 101-113.

Barabasi Albert-László - Albert R. - Jeong, H. (1999): Physica A. 272, 173

Bianconi, Ginestra - Barabási A.L. (2001a): Europhysics Letters. 54, 436

Bianconi, Ginestra - Barabási A.L. (2001b): Physical Review Letters. 86, 5632

Bollobás Béla (1985): Random Graphs. Academic, London

Broder, Andrei - Kumar, R. - Maghoul, F. - Raghavan, P. - Rajalopagan, S. - Stata, R. - Tomkins, A. - Weiner, J. (2000): Graph Structure in the Web. Computer Networks. 33, 1-6, 309-320.

Cohen, Reuven - Reez, K. - Ben-Avraham, D. - Havlin, S. (2000): Resilience of the Internet to Random Breakdowns. Physical Review Letters. 85, 4626.

Cohen, Reuven - Reez K. - Ben-Avraham D. - Havlin S. (2001): Physical Review Letters. 86, 3682.

Cohen, Reuven - Havlin S. - ben-Avraham D. (2003): Efficient Immunization Strategies for Computer Networks - Populations. Physical Review Letters.91, 247901

Dezső Zoltán - Barabási Albert-László (2002): Can We Stop the AIDS Epidemic? Physical Review E. 65, 055103(R)

Erdős Pál - Rényi Alfréd (1959): Publicationes Mathematicae Debrecen. 6, 290.

Erdős Pál - Rényi Alfréd (1960): Publications of the Mathematical Institute of the Hungarian Academy of Sciences. 5, 17.

Faloutsos, Michalis - Faloutsos P. - Faloutsos C. (1999): On Power-law Relationships of the Internet Topology. ACM SIGCOMM 99. Computer Communication Review. 29, 251

Granovetter, Mark S. (1973): American Journal of Sociology. 78, 1360.

Guare, John (1990): Six Degrees of Separation. Vintage Books; NY

Lawrence, Steve - Giles, C. Lee (1998): Science. 280, 98

Lawrence, Steve - Giles, C. Lee (1999): Accessibility of Information on the Web. Nature. 400, 107

Milgram, Stanley (1967): Psychology Today. 1, 60.

Pastor-Satorras, Romualdo - Vespignani, Allessandro (2001): Physical Review Letters. 86, 3200

Pastor-Satorras, Romualdo - Vespignani, Allessandro (2002): Immunization of Complex Networks. Physical Review E. 65, 036104

Pastor-Satorras, Romualdo - Vespignani, Allessandro (2004): Evolution - Structure of the Internet: A Statistical Physics Approach, Cambridge University Press

Yook, Soon-Hyung - Jeong, H. - Barabási A.-L. (2002): Modeling the Internet's Large-Scale Topology. Proceedings of the National Academy of Sciences of the USA 99, 13382.


<-- Vissza a 2006/11 szám tartalomjegyzékére


<-- Vissza a Magyar Tudomány honlapra