Barabashi-Albert modell

A Barabashi-Albert (BA) modell véletlenszerű skálamentes hálózatok generálására szolgáló algoritmus a preferenciális csatolás elvén. A skálamentes hálózatok széles körben elterjedtek a természetes hálózatokban (élelmiszerláncok) és az ember által létrehozott hálózatokban ( Internet , World Wide Web , hivatkozási hálózatok , egyes közösségi hálózatok ).

Fogalmak

Sok vizsgált hálózat a skálamentes hálózatok osztályába tartozik. Ez azt jelenti, hogy hatványtörvény-eloszlásuk van csomóponti fokban, míg véletlenszerű gráfmodellek ( Watts-Strogatzés Erdős-Renyi ) nem rendelkezik ilyen eloszlással. A Barabasi-Albert modell egyike azon számos javasolt hatványtörvény-modellnek, amelyek skálamentes hálózatokat generálnak. Két fontos általános fogalmat tartalmaz:

hálózat növekedése
Preferált csatolási elv (PP)

Mindkét fogalom széles körben képviselteti magát a valós világ hálózataiban. A növekedés azt jelenti, hogy a hálózati csomópontok száma idővel növekszik.

A preferenciális csatolás elve az, hogy minél több kapcsolata van egy csomópontnak, annál előnyösebb, ha új kapcsolatokat hoz létre. A legmagasabb fokozattal rendelkező csomópontoknak több lehetőségük van a hálózathoz hozzáadott hivatkozások átvételére. Intuitív módon a preferenciális kötődés elve érthető, ha olyan közösségi hálózatokban gondolkodunk, amelyek összehozzák az embereket. Itt az A-tól B-ig tartó kapcsolat azt jelenti, hogy A személy "ismeri" vagy "ismeri" B személyt. Az erősen kapcsolódó csomópontokat jól ismert emberek képviselik nagyszámú kapcsolattal. Amikor egy újonc belép a közösségbe, jobb, ha felveszi a kapcsolatot egy ismert emberrel, mint egy viszonylag ismeretlennel. Hasonlóképpen, a világhálón az oldalak csomópontokhoz, például jól ismert webhelyekhez, például a Google -hoz vagy a Wikipédiahoz vannak társítva , nem pedig a nem jól ismert oldalakhoz. Ha egy új oldalt véletlenszerűen választunk ki hivatkozásra, akkor egy adott oldal kiválasztásának valószínűsége arányos annak mértékével. Ez magyarázza a kedvezményes kötődés elvét.

A preferenciális csatolás elve egy példa a pozitív visszacsatolásra, ahol kezdetben a véletlenszerű variációk (egy csomópontnak kezdetben több linkje van, vagy korábban kezdi el gyűjteni a hivatkozásokat, mint a többi) automatikusan felerősödik, ezzel nagymértékben növelve a különbséget. Ezt néha Máté-effektusnak is nevezik , "a gazdagok gazdagabbak lesznek" vagy autokatalízisnek a kémiában.

Algoritmus

A hálózat egy kezdeti hálóval kezdődik csomópontokkal. és a kezdeti hálózat minden csomópontjának fokszámának legalább 1-nek kell lennie, különben mindig el lesz választva a hálózat többi részétől. $m_{0}$ $m_{0}>=2$

Minden egyes időpontban egy új csomópont kerül a hálózatba. Minden új csomópont olyan valószínűséggel csatlakozik a meglévő csomópontokhoz, amelyek arányosak ezen csomópontok kapcsolatainak számával. Formálisan annak a valószínűsége , hogy egy új csomópont csatlakozik az i csomóponthoz: [1] $p_{i}$

p_{i}={k_{i} \over \sum _{j}k_{j))

ahol az i-edik csomópont foka, a nevező pedig az összes létező csomópont fokát összegzi. A leginkább összekapcsolt csomópontok ("hubok") általában még több kapcsolatot halmoznak fel, míg a kevés kapcsolattal rendelkező csomópontokat nem valószínű, hogy kiválasztják az új csomópontokhoz. Az új csomópontoknak "preferenciája" van a leginkább csatlakoztatott csomópontokhoz való csatlakozáshoz. $k_i$

Tulajdonságok

Áramelosztás

A BA modellben a hatványtörvény eloszlás skálamentes, pontosabban betartja a hatványtörvényt

{\displaystyle P\left(k\right)\sim k^{-3))

Átlagos úthossz

Az átlagos úthossz a BA modellben átlagosan a hálózat méretének logaritmusával nő. A pontos forma kettős logaritmikus korrekcióval rendelkezik [1] , és így néz ki

\ell \sim {\frac {\ln N}{\ln \ln N)).

A BA modellnek szisztematikusan rövidebb átlagos útja van, mint egy véletlen gráfnak.

Csomófokú korrelációk

A BA modellben a hálózatfejlesztés sajátosságaiból adódóan véletlenszerűen alakulnak ki az összekapcsolt csomópontok fokszámainak korrelációi. A fokszámú csomópontok közötti kapcsolat megtalálásának valószínűségét a BA modellben a következőképpen mutatjuk be

