I. Bevezető a gráfokról

A Mindentudás Egyetemének sok előadása foglalkozott már hálózatokkal (matematikai nevükön gráfokkal). A legutóbbi két előadásban Vicsek Tamás és Kertész János a tudomány, technika és társadalom legkülönbözőbb területein megtalálható hálózatokat vizsgálta. Itt az ideje, hogy a matematikus szemével, általánosan is megnézzük ezeket a nagy hálózatokat.

Első ábránkat (1. ábra) akár egy gráfelméleti tankönyvből is vehetnénk. Egy gráf csúcsokból és a csúcsokat összekötő élekből áll. Egy csúcs fokának (fokszámának) nevezzük a belőle kiinduló élek számát. Annak illusztrálására, hogy milyen jellegű kérdéseket lehet vizsgálni egy ilyen gráffal kapcsolatban, említsünk meg egyet: mikor lehet egy gráfot egyetlen vonallal úgy lerajzolni, hogy minden élen pontosan egyszer haladunk át? Ezt a - talán legklasszikusabb - gráfelméleti kérdést a königsbergi hidak problémájának nevezik, és Euler oldotta meg több mint 250 évvel ezelőtt. Az 1. ábrán látható gráfot például nem lehet így lerajzolni. Ehhez nézzük azt a csúcsot, melyből 5 él indul ki. Valahányszor áthaladunk a csúcson, két élt használunk el (t.i. egyet a beérkezéshez és egy másikat a továbbhaladáshoz), és mivel az 5 páratlan szám, ezért vagy ebből a csúcsból kell indulnunk, vagy a végén ide kell megérkeznünk. De ugyanez minden páratlan fokú csúcsról elmondható, és ilyen csúcsból négy is van. Tegyük fel, hogy az egyikből indulunk, a másikban végzünk, de még mindig marad két páratlan fokszámú csúcs, amelyekből kiinduló éleket nem tudjuk mind megrajzolni.

A 2. ábra olyan gráfot mutat, melynek 100 csúcsa van.  Ez a mérete alapján lehetne mondjuk egy kisebbfajta beruházás kivitelézési hálója. Ekkora gráfot a rajz alapján már nehéz áttekinteni, de számítógépekkel könnyen kezelhető.

 

A 3. ábra gráfja már egészen ijesztő, bár csak 3000 csúcsa van. Ezt már szemmel egyáltalában nem látjuk át, de számítógéppel még sok fontos tulajdonsága meghatározható. Mi ez azonban az internethez képest?

II. Nagyon nagy gráfok

A 4. ábra két próbálkozást mutat az internet ábrázolására. Szépek, de meg kell jegyeznem, hogy nekem nem sokat mondanak. Sok más nagy hálózat van, amit szeretnénk megérteni. Ilyenek például a legkülönbözőbb társadalmi hálózatok: nem csak az iwiw, de az emberek közötti ismeretségek gráfja, rokonságok gráfja stb, melyeknek több mint hatmilliárd csúcsa van. Más jellegű nagyon nagy hálózatok az integrált áramkörök (chip-ek). Az 5. ábra csak két kis részletét mutatja egy modern integrált áramkörnek, mely százmilliónyi elemből áll. Bár ezek minden részletükben tervezettek, lerajzolásuk és megértésük nehéz, mert olyan hatalmasak.

 

Az agy (6. ábra) százmilliárdnyi csúcsú gráfja talán a legizgalmasabb mind között, de sajnos keveset tudunk róla gráfelméleti szempontból. Hatalmas méretű, bonyolult hálózatokat alkotnak az ökológiai rendszerek. A 7. ábra alapján különböző térségek közötti kölcsönhatásokat modellezhetünk, de lejjebb is mehetünk a fajok, sőt, az egyedek szintjére.

