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.
thumb|300px|A növekedés lépései a Barabási–Albert-modell szerint. Itt csak az első lépés látható, a többi lépést az animált változat mutatja.
A modell A modellben egy irányítatlan hálózatot hozunk létre.
Kezdetben van egy pontosabban nem definiált m0 (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 élt „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 thumb|A fokszámeloszlás a Barabási–Albert-modellben hatványfüggvényt követ (negatív kitevővel). A hatványfüggvényt kétszer logaritmikus skálán ábrázolva egyenest kapunk.
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
Jegyzetek
További információk BarabásiLab. Rejtett mintázatok. A hálózati gondolkodás nyelve; szerk. Alanna Stang; Open Books, Bp., 2021 BarabásiLab: Élek mentén. Kortárs magyar képzőművészet az adatok tükrében; szerk. Bérczi Linda, Üveges Krisztina; Együtt a Művészetért Egyesület, Bp., 2021
Kategória:Gráfalgoritmusok