Barabashi-Albert malli

Barabashi-Albert (BA) -malli on algoritmi satunnaisten mittakaavavapaiden verkkojen generoimiseksi käyttämällä etuuskohtelun periaatetta. Mittakaavattomat verkostot ovat yleisiä luonnollisissa verkostoissa (ruokaketjut) ja ihmisen luomissa verkostoissa ( Internet , World Wide Web , lainausverkostot , jotkut sosiaaliset verkostot ).

Käsitteet

Monet tutkittavat verkot kuuluvat mittakaavattomien verkkojen luokkaan. Tämä tarkoittaa, että niillä on potenssilakijakauma solmuasteena, kun taas satunnaiset graafimallit ( Watts-Strogatzja Erdős-Renyi ) ei ole tällaista jakaumaa. Barabasi-Albert-malli on yksi useista ehdotetuista teholakimalleista, jotka luovat skaalautumattomia verkkoja. Se sisältää kaksi tärkeää yleistä käsitettä:

verkon kasvua
Ensisijainen liiteperiaate (PP)

Molemmat käsitteet ovat laajalti edustettuina reaalimaailman verkostoissa. Kasvu tarkoittaa, että verkkosolmujen määrä kasvaa ajan myötä.

Ensisijaisen liittämisen periaate on, että mitä enemmän solmulla on yhteyksiä, sitä edullisemmin se luo uusia yhteyksiä. Solmuilla, joilla on korkein aste, on enemmän mahdollisuuksia ottaa haltuunsa verkkoon lisätyt linkit. Intuitiivisesti etuuskohtelun periaate voidaan ymmärtää, jos ajatellaan sosiaalisia verkostoja, jotka tuovat ihmiset yhteen. Tässä yhteys A:sta B:hen tarkoittaa sitä, että henkilö A "tietää" tai on "tuttu" henkilön B. Vahvasti yhteydessä olevia solmuja edustavat tunnetut ihmiset, joilla on suuri määrä yhteyksiä. Kun uusi tulokas tulee yhteisöön, hänen on parempi ottaa yhteyttä johonkin tunnettuun ihmiseen kuin suhteellisen tuntemattomaan. Samoin World Wide Webissä sivut yhdistetään keskitteisiin, kuten tunnettuihin sivustoihin, kuten Google tai Wikipedia , eikä sivuihin, joita ei tunneta hyvin. Jos linkitettäväksi valitaan satunnaisesti uusi sivu, tietyn sivun valitsemisen todennäköisyys on verrannollinen sen asteeseen. Tämä selittää etuoikeutetun kiinnityksen periaatteen.

Ensisijaisen liittämisen periaate on esimerkki positiivisesta palautteesta, jossa aluksi satunnaiset muunnelmat (yhdessä solmussa on aluksi enemmän linkkejä tai se alkaa kerätä linkkejä aikaisemmin kuin muut) vahvistuvat automaattisesti, mikä lisää aukkoa huomattavasti. Tätä kutsutaan joskus myös Matthew-efektiksi , "rikkaat rikastuvat" tai autokatalyysiksi kemiassa.

Algoritmi

Verkko alkaa alkuverkolla solmuilla. ja kunkin solmun asteen alkuverkossa on oltava vähintään 1, muuten se on aina erotettu muusta verkosta. $m_{0}$ $m_{0}>=2$

Joka ajankohtana verkkoon lisätään uusi solmu. Jokainen uusi solmu muodostaa yhteyden olemassa oleviin solmuihin todennäköisyydellä, joka on verrannollinen näiden solmujen yhteyksien määrään. Muodollisesti todennäköisyys , että uusi solmu muodostaa yhteyden solmuun i, on: [1] $p_{i}$

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

missä on i:nnen solmun aste, ja nimittäjä summaa kaikkien olemassa olevien solmujen asteet. Eniten yhdistetyt solmut ("keskittimet") keräävät yleensä vielä enemmän yhteyksiä, kun taas solmuja, joissa on pieni määrä yhteyksiä, ei todennäköisesti valita liittymään uusiin solmuihin. Uusilla solmuilla on "etuoikeus" muodostaa yhteys eniten kytkettyihin solmuihin. $k_i$

Ominaisuudet

Tehonjako

BA-mallin potenssilakijakauma on skaalaamaton , tarkemmin sanottuna potenssilain mukainen

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

Keskimääräinen polun pituus

Keskimääräinen polun pituus BA-mallissa kasvaa keskimäärin verkon koon logaritmina. Tarkalla muodossa on kaksinkertainen logaritminen korjaus [1] ja se näyttää tältä

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

BA-mallilla on systemaattisesti lyhyempi keskimääräinen polku kuin satunnaisella graafilla.

Solmuastekorrelaatiot

Kytkettyjen solmujen asteiden korrelaatiot kehittyvät BA-mallissa satunnaisesti, johtuen verkon kehityksen erityispiirteistä. Todennäköisyys löytää yhteys asteiden solmujen ja BA-mallissa on esitetty muodossa

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

Tietenkin tulos on erilainen, jos jakauma ei korreloi, . ${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3))$

Klusterikerroin

