Lovász László

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

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

9. ábra

animáción

10. ábra

animációban

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.

11. ábra

12. ábra

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 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.

13. ábra

14. ábra