Watts-Strogatz modell

Watts–Strogatz liten världsmodell genererad av igraph och visualiserad av Cytoscape 2.5. 100 noder.

Watts –Strogatz-modellen är en slumpmässig grafgenereringsmodell som producerar grafer med små världsegenskaper, inklusive korta genomsnittliga väglängder och hög klustring . Det föreslogs av Duncan J. Watts och Steven Strogatz i deras artikel publicerad 1998 i Nature scientific journal. Modellen blev också känd som (Watts) betamodellen efter att Watts använde $\beta$ för att formulera den i sin populärvetenskapliga bok Six Degrees .

Motiv för modellen

Den formella studien av slumpmässiga grafer går tillbaka till Paul Erdős och Alfréd Rényis arbete . Graferna de ansåg, nu kända som de klassiska eller Erdős–Rényi (ER) graferna, erbjuder en enkel och kraftfull modell med många tillämpningar.

Emellertid har ER- graferna inte två viktiga egenskaper som observeras i många verkliga nätverk:

De genererar inte lokala kluster och triadiska stängningar . Istället, eftersom de har en konstant, slumpmässig och oberoende sannolikhet att två noder är sammankopplade, har ER-grafer en låg klusteringskoefficient .
De står inte för bildandet av nav. Formellt gradfördelningen av ER-grafer till en Poisson-fördelning snarare än en kraftlag som observeras i många verkliga, skalfria nätverk .

Watts och Strogatz-modellen designades som den enklaste möjliga modellen som tar itu med den första av de två begränsningarna. Den står för klustring samtidigt som den behåller de korta genomsnittliga väglängderna för ER-modellen. Den gör det genom att interpolera mellan en randomiserad struktur nära ER-grafer och ett vanligt ringgitter . Följaktligen kan modellen åtminstone delvis förklara fenomenen "den lilla världen" i en mängd olika nätverk, såsom elnätet, C. elegans neurala nätverk , nätverk av filmskådespelare eller kommunikation om fettmetabolism i spirande jäst. .

Algoritm

Watt-Strogatz-graf

Givet det önskade antalet noder $N$ , medelgraden $\displaystyle K}$ ${\ displaystyle 0\leq \beta \leq 1}$ (antas vara ett jämnt heltal), och en parameter $\beta$ , alla uppfyller ≤ och $N\gg K\gg \ln N\gg 1$ , modellen konstruerar en oriktad graf med $N$ noder och ${\frac {NK}{2}}$ kanter på följande sätt:

