Barabashi-Albert Model

Barabashi-Albert (BA) modellen er en algoritme til at generere tilfældige skalafri netværk ved hjælp af princippet om præferencetilknytning. Skalafri netværk er udbredt i naturlige netværk (fødekæder) og menneskeskabte netværk ( Internet , World Wide Web , citationsnetværk , nogle sociale netværk ).

Begreber

Mange netværk under undersøgelse falder ind under klassen af skalafri netværk. Det betyder, at de har en magtlovfordeling i nodegrad, mens tilfældige grafmodeller ( Watts-Strogatzog Erdős-Renyi ) ikke har en sådan fordeling. Barabasi-Albert-modellen er en af flere foreslåede magtlovsmodeller, der genererer skalafrie netværk. Den indeholder to vigtige generelle begreber:

netværksvækst
Preferred Attachment Principle (PP)

Begge koncepter er bredt repræsenteret i den virkelige verdens netværk. Vækst betyder, at antallet af netværksknuder stiger over tid.

Princippet for præferencetilknytning er, at jo flere forbindelser en node har, jo mere foretrækkes det, at den skaber nye forbindelser. Noderne med den højeste grad har flere muligheder for at overtage de links, der er tilføjet netværket. Intuitivt kan princippet om præferencetilknytning forstås, hvis vi tænker i sociale netværk, der bringer mennesker sammen. Her betyder en forbindelse fra A til B, at person A "kender" eller er "bekendt" med person B. Stærkt forbundne noder er repræsenteret af kendte personer med et stort antal forbindelser. Når en tilflytter kommer ind i fællesskabet, er det mere at foretrække for ham/hende at kontakte en af de kendte personer end en forholdsvis ukendt. Tilsvarende er sider på World Wide Web forbundet med hubs, såsom velkendte websteder som Google eller Wikipedia , snarere end med sider, der ikke er velkendte. Hvis en ny side er tilfældigt udvalgt til at linke, så vil sandsynligheden for at vælge en bestemt side være proportional med dens grad. Dette forklarer princippet om præferencetilknytning.

Princippet om præferencetilknytning er et eksempel på positiv feedback, hvor indledningsvis tilfældige variationer (én node har i starten flere links eller begynder at indsamle links tidligere end andre) automatisk forstærkes, og derved øges gapet kraftigt. Dette kaldes også nogle gange for Matthew-effekten , "de rige bliver rigere", eller autokatalyse i kemi.

Algoritme

Netværket starter med et indledende mesh med noder. og graden af hver node i det indledende netværk skal være mindst 1, ellers vil den altid være adskilt fra resten af netværket. $m_{0}$ $m_{0}>=2$

På hvert tidspunkt tilføjes en ny node til netværket. Hver ny knude forbindes til eksisterende knudepunkter med en sandsynlighed, der er proportional med antallet af forbindelser for disse knudepunkter. Formelt set er sandsynligheden for , at en ny node forbinder til node i: [1] $p_{i}$

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

hvor er graden af den i-te node, og nævneren opsummerer graderne af alle eksisterende noder. De mest forbundne noder ("hubs") har en tendens til at akkumulere endnu flere forbindelser, mens noder med et lille antal forbindelser sandsynligvis ikke vil blive valgt til at slutte sig til nye noder. Nye noder har en "præference" til at forbinde med de mest forbundne noder. $k_i$

Egenskaber

Strømfordeling

Magtlovfordelingen i BA-modellen er skalafri, mere præcist overholder den magtloven

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

Gennemsnitlig vejlængde

Den gennemsnitlige vejlængde i BA-modellen stiger i gennemsnit som logaritmen af netværksstørrelsen. Den nøjagtige form har en dobbelt logaritmisk korrektion [1] og ser ud

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

BA-modellen har en systematisk kortere gennemsnitsvej end en tilfældig graf.

Knudegradskorrelationer

Korrelationer af grader af forbundne noder udvikler sig tilfældigt i BA-modellen på grund af de særlige forhold ved netværksudvikling. Sandsynligheden for at finde sammenhæng mellem noder med grader og i BA-modellen præsenteres som

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)}}.

Selvfølgelig vil resultatet være anderledes, hvis fordelingen var ukorreleret, . ${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3))$

Klyngningskoefficient

Der er endnu ingen analytiske værdier af klyngekoefficienten for BA-modellen. Empirisk opnåede klyngekoefficienter er generelt meget højere for BA-modellen end for tilfældige netværk. Klyngekoefficienten afhænger også af netværkets størrelse i henhold til en omtrentlig effektlov:

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