A fizika is szolgáltat néhány nagyon izgalmas hálózatot: talán az egész Világegyetem egyetlen nagy hálózat, mely elemi részekből és az azok közötti kölcsönhatásokból áll. De erről nemigen tudok mit mondani, így inkább egy sokkal egyszerűbb struktúráról fogok néhány szót szólni: a kristályszerkezetről (8. ábra). Egy fémdarab atomokból és azok közötti kötésekből áll. Egy tökéletes kristály gráfja iszonyú sok, mondjuk 10³⁰ csúcsból áll, bár eléggé unalmas, mondjuk egy kocka ismétlődik nagyon sokszor. A valóságban minden kristályban vannak szabálytalanságok (szennyeződések, törésvonalak, hiányok, stb.), amitől érdekessé válik. A kristályos anyagot azonban nem mindig célszerű gráfként elképzelni vagy leírni: a mérnök a kristályt folytonos anyagnak tekinti, melynek fontos tulajdonságait (pl. rugalmasság, nyúlás, rezgések) a matematika eszközeivel, differenciálegyenletekkel írja le. Ugyanakkor más tulajdonságok, mint pl. a mágnesezhetőség vagy az olvadáspont csak az atomos leírásból érthetők meg. Egyebek mellett ezekkel a kérdésekkel foglalkozik a statisztikus fizika. E problémák megoldása gyakran számítógépes szimuláció segítségével történik, amelyben ugyanolyan kristályszerkezetű, de sokkal kisebb, néhány száz vagy ezer atomból álló, idealizált kristályt használnak. Tehát a 1030 atomból álló valódi kristályt kétféleképpen is közelíthetjük: végtelen, folytonos struktúrával illetve sokkal kevesebb atomból álló idealizált kristállymodellel. De vajon lehet-e ilyen közelítéseket keresni más, hasonlóan gigantikus méretű hálózatok esetén is?

Mielőtt a kérdés tárgyalásába kezdenénk, gondoljuk végig, hogy mit is akarunk vizsgálni egy nagyon nagy hálózattal, pl. az internettel kapcsolatban. Nézzünk néhány konkrét kérdést, amit kis gráfokkal kapcsolatban lépten-nyomon felteszünk:

• Páros vagy páratlan számú csúcsa van-e az internetnek?

Ez a kérdés a klasszikus gráfelméletben sokszor előjön, de az internetre vonatkozóan nyilvánvalóan értelmetlen, hiszen egyrészt az internet pillanatról pillanatra változik, másrészt nem világos, hogy hova sorolhatók azok a számítógépek, amelyeket éppen ki- vagy bekapcsolnak.

• Hány éle van az internetnek?

Persze a pontos számra rákérdezni értelmetlenség. Ugyanakkor, ha nem a pontos válasz az érdekes, hanem megengedünk pl. 1%-os pontatlanságot, akkor már értelmes a kérdés.

• Összefüggő-e az internet?

Erre a válasz biztosan az, hogy nem, hiszen valahol egy router biztosan el van romolva, ezáltal néhány boldogtalan felhasználó mindig el van vágva a többitől. A kérdés azonban nem egészen erre irányult, inkább arra, hogy nem esik-e szét az internet két (vagy több), az egésszel összemérhető nagyságú részre. Néhány hete például egy hajó elvágta az Európa és Afrika közötti tengeralatti kábelt és egy időre Afrika egyes részeivel minden kapcsolat megszakadt... Látjuk tehát, hogy ilyen nagyméretű hálózatok esetén a klasszikus kérdések egy része értelmetlen, más részüket pedig módosítani kell ahhoz, hogy érdekesek, relevánsak legyenek.

III. Véletlen gráfok és a sznobizmus

Térjünk rá arra a kérdésre, hogyan lehet egy nagyon nagy hálózathoz hasonlót csinálni kisebb méretben. Véletlenszerűen növekedő nagy hálózatok esetén működő ötlet lehet, ha megpróbálunk hasonló véletlen módszerrel létrehozni egy kisebb hálózatot. Így jutunk a véletlen gráfok elméletéhez. Ennek vizsgálatát Erdős Pál és Rényi Alfréd (9. ábra)  kezdték meg 1960 körül. Az ő modelljükben rögzítünk n csúcsot, és ezek közé véletlenszerűen húzunk be éleket, amíg a kívánt sűrűséget el nem érjük. Egy ilyen Erdős-Rényi-gráf növekedését animáción ^|1}| is megnézhetjük. Az így kapott véletlen gráfokat sokat vizsgálták és sok érdekes tulajdonságot fedeztek fel velük kapcsolatban, de - mint látni fogjuk - az Erdős-Rényi-gráfok az internetet és más hasonló hálózatokat nem írják le elég jól.
1999-ben Barabási Albert-László és Albert Réka (10. ábra) egy olyan modellt javasoltak, mely az internet fontos tulajdonságait (pl. fokszámainak eloszlását) jobban tükrözi. Az ő modelljükben nemcsak élek, hanem csúcsok is születnek, és egy új csúcs születésekor véletlenszerűen, de a fokszámokkal arányos valószínűséggel kiválaszt egy vagy több korábbi csúcsot (az animációban ^|2}|

