Medlingsdriven anknytningsmodell

I den skalfria nätverksteorin ( matematisk teori om nätverk eller grafteori ) tycks en medlingsdriven anknytningsmodell (MDA) förkroppsliga en preferentiell anknytningsregel tyst snarare än explicit. Enligt MDA-regeln väljer en ny nod först en nod från det befintliga nätverket slumpmässigt och ansluter sig inte till den utan med en av grannarna som också plockas slumpmässigt.

Barabasi och Albert noterade 1999 genom sin nyskapande artikel att (i) de flesta naturliga och konstgjorda nätverk inte är statiska, snarare växer de med tiden och (ii) nya noder ansluter inte till en redan ansluten slumpmässigt snarare preferentiellt med respekt till sina grader. Den senare mekanismen kallas preferential attachment (PA) regel som förkroppsligar de rika blir rikare fenomen inom ekonomi. I sin första modell, känd som Barabási–Albert-modellen , väljer Barabási och Albert (BA-modellen).

$\Pi (i)={\frac {k_{i}}{\sum _{j=1}k_{j}}}$

där $\Pi (i)$ är sannolikheten att den nya noden väljer en nod $i$ från de märkta noderna i det befintliga nätverket. Den förkroppsligar direkt mekanismen för de rika blir rikare.

Nyligen har Hassan et al. föreslog en medlingsdriven anknytningsmodell som verkar förkroppsliga PA-regeln men inte direkt snarare i förklädnad. I MDA-modellen väljer en inkommande nod en befintlig nod att ansluta genom att först välja en av de befintliga noderna slumpmässigt som betraktas som mediator. Den nya noden ansluter sedan till en av medlarens grannar, som också väljs slumpmässigt. Nu är frågan: Vad är sannolikheten $\Pi (i)$ att en redan existerande nod $i$ slutligen väljs för att koppla den till den nya noden? Säg, noden $i$ har graden $k_{i}$ och därför har den $k_{i}$ grannar. Tänk på att grannarna till $i$ är märkta $1,2,\ldots ,k_{i}$ som har grader $k_{1},k_{2},\ldots ,k_{k_{i}}$ respektive. Man kan nå noden $i$ från var och en av dessa ${\displaystyle k_{i}}-$ noder med sannolikheter invers av deras respektive grader, och var och en av ${\displaystyle k_{i}}-$ noderna är kommer sannolikt att väljas slumpmässigt med sannolikhet $1/N$ . Således är sannolikheten $\Pi (i)$ för MDA-modellen:

$\Pi (i)={\frac {1}{N}}\left[{\frac {1}{k_{1}}}+{\frac {1}{k_{2}}}+ \cdots +{\frac {1}{k_{k_{i}}}}\right]={\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_ {j}}}}{N}}.$

Det kan skrivas om som

$\Pi (i)={\frac {k_{i}}{N}}\cdot {\frac {\ summa _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}},$

där faktorn ${\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}} {k_{i}}}$ är inversen av det harmoniska medelvärdet (IHM) av grader av $k_{i}$ grannarna till noden $i$ . Omfattande numerisk simulering tyder på att för små $m$ fluktuerar IHM-värdet för varje nod så vilt att medelvärdet av IHM-värdena över hela nätverket inte har någon betydelse. Men för stora $m$ (speciellt $m$ ungefär större än 14) blir fördelningen av IHM-värdet för hela nätverket lämnad skev Gaussisk typ och medelvärdet börjar få en betydelse som blir ett konstant värde i den stora $m$ -gränsen. I denna gräns finner man att $\Pi (i)\propto k_{i}$ vilket är exakt PA-regeln. Det innebär att ju högre länkar (grad) en nod har, desto högre är chansen att få fler länkar eftersom de kan nås på ett större antal sätt genom medlare som i huvudsak förkroppsligar den intuitiva idén om rik blir rikare mekanism. Därför kan MDA-nätverket ses följa PA-regeln men i förklädnad. Dessutom, för liten $m$ är MFA inte längre giltig, snarare blir anknytningssannolikheten $\Pi (i)$ superpreferentiell till karaktären.

Idén med MDA-regeln kan hittas i tillväxtprocessen för det vägda plana stokastiska gittret (WPSL) . En existerande nod (mitten av varje block av WPSL betraktas som noder och den gemensamma gränsen mellan blocken som länkarna mellan motsvarande noder) under processen förstärker länkar endast om en av dess grannar inte väljs själv. Det innebär att ju högre länkar (eller grad) en nod har, desto högre är chansen att få fler länkar eftersom de kan nås på ett större antal sätt. Det förkroppsligar i huvudsak den intuitiva idén om PA-styre. Därför är den dubbla av WPSL ett nätverk som kan ses följa regeln för preferensbifogning men i förklädnad. I själva verket visar sig dess gradfördelning uppvisa maktlag som understryks av Barabasi och Albert som en av de väsentliga ingredienserna.