n_{k\ell }={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+ \ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right) \left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.

Természetesen az eredmény más lesz, ha az eloszlás nem korrelált, . ${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3))$

Klaszterezési együttható

A BA-modell klaszterezési együtthatójának még nincsenek analitikai értékei . Az empirikusan kapott klaszterezési együtthatók általában sokkal magasabbak a BA modellnél, mint a véletlenszerű hálózatoknál. A klaszterezési együttható a hálózat méretétől is függ egy közelítő hatványtörvény szerint:

C\sim N^{-0,75}.

[egy]

Ez a viselkedés még mindig eltér a kis hálózatok viselkedésétől, ahol a klaszterezés nem függ a hálózat méretétől. Hierarchikus hálózatok esetén a csomóponti fok függvényében a klaszterezés is betart egy hatványtörvényt:

C(k)=k^{-1}.

Ezeket az eredményeket analitikusan Dorogovtsev, Goltsev és Mendes szerezte meg. [3]

Spektrális minőségek

A BA modell spektrális sűrűségének alakja eltér egy véletlen gráf félkör alakú spektrális sűrűségétől. Háromszög alakú, csúcsa jóval magasabb, mint egy félkör, és az élek egy hatványtörvény szerint csökkennek.

Limit esetek

A modell

Az A modell megtartja a növekedést, de nem tartalmazza a preferenciális kötődés elvét. Egy új csomópont meglévőhöz való csatlakozásának valószínűsége mindenhol azonos. A véges fokeloszlás ebben az esetben arra utal, hogy a növekedés önmagában nem elegendő a skálamentes szerkezet eléréséhez.

B modell

A B modell megtartja a preferenciális kötődés elvét, de kizárja a növekedést. A modell fix számú leválasztott csomóponttal indul, és hivatkozásokat ad hozzá, lehetőleg magas fokú csomópontokat választva célként. Bár a teljesítményeloszlás a szimuláció elején skálamentesnek tűnik, instabil, és végül a Gauss-féle közelébe kerül, ahogy a hálózat közeledik a telítettséghez. Így a PP elve önmagában nem elegendő egy skálamentes szerkezet létrehozásához. [egy]

Az A és B modellek kudarca skálamentes eloszlás elérésében azt sugallja, hogy a növekedés és a PP egyformán szükséges a valós hálózatokban látható stacionárius hatványeloszlás reprodukálásához.

Történelem

A preferenciális kötődés elvét először 1925 -ben használták Yule hatványtörvény-eloszlásának magyarázatára [4] , bár Yule matematikai elemzését a modern szabványok homályosnak tartják, mivel nincsenek megfelelő eszközök a véletlenszerű folyamatok elemzésére. A kinetikai alapegyenlet modern, átláthatóbb következtetést adó módszerét Herbert Simon alkalmazta a problémára 1955-ben [5] a városok méretének és egyéb jelenségeknek a tanulmányozása során. Derek de Solla Price alkalmazta először 1976-ban a hálózatok bővítésére, [6] akit a tudományos publikációk közötti hivatkozási hálózatok érdekeltek. A "preferált összekapcsolás" elnevezés és a méretarányos hálózati modellek jelenlegi népszerűsége Barabási Albert-László és Reki Albert munkásságának köszönhető., aki 1999-ben önállóan fedezte fel a folyamatot, és alkalmazta a világhálón a hatalomtörvény eloszlására. [2]

Jegyzetek

↑ 1 2 3 4 Albert Réka; R. Albert; A.L. Barabasi. Összetett hálózatok statisztikai mechanikája (angol) // Reviews of Modern Physics : folyóirat. - 2002. - 20. évf. 74 . - P. 47-97 . - doi : 10.1103/RevModPhys.74.47 . - Iránykód . Archiválva az eredetiből 2015. augusztus 24-én.
↑ 1 2 Albert-László Barabási & Reka Albert Scaling megjelenése véletlenszerű hálózatokban (angol) // Science : Journal. - 1999. - október ( 286. évf. , 5439. sz.). - P. 509-512 . - doi : 10.1126/tudomány.286.5439.509 . Archiválva az eredetiből 2012. április 17-én.
↑ SN Dorogovtsev, AV Goltsev és JFF Mendes, e-print cond-mat/0112143.
↑ Yule, G. Udny . Az evolúció matematikai elmélete Dr. JC Willis, FRS // A Királyi Statisztikai Társaság folyóirata : folyóirat. - 1925. - 1. évf. 88 , sz. 3 . - P. 433-436 . - doi : 10.2307/2341419 . — .
↑ Herbert A. Simon . On a Class of Skew Distribution Functions (angol) // Biometrika : Journal. - 1955. - december ( 42. évf. , 3-4. sz. ). - P. 425-440 . - doi : 10.1093/biomet/42.3-4.425 .
↑ DJ de Solla Price . A bibliometriai és egyéb kumulatív előnyfolyamatok általános elmélete (angol) // Journal of the American Society for Information Science : folyóirat. - 1976. - 1. évf. 27 . - P. 292-306 . - doi : 10.1002/asi.4630270505 .

Linkek

Összetett hálózatok