„Barabási–Albert-modell” változatai közötti eltérés

[ellenőrzött változat]

[nem ellenőrzött változat]

← Régebbi szerkesztés Újabb szerkesztés →

Tartalom törölve Tartalom hozzáadva

Sorban

A lap 2012. november 13., 19:24-kori változata

A Barabási–Albert-modell a komplex hálózatok (gráfok) fejlődésének egy modellje, mely magyarázattal szolgál azok gyakori skálafüggetlen tulajdonságára, azaz arra, hogy a fokszámeloszlásuk gyakran negatív kitevőjű hatványfüggvény szerint cseng le. A modellt Barabási Albert-László és tanítványa Albert Réka dolgozta ki 1999-ben, miután a webet, a hivatkozásokkal (linkekkel) mint irányítatlan élekkel vizsgálva skálafüggetlennek találták.

A modell

A modellben egy irányítatlan hálózatot hozunk létre.^[1]

Kezdetben van egy pontosabban nem definiált m₀ (legalább kettő) csomópontú hálózat, amelyben minden csúcshoz legalább egy él vezet.

Minden egyes lépésben egy újabb csúcsot adunk hozzá, melyet egy-egy éllel kapcsolunk m véletlenszerűen választott régi csúcshoz úgy, hogy a kiválasztás valószínűsége arányos a régi csúcsok pillanatnyi fokszámával. Azt, hogy a nagyobb fokszámú csúcs nagyobb eséllyel kap új élt, preferenciális kapcsolódásnak hívják.

Kiemelendő még egyszer a modell két fontos eleme, melyek egyike sem képes egyedül magyarázatot adni a skálafüggetlenségre:

Növekedés: A modell egy folyamatosan növekvő hálózatot hoz létre, szemben például az Erdős Pál és Rényi Alfréd által tanulmányozott véletlen gráfokkal, ahol „rögtön” az elején létezik az összes csúcs.
Preferenciális kapcsolódás: A folyamat során a nagyobb fokszámú csúcsok (amelyhez több él fut) nagyobb valószínűséggel kapnak új éleket. Ez segíti ahhoz a hálózatot, hogy néhány csomópontja rengeteg élet „begyűjthessen” ezzel csomóponttá válva. A legtöbb csúcsnak pedig csupán néhány kapcsolata (kis fokszáma) lesz.

A modellben keletkezett hálózat tulajdonságai

Fokszámeloszlás

Sok lépés után, ha a csúcsok száma jóval nagyobb a kezdeti hálózaténál, a fokszámeloszlás fordítottan arányos a fokszám köbével (azaz a mínusz harmadik hatványával arányos), tehát hatványfüggvény eloszlást követ. A pontos formula szerint a hálózatban annak a valószínűsége, hogy a fokszám k

P(k)={\frac {2m_{0}}{k^{3}}}

Hivatkozások

↑ ^a ^b (2002) „Statistical mechanics of complex networks”. Reviews of Modern Physics 74, 47-97. o.

[RMP-1] (2002) „Statistical mechanics of complex networks”. Reviews of Modern Physics 74, 47-97. o.

[1]

@@ 18. sor: / 18. sor: @@
 Kezdetben van egy pontosabban nem definiált ''m<sub>0</sub>'' (legalább kettő) csomópontú hálózat, amelyben minden csúcshoz legalább egy él vezet.
-Minden egyes lépésben egy újabb csúcsot adok hozzá, melyek a régi élekhez ''m'' éllel kapcsolódik úgy, hogy a kapcsolódás valószínűsége arányos azok pillanatnyi fokszámával. Ezt – hogy a nagyobb fokszámú nagyobb eséllyel kap új élt – hívják preferenciális kapcsolódásnak.
+Minden egyes lépésben egy újabb csúcsot adunk hozzá, melyet egy-egy éllel kapcsolunk ''m'' véletlenszerűen választott régi csúcshoz úgy, hogy a kiválasztás valószínűsége arányos a régi csúcsok pillanatnyi fokszámával. Azt, hogy a nagyobb fokszámú csúcs nagyobb eséllyel kap új élt, preferenciális kapcsolódásnak hívják.
-Kiemelnénk még egyszer a modell két fontos elemét, melyek egyike sem képes egyedül magyarázatot adni a skálafüggetlenségre:
+Kiemelendő még egyszer a modell két fontos eleme, melyek egyike sem képes egyedül magyarázatot adni a skálafüggetlenségre:
-# ''Növekedés'': A modell egy folyamatosan növekvő hálózatot hoz létre. szemben például az [[Erdős Pál]] és [[Rényi Alfréd]] által tanulmányozott [[véletlen gráf]]okkal, ahol „rögtön” az elején létezik az összes csúcs.
+# ''Növekedés'': A modell egy folyamatosan növekvő hálózatot hoz létre, szemben például az [[Erdős Pál]] és [[Rényi Alfréd]] által tanulmányozott [[véletlen gráf]]okkal, ahol „rögtön” az elején létezik az összes csúcs.
 # ''Preferenciális kapcsolódás'': A folyamat során a nagyobb fokszámú csúcsok (amelyhez több él fut) nagyobb valószínűséggel kapnak új éleket. Ez segíti ahhoz a hálózatot, hogy néhány csomópontja rengeteg élet „begyűjthessen” ezzel csomóponttá válva. A legtöbb csúcsnak pedig csupán néhány kapcsolata (kis fokszáma) lesz.