Skálafüggetlen hálózat

Egy komplex hálózat skálafüggetlen, ha benne a fokszámeloszlás hatványfüggvényt (Yule–Simon eloszlást) követ:

$\mathbf {P(k)\sim k^{-\gamma }} ,$

Az ilyen hálózatoknak viszonylag sok nagy fokszámú csomópontjuk van, és a csomópontok fokszámeloszlása méretfüggetlen (formálisabban ha x egy véletlenül választott csúcs fokszáma, akkor a P(x>n) és P(x>n|x>m) eloszlások csak egy konstans szorzóban különböznek).

Egy másik, nem egyenértékű definíció az, hogyha az összekötött csúcsok fokszámainak szorzatát összegzem, nagy értéket kapok, azaz ha E a gráf éleinek halmaza, akkor

$\sum _{(i,j)\in E}d_{i}d_{j}$

az azonos fokszámeloszlású gráfok között közel maximális. Ez azt jelenti, hogy a nagy fokszámú csúcsok jellemzően össze vannak kötve egymással.

Kialakulás

Skálafüggetlen gráfok kialakulásának egyik lehetséges módja a preferenciális kapcsolódás. Ez azt jelenti, hogy egy növekvő gráfban annak a valószínűsége, hogy az új csúcs csatlakozzon egy régivel, arányos a régi csúcs fokszámával. Az ilyen módon nyerhető hálózatok csak egy alosztályát alkotják a skálafüggetlen hálózatoknak.

Tulajdonságok

A skálafüggetlen gráfok kis-világ tulajdonságúak. A klaszterezettség egy hatványfüggvény fordítottja szerint arányos bennük a fokszámmal (vagyis a kis fokszámú pontok sűrű részhálókat alkotnak, és ezeket a részhálókat nagy fokszámú csomópontok kapcsolják össze).

A skálafüggetlen rendszerek rendkívül hibatűrőek a véletlen hibákkal szemben, azaz rendkívül sok véletlenül választott pontot eltávolítható úgy, hogy a rendszer továbbra is összefüggő marad. Másfelől viszont nagyon sérülékenyek a célzott támadásokkal szemben, viszonylag kevés csúcsot eltávolítva a legnagyobb csomópontok közül a hálózat azonban darabjaira hull.

Alkalmazás

A skálafüggetlenség jelentőségét az adja, hogy számos, fontos gyakorlati szerepet játszó hálózatról kimutatták, hogy ilyen tulajdonságú; például a különféle szociális hálókról, az Internetről, a World Wide Webről, az idegsejtek alkotta hálózatokról, a járványok terjedési útvonalairól vagy a sejtek reakcióútjairól.

Kritika

A skálafüggetlen hálózatok elméletével szembeni egyik kritika, hogy összemosódnak a matematikai modellekből levezetett, és a valódi skálafüggetlen (vagy annak vélt) hálózatokban tapasztalt jellemzők; az elmélet használói gyakran nem teszik egyértelművé, hogy mely tulajdonságokat tekintenek a skálafüggetlenség definíciója részének, mik azok, amik következnek (vagy nagy valószínűséggel következnek) a definícióból, és mik azok, amik esetlegesek.

Története

A skálafüggetlenség és a preferenciális kapcsolódás felfedezése Barabási Albert László és munkatársai nevéhez fűződik, akik 1999-ben a Notre Dame Egyetemen a honlapok közötti linkek hálózatát tanulmányozták. Barabási és munkatársa Albert Réka kidolgozott egy olyan modellt, amely skálafüggetlen hálózatot hoz létre, a Barabási–Albert-modellt.

Irodalom

• Barabási, Albert-László and Albert, Réka. "Emergence of scaling in random networks". Science, 286:509-512, October 15, 1999.
• Lun Li, David Alderson, Reiko Tanaka, John C. Doyle, Walter Willinger: Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications, 2005
• Mark Newman, Albert-László Barabási, Duncan J. Watts: The Structure and Dynamics of Networks, Princeton University Press, 2006 (Benne: Error end attack tolerance of complex networks)