, és ahhoz köti magát. Tehát azokat a csúcsokat, amelyek népszerűbbek, vagyis több szomszédjuk van, az új csúcs nagyobb valószínűséggel választja. Vagyis a véletlen gráf definíciójába sikerült beépíteni a sznobizmust! De milyen értelemben lesz ez jobb modellje pl. az internetnek?

A fokszámok tanulmányozása meglepő erdeményt hozott: a 11. ábrán egy Erdős-Rényi-gráf fokszámainak statisztikája látható, a vizszintes tengelyen a lehetséges fokszámok vannak feltüntetve, az oszlopok magassága pedig azt mutatja, hogy a csúcsok hányadrészének a foka a vízszintes tengelyen szereplő érték. Az Erdős-Rényi-gráf fokszámeloszlása ú.n. haranggörbe alakú, vagy más szóval normális eloszlást mutat.

 

A valóságban előforduló hálózatok gráfjainak fokszámeloszlása azonban nem haranggörbére emlékeztet, hanem a 12. ábrán látható statisztikához hasonlít. Mindjárt két érdekes tulajdonságot is megfigyelhetünk: egyfelől a gyakoriság maximuma az elején van, vagyis a legkisebb fokszámú csúcsokból van a legtöbb, másfelől a fokszám statisztika a magasabb fokszámok felé haladva egyre lassabban cseng le. Matematikai kifejezéssel: a gyakoriság a fokszám valamilyen hatványa szerint csökken. A társadalomtudományokban már régebben felfedezték azt a jelenséget, hogy a ,,való életből vett" statisztikák igen gyakran ilyen elnyújtott, lassan lecsengő görbékre vezetnek; az jelenséget leírójáról "Zipf-jeleségnek" is nevezik. Ilyen jellegű statisztikát mutatnak egy élettér fajainak egyedszámai, az egyes példányok mérete stb.

Hogy a Zipf-jelenség hátterét megértsük, ismerkedjünk meg a Pólya-urnával, amit Pólya György (13. ábra) az 1920-as években vezetett be! A következő animációban ^|3}|  kétféle urnát láthatunk, az ú.n. közönséges- és a Pólya-urnát. A közönséges urnákba (a baloldali piros edények) minden egyes golyó egyforma valószínűséggel esik az egyikbe vagy a másikba. A Pólya-urnák (a jobboldali kék edények) esetén az új golyó egy már korábban leesett golyót véletlenszerűen kiválaszt, és vele azonos edénybe pottyan (a sznobizmus tehát már ide is be van építve!). A kísérlet végén a 14. ábra tanúsága szerint a közönséges urnában közelítőleg ugyanannyi golyó lesz, amit a nagy számok törvénye alapján is elvárunk. Az első edénybe jutó golyók számának eloszlása az ismerős haranggörbét mutatja. A Pólya-urna esetén viszont egyforma valószínűséggel lesz 1, 2, 3, ... golyó az első edényben. A Pólya-urna magyarázza meg a Barabási-Albert-gráf tulajdonságait.

IV. A Szemerédi-féle regularitási lemma

Térjünk vissza a nagy hálózatokra. Hogyan tudnánk a szerkezetüket megérteni, kevés adattal leírni? Ehhez érdemes egy ábrázolásmóddal megismerkedni. A rajznál néha többet mond a 15. ábrán látható összekötöttségi táblázat (és természetesen számításokban jobban használható). Hogy még jobban látszódjon a gráf szerkezete, helyettesítsük az 1-est fekete, a 0-t fehér négyzettel. Így a 16. ábrán látható, keresztrejtvényre emlékeztető rajzot kapunk.

 