Medlingsdrivet anslutningsnätverk av storlek 256 noder

Gradfördelning: De två faktorerna att medelvärdet för IHM är meningsfullt och det är oberoende av $N$ innebär att man kan tillämpa medelfältsapproximationen (MFA). Det vill säga, inom denna approximation kan man ersätta det sanna IHM-värdet $\beta /m$ för varje nod med deras medelvärde, där faktorn $m$ som antalet kanter de nya noderna kommer med införs för senare bekvämlighet. Hastighetsekvationen att lösa blir då exakt som den för BA-modellen och därför är nätverket som uppstår efter MDA-regeln också skalfritt till sin natur. Den enda skillnaden är att exponenten $\gamma ={{1} \over {\beta (m)}}+1$ beror på $m$ där som i BA-modellen $\gamma =3$ oberoende av $m$ .

Grafer över gradfördelning för MDA-modellen. De distinkta diagrammen är för inkommande noder som kommer kanter m = 1, m = 15 och m = 100. I insättningen visar vi variationen i exponenten för gradfördelningen som funktion av m .

Ledarskapsuthållighet sannolikhet

I det växande nätverket är inte alla noder lika viktiga. Omfattningen av deras betydelse mäts med värdet av deras grad $k$ . Noder som är kopplade till ett ovanligt stort antal andra noder, dvs noder med exceptionellt högt $k$ -värde, kallas nav. De är speciella eftersom deras existens gör medelavståndet, mätt i enheter av antalet länkar, mellan noder otroligt litet och spelar därmed nyckelrollen för att sprida rykten, åsikter, sjukdomar, datavirus etc. Det är därför viktigt att känna till egenskaper hos det största navet, som vi betraktar som ledande. Liksom i samhället är ledarskapet i ett växande nätverk inte permanent. Det vill säga, när en nod väl blir ledare betyder det inte att den förblir ledare i oändlighet . En intressant fråga är: hur länge behåller ledaren denna ledarskapsegenskap när nätverket utvecklas? För att hitta ett svar på denna fråga definierar vi sannolikheten för ledarskapspersistens $F(\tau )$ att ledaren behåller sitt ledarskap åtminstone upp till tiden $\tau$ . Persistenssannolikhet har varit av intresse i många olika system, allt från förgrovning av dynamik till fluktuerande gränssnitt eller polymerkedjor.

De två plotten överst avslöjar maktlagsbeteendet för sannolikheten för ledarskapspersistens. För att uppskatta rollen av m ger vi sannolikhet för ledarskapspersistens för två värden (m=1 och m=100) i samma plot: (a) BA-nätverk och (b) MDA-nätverk. De två diagrammen längst ner är för persistensexponenten som en funktion av m i (c) BA-nätverk och (d) MDA-nätverk.

Grundtanken med MDA-regeln är dock inte helt ny eftersom antingen denna eller modeller liknande denna finns i några tidigare arbeten, även om deras tillvägagångssätt, efterföljande analys och deras resultat skiljer sig från våra. Till exempel presenterade Saramaki och Kaski en slumpmässigt baserad modell. En annan modell föreslagen av Boccaletti et al. kan se ut som vår, men den skiljer sig markant vid närmare titt. Nyligen gav Yang {\it et al.} också en form för $\Pi (i)$ och tillgrep medelfältsapproximation. Men karaktären av deras uttryck skiljer sig väsentligt från den som studerats av Hassan et al. . Ännu en närbesläktad modell är modellen Growing Network with Redirection (GNR) som presenteras av Gabel, Krapivsky och Redner där en ny nod vid varje tidssteg antingen kopplas till en slumpmässigt vald målnod med sannolikheten 1 − r {\displaystyle $}$ , eller till föräldern till målet med sannolikheten $r=1$ . GNR-modellen med $r=1$ kan likna MDA-modellen. Men till skillnad från GNR-modellen är MDA-modellen för oriktade nätverk, och att den nya länken kan ansluta till vilken granne som helst till medlar-föräldern eller inte. En ytterligare skillnad är att i MDA-modellen kan en ny nod ansluta sig till det befintliga nätverket med $m$ -kanter och i GNR-modellen betraktas den endast som ${\displaystyle m=1} .$