[en]

Denne adfærd er stadig forskellig fra adfærden for små netværk, hvor klyngedannelse ikke afhænger af netværkets størrelse. I tilfælde af hierarkiske netværk adlyder klyngedannelse som funktion af nodegrad også en magtlov:

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

Disse resultater blev analytisk opnået af Dorogovtsev, Goltsev og Mendes. [3]

Spektralkvaliteter

Formen af BA-modellens spektraltæthed adskiller sig fra den halvcirkelformede spektraltæthed af en tilfældig graf. Den har en trekantet form med et toppunkt, der ligger meget højere end en halvcirkel, og kanterne aftager ifølge en magtlov.

Begræns tilfælde

Model A

Model A bevarer vækst, men omfatter ikke princippet om præferencetilknytning. Sandsynligheden for at forbinde en ny node med eksisterende er den samme overalt. Den endelige gradsfordeling antyder i dette tilfælde, at vækst alene ikke er tilstrækkelig til at opnå en skalafri struktur.

Model B

Model B bevarer princippet om præferencetilknytning, men udelukker vækst. Modellen starter med et fast antal afbrudte noder og tilføjer links, fortrinsvis ved at vælge højgradsknuder som destinationer. Selvom strømfordelingen ser ud til at være skalafri i begyndelsen af simuleringen, er den ustabil og bliver til sidst tæt på Gauss, når netværket nærmer sig mætning. Princippet om PP i sig selv er således ikke tilstrækkeligt til at skabe en skalafri struktur. [en]

Manglen på model A og B for at opnå en skalafri fordeling antyder, at vækst og PP er lige så nødvendige for at reproducere den stationære kraftlovfordeling set i den virkelige verdens netværk.

Historie

Princippet om præferencetilknytning blev først brugt til at forklare Yules magtlovfordeling i 1925 [4] selvom Yules matematiske analyse anses for at være uklar efter moderne standarder på grund af manglen på passende værktøjer til at analysere tilfældige processer. Den moderne metode med den grundlæggende kinetiske ligning, som giver en mere gennemsigtig konklusion, blev anvendt på problemet af Herbert Simon i 1955 [5] i løbet af studiet af størrelsen af byer og andre fænomener. Det blev første gang anvendt på netværksvækst af Derek de Solla Price i 1976, [6] som var interesseret i citationsnetværk mellem videnskabelige publikationer. Navnet "foretrukken sammenkobling" og den nuværende popularitet af skalafri netværksmodeller skyldes arbejdet fra Albert-Laszlo Barabasi og Reki Albert, som uafhængigt opdagede processen i 1999 og anvendte den til magtlovfordelingen på World Wide Web. [2]

Noter

↑ 1 2 3 4 Albert, Reka; R. Albert; A.L. Barabasi. Statistisk mekanik af komplekse netværk (engelsk) // Reviews of Modern Physics : journal. - 2002. - Bd. 74 . - S. 47-97 . - doi : 10.1103/RevModPhys.74.47 . - . Arkiveret fra originalen den 24. august 2015.
↑ 1 2 Albert-László Barabási & Reka Albert Emergence of scaling in random networks (engelsk) // Science : journal. - 1999. - Oktober ( bind 286 , nr. 5439 ). - S. 509-512 . - doi : 10.1126/science.286.5439.509 . Arkiveret fra originalen den 17. april 2012.
↑ SN Dorogovtsev, AV Goltsev og JFF Mendes, e-print cond-mat/0112143.
↑ Yule, G. Udny . En matematisk evolutionsteori baseret på konklusionerne fra Dr. JC Willis, FRS // Journal of the Royal Statistical Society : journal. - 1925. - Bd. 88 , nr. 3 . - S. 433-436 . - doi : 10.2307/2341419 . — .
↑ Herbert A. Simon . On a Class of Skew Distribution Functions (engelsk) // Biometrika : journal. - 1955. - December ( bind 42 , nr. 3-4 ). - S. 425-440 . - doi : 10.1093/biomet/42.3-4.425 .
↑ DJ de Solla Price . En generel teori om bibliometriske og andre kumulative fordelsprocesser (engelsk) // Journal of the American Society for Information Science : journal. - 1976. - Bd. 27 . - S. 292-306 . - doi : 10.1002/asi.4630270505 .