Ha ezzel az ábrázolási technikával egy olyan Erdős-Rényi-féle véletlen gráfot ábrázolunk, melyben a csúcspárok fele van összekötve, akkor "messziről nézve" az ábra egyenletesen szürkének fog látszani (17. ábra ). De vigyázzunk! Hiszen "messziről" a 18. ábrán bemutatott sakktábla-szerű elrendezés is egyenletesen szürkének látszik, ha nagyon sok sora van. Ha azonban itt a sorokat és oszlopokat átrendezzük úgy, hogy előrehozzuk a párosakat, akkor a 18. ábra jobboldalán látható sokkal szabályosabb, igen egyszerű struktúrát kapjuk. Ezzel szemben egy véletlen gráf ábráját akárhogyan rendeznénk át, mindenképpen egyenletesen szürke volna.

 

Itt az ideje, hogy bemutassuk a 20. századi magyar matematika egyik legnagyobb hatású eredményét, Szemerédi Endre (19. ábra) regularitási lemmáját. A 20. ábra bal felső sarkában látható gráfnak nem látszik különösebb struktúrája. Azonban a csúcsait alkalmasan átrendezve a jobb felső sarokban már azt látjuk, hogy az ábra négy különböző sűrűségű területre oszlik. Ezeken a területeken belül azonban már további struktúra nincs, ezek a részek már véletlenszerűek. A Szemerédi-lemma éppen ezt fogalmazza meg: minden gráf felbontható korlátos számú részre (ezek száma csak a hibahatártól függ, nem függ a gráftól) úgy, hogy a megfelelő kisebb négyzeteken a keresztrejtvény-ábra (kis hibával) véletlenszerű, más-más sűrűséggel. Ha ezeket a sűrűségeket ismerjük, a gráf sok fontos tulajdonságát meg tudjuk mondani.

V. Gigantikus hálózatok folytonos modellje

Végezetül arról ejtek néhány szót, hogyan lehet folytonosnak tekinteni egy kellőképpen nagy hálózatot. Nézzünk először is egy animációt ^|4}| . Ez egy 100 csúcsú gráf létrejöttét mutatja, mely úgy épül fel, hogy minden lépésben egy új csúcs és több új véletlen él születik úgy, hogy az élek sűrűsége állandó marad. Az ábra egyre simább lesz. A 21. ábra 200 csúccsal mutatja be az előbbi módon megkonstruált gráfot. A jobb oldalon pedig az 1-max(x,y) függvénynek egy "szürkeskálás" ábrája látható. A kettő nagyon hasonló! És valóban: megmutatható, hogy ha 200 helyett 1000, 10000, stb. csúcsig mennénk el, a gráf "keresztrejtvény" ábrája egyre jobban hasonlítana a jobboldali "szürkeskálás" ábrához. A jobboldali függvény ismeretében a gráf sok lényeges tulajdonsága és paramétere egyszerű számolással meghatározható. A jobboldali függvény olyan közelítése a baloldali gráfnak, ahogyan a folytonosnak tekintett anyag közelítése a fématomokból álló kristálynak.

Szegedy Balázs fiatal kollégámmal megmutattuk, hogy egy nagyon nagy gráf lényegében mindig megközelíthető egy kétváltozós függvénnyel. Ez adott esetben egyszerűbb lehet, mint más leírás. Akkor hát melyik függvény írja le az internetet? Sajnos, erre a kérdésre a fenti elmélet nem ad értelmes választ, ugyanis sűrű gráfokra alkalmazható. Az internet-szerű hálózatokban sokkal kevesebb él van, egy csúcs csak a többi csúcs egy elenyészően kicsi hányadával van összekötve. Az internetet ily módon az azonosan 0 függvény igen jól megközelíti - ami viszont semmitmondó. Vannak bíztató eredmények az ilyen "ritka" hálózatokra vonatkozólag is, a teljes elméletre azonban még várni kell.