Konstruera ett vanligt ringgitter, en graf med $N$ -noder som var och en är ansluten till $K$ -grannar, $K/2$ på varje sida. Det vill säga, om noderna är märkta $0\ldots {N-1}$ , finns det en kant $(i,j)$ om och endast om $0<|ij|\ \mathrm {mod} \ \left(N-1-{\frac {K}{2}}\right)\leq {\frac {K}{2}}.$
För varje nod $i=0,\dots ,{N-1}$ ta varje kant som ansluter $i$ till dess $K/2$ längst till höger grannar, det vill säga varje kant $(i,j\ \mathrm {mod} \ N)$ med $i<j\leq i+K/2$ , och koppla om den med sannolikheten $\beta$ . Omkoppling görs genom att ersätta $(i,j\ \mathrm {mod} \ N)}$ $(i,k)$ med där ${\ displaystyle k}$ väljs enhetligt slumpmässigt från alla möjliga noder samtidigt som man undviker självloopar ( $k\neq i$ ) och länkduplicering (det finns ingen kant $(i, {k'})$ med $k'=k$ vid denna punkt i algoritmen).

Egenskaper

Modellens underliggande gitterstruktur producerar ett lokalt klustrat nätverk, medan de slumpmässigt omkopplade länkarna dramatiskt minskar de genomsnittliga väglängderna . Algoritmen introducerar om $\beta {\frac {NK}{2}}$ av sådana icke-gitterkanter. Att variera $\beta$ gör det möjligt att interpolera mellan ett regelbundet gitter ( $\beta =0$ ) och en struktur nära en Erdős–Rényi slumpmässig graf $G (N,p)$ med $p={\frac {K}{N-1}}$ vid $\beta =1$ . Den närmar sig inte den faktiska ER-modellen eftersom varje nod kommer att vara ansluten till minst $K/2$ andra noder.

av intresse är den genomsnittliga väglängden , klustringskoefficienten och gradfördelningen .

Genomsnittlig väglängd

För ett ringgitter är den genomsnittliga väglängden $\ell (0)\approx N/2K\gg 1$ och skalas linjärt med systemstorleken. I begränsningsfallet β $\beta \rightarrow 1$ närmar sig grafen en slumpmässig graf med $\displaystyle \ell (1)\approx {\frac { \ln N}{\ln K}}}$ , samtidigt som det inte konvergerar till det. I det mellanliggande området $0<\beta <1$ sjunker den genomsnittliga väglängden mycket snabbt med ökande ${\displaystyle \beta } och$ närmar sig snabbt sitt gränsvärde.

Klusteringskoefficient

För ringgittret är klusteringskoefficienten $C(0)={\frac {3(K-2)}{4(K-1)} }$ $3/4$ och tenderar alltså till när $K$ växer, oberoende av systemstorleken I begränsningsfallet $\beta \rightarrow 1$ är klusteringskoefficienten av samma ordning som klusteringskoefficienten för klassiska slumpmässiga grafer, $C=K/ (N-1)$ och är således omvänt proportionell mot systemstorleken. I den mellanliggande regionen förblir klustringskoefficienten ganska nära sitt värde för det reguljära gittret och faller endast vid relativt högt $\beta$ . Detta resulterar i en region där den genomsnittliga väglängden sjunker snabbt, men klustringskoefficienten inte gör det, vilket förklarar fenomenet "small-world".

Om vi använder måttet Barrat och Weigt för att gruppera

C'(\beta )

definierat som bråkdelen mellan det genomsnittliga antalet kanter mellan grannarna till en nod och det genomsnittliga antalet möjliga kanter mellan dessa grannar, eller alternativt

C'(\beta )\equiv {\frac {3\gånger {\text{antal trianglar}}}{ \text{antal anslutna trippel}}}

då får vi

C'(\beta )\sim C(0)(1-\beta )^{3}.

Examensfördelning

Gradfördelningen i fallet med ringgittret är bara en Dirac deltafunktion centrerad vid ${\displaystyle K}$ . Gradfördelningen för ett stort antal noder och $0<\beta <1$ kan skrivas som,

P(k)\approx \sum _{n=0}^{f(k,K)}{{K/2} \choose {n}}(1-\beta )^{n}\beta ^{K/2-n}{\frac {(\beta K/2)^{kK/2-n}}{(kK/2-n)!}}e^{- \beta K/2},

där $k_{i}$ är antalet kanter som den ${\displaystyle i^{\text{th}}}-$ noden har eller dess grad. Här $k\geq K/2$ , och $f(k,K)=\min( kK/2,K/2)$ . Formen på gradfördelningen liknar den för en slumpmässig graf och har en uttalad topp vid $k=K$ och avtar exponentiellt för stora $|kK|$ . Nätverkets topologi är relativt homogen, vilket betyder att alla noder är av liknande grad.

Begränsningar

Modellens stora begränsning är att den ger en orealistisk gradfördelning . Däremot är riktiga nätverk ofta skalfria nätverk som är inhomogena i grad, med nav och en skalfri gradfördelning. Sådana nätverk beskrivs bättre i det avseendet av den förmånliga anknytningsfamiljen av modeller, som Barabási–Albert (BA)-modellen . (Å andra sidan lyckas Barabási–Albert-modellen inte producera de höga nivåerna av klustring som ses i verkliga nätverk, en brist som inte delas av Watts och Strogatz-modellen. Således bör varken Watts och Strogatz-modellen eller Barabási–Albert-modellen ses som fullt realistiskt.)

Watts och Strogatz-modellen innebär också ett fast antal noder och kan därför inte användas för att modellera nätverkstillväxt.

Se även