Lovász László

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

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.

4. ábra

5. ábra

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.

6. ábra

7. ábra

8. ábra

³⁰statisztikus fizika

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.