BA-mallin klusterointikertoimella ei ole vielä analyyttisiä arvoja . Empiirisesti saadut klusterointikertoimet ovat yleensä paljon korkeammat BA-mallissa kuin satunnaisissa verkoissa. Klusterointikerroin riippuu myös verkon koosta likimääräisen teholain mukaan:

C\sim N^{-0.75}.

[yksi]

Tämä käyttäytyminen eroaa edelleen pienten verkkojen käyttäytymisestä, joissa klusterointi ei riipu verkon koosta. Hierarkkisten verkkojen tapauksessa klusterointi solmuasteen funktiona noudattaa myös teholakia:

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

Nämä tulokset saivat analyyttisesti Dorogovtsev, Goltsev ja Mendes. [3]

Spektrilaadut

BA-mallin spektritiheyden muoto eroaa satunnaisgraafin puoliympyrän muotoisesta spektritiheydestä. Sillä on kolmion muotoinen kärki, joka on paljon korkeammalla kuin puoliympyrä, ja reunat pienenevät potenssilain mukaan.

Rajatapaukset

Malli A

Malli A säilyttää kasvun, mutta se ei sisällä etuuskohtelun periaatetta. Todennäköisyys liittyä uusi solmu olemassa oleviin solmuihin on sama kaikkialla. Äärillinen astejakauma tässä tapauksessa viittaa siihen, että pelkkä kasvu ei riitä skaalattoman rakenteen saavuttamiseen.

Malli B

Malli B säilyttää etuuskohtelun periaatteen, mutta sulkee pois kasvun. Malli alkaa kiinteällä määrällä katkaistuja solmuja ja lisää linkkejä, edullisesti valitsemalla korkean asteen solmut kohteiksi. Vaikka tehojakauma näyttää olevan skaalaamaton simulaation alussa, se on epävakaa ja tulee lopulta lähelle Gaussia, kun verkko lähestyy kylläisyyttä. Näin ollen PP:n periaate ei yksinään riitä luomaan mittakaavattoman rakenteen. [yksi]

Mallien A ja B epäonnistuminen mittakaavattoman jakauman saavuttamisessa viittaa siihen, että kasvu ja PP ovat yhtä tärkeitä toistamaan todellisen maailman verkoissa havaittu stationäärinen teholakijakautuma.

Historia

Ensisijaisen liittämisen periaatetta käytettiin ensimmäisen kerran selittämään Yulen teholain jakaumaa vuonna 1925 [4] , vaikka Yulen matemaattista analyysiä pidetään nykyaikaisten standardien mukaan epäselvänä, koska satunnaisten prosessien analysointiin ei ole sopivia työkaluja. Nykyaikaista kineettisen perusyhtälön menetelmää, joka antaa avoimemman johtopäätöksen, sovelsi ongelmaan Herbert Simon vuonna 1955 [5] tutkiessaan kaupunkien kokoa ja muita ilmiöitä. Derek de Solla Price sovelsi sitä ensimmäisen kerran verkoston kasvattamiseen vuonna 1976, [6] joka oli kiinnostunut tieteellisten julkaisujen välisistä viittausverkostoista. Nimi "preferred interconnection" ja skaalautumattomien verkkomallien nykyinen suosio johtuu Albert-Laszlo Barabasin ja Reki Albertin työstä., joka löysi prosessin itsenäisesti vuonna 1999 ja sovelsi sitä valtalain jakeluun World Wide Webissä. [2]

Muistiinpanot

↑ 1 2 3 4 Albert, Reka; R. Albert; A.L. Barabasi. Monimutkaisten verkkojen tilastollinen mekaniikka (englanniksi) // Reviews of Modern Physics : Journal. - 2002. - Voi. 74 . - s. 47-97 . - doi : 10.1103/RevModPhys.74.47 . - . Arkistoitu alkuperäisestä 24. elokuuta 2015.
↑ 1 2 Albert-László Barabási & Reka Albert Skaalauksen syntyminen satunnaisissa verkoissa (englanniksi) // Science : Journal. - 1999. - lokakuu ( nide 286 , nro 5439 ). - s. 509-512 . - doi : 10.1126/tiede.286.5439.509 . Arkistoitu alkuperäisestä 17. huhtikuuta 2012.
↑ SN Dorogovtsev, AV Goltsev ja JFF Mendes, e-print cond-mat/0112143.
↑ Yule, G. Udny . Matemaattinen evoluutioteoria, joka perustuu Dr. JC Willis, FRS // Royal Statistical Societyn lehti : päiväkirja. - 1925. - Voi. 88 , no. 3 . - s. 433-436 . - doi : 10.2307/2341419 . — .
↑ Herbert A. Simon . On a Class of Skew Distribution Functions (englanniksi) // Biometrika : Journal. - 1955. - Joulukuu ( osa 42 , nro 3-4 ). - s. 425-440 . - doi : 10.1093/biomet/42.3-4.425 .
↑ DJ de Solla Price . Yleinen teoria bibliometrisista ja muista kumulatiivisista hyötyprosesseista (englanniksi) // Journal of the American Society for Information Science : päiväkirja. - 1976. - Voi. 27 . - s. 292-306 . - doi : 10.1002/asi.4630270505 .

Linkit

Monimutkaiset verkot