Lovász László

Hova nőnek a nagy hálózatok?

Vajon milyen matematikai eszközökkel lehet leírni, megérteni és elemezni egy olyan nagy hálózatot, amelynek még a pontos szerkezetét sem tudjuk megadni? Gondoljunk az internetre, az emberi agyra, vagy pl. az emberek közötti ismeretségek hálózatára! Lehetséges-e egy ilyen hatalmas hálózatot egy sokkal kisebbel modellezni, a nagy hálózathoz hasonlót generálni valamilyen egyszerű véletlenszerű folyamattal? Vagy esetleg célszerűbb egy ilyen nagy hálózatot folytonos közegként elképzelni, ahogy az atomokból felépülő anyagot makroszkópikusan kezeljük?

I. Bevezető a gráfokról
Mi a gráf és mire jó? Mi a fokszám? A rövid bevezetőből alapfogalmak tisztázása után az is kiderül, hogy mikor lehet egy gráfot egyetlen vonallal úgy lerajzolni, hogy minden élen pontosan egyszer haladunk át.

II. Nagyon nagy gráfok
Az internet mellett sok más nagy hálózat van, amit szeretnénk megérteni. Ilyenek például a társadalmi hálózatok: ismeretségek gráfja, rokonságok gráfja, stb. Más jellegű nagyon nagy hálózatok az integrált áramkörök, melyek akár százmilliónyi elemből is állhatnak. Talán mind között a legizgalmasabb az emberi agy a maga százmilliárdnyi csúcsú gráfjával, csak sajnos keveset tudunk róla gráfelméleti szempontból. Hatalmas méretű hálózatokat alkotnak az ökológiai rendszerek, vagy egy kristály atomjai.

III. Véletlen gráfok és a sznobizmus
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. De vajon milyen módszerrel építsük fel azt a véletlen gráfot, amellyel az internetet akarjuk modellezni? És mi köze van az internet gráfjának a sznobizmushoz? A válaszhoz egy gondolatkísérlet segít majd bennünket, amely során különböző urnákba golyókat ejtünk...

IV. A Szemerédi-féle regularitási lemma
Hogyan tudnánk a nagyon nagy gráfok szerkezetét megérteni, kevés adattal leírni? Ehhez először egy új ábrázolásmóddal ismerkedünk meg, amely segítségével a gráfokat "messziről" fogjuk nézni. Majd megfogalmazzuk a 20. századi magyar matematika egyik legnagyobb hatású eredményét, a Szemerédi-féle regularitási lemmát, amely szerint minden nagy gráf felbontható korlátos számú részre úgy, hogy a részek lényegében véletlenszerűnek tekinthetők.

V. Gigantikus hálózatok folytonos modellje
Hogyan lehet folytonosnak tekinteni egy kellőképpen nagy hálózatot? 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. Épp úgy, ahogyan a gigantikus számú fématomból álló kristály is közelíthető folytonosnak tekintett anyag modellel. Akkor hát melyik függvény írja le az internetet?

Tovább