Kopiera nätverksmodeller

Kopieringsnätverksmodeller är nätverksgenereringsmodeller som använder en kopieringsmekanism för att bilda ett nätverk, genom att upprepade gånger duplicera och mutera befintliga noder i nätverket. En sådan nätverksmodell har först föreslagits 1999 för att förklara nätverket av länkar mellan webbsidor, men har sedan dess använts för att modellera biologiska nätverk och citeringsnätverk.

Ursprung

1999 publicerade Jon Kleinberg och 3 medförfattare en artikel till Computing and combinatorics som försöker konstruera en nätverksmodell som förklarar mönster som finns i en analys av World Wide Web . Intuitionen bakom modellen var att när en användare bestämmer sig för att bygga och publicera sin egen webbsida, stöter hon på en lista med länkar för sitt ämne av intresse på webben och slutar med att kopiera denna samling, eller många sådana samlingar till sin egen webbsida . Detta skapar en ny nod i nätverket - den nya sidan - och kopierar kanter från redan existerande noder på något sätt.

De skisserade en modell väldigt allmänt, men analyserade inte förutsägelserna för en exakt modell i detalj, mestadels på grund av beräkningsbegränsningar, utan föreslog att kopiering av noder slumpmässigt är en enkel, modellvärdig mekanism för att skapa Zipfian- distributionsnätverk .

Denna artikel har sedan dess citerats över 1200 gånger, vilket är ett antal jämförbart med betydande artiklar som bidrar till nätverksvetenskap, som den som beskriver Erdős– Rényi-modellen (cirka 8300) och inkluderar anmärkningsvärda nätverksvetenskapliga böcker som Mark Newmans.

Beskrivning

Allmän modell

För att förstå en generell modell, ta en grundläggande nätverkstillväxtmodell, som kännetecknas av fyra stokastiska processer. Skapandeprocesser $C_{v}$ och $C_{e}$ för nod- och kantskapande och raderingsprocesser $D_{v}$ och $D_{e}$ för nod- och kantborttagning.

Ta en diskret tidsram, där $C_{v}$ helt enkelt består av att i varje steg skapa en nod med sannolikhet $a_{c}(t)$ , och på liknande sätt $D_{v}$ tar bort en nod med sannolikhet a _d ( t ). Följaktligen betyder detta också att $D_{e}$ inkluderar att ta bort alla kanter som tillhörde en nod som togs bort.

$C_{e}$ är där kärnan i kopieringsmodellen finns. I den ursprungliga artikeln karaktäriserar de $C_{e}$ med en sannolikhetsfördelning, som bestämmer en nod $v$ att lägga till kanter från, och ett antal kanter $k$ som kommer läggas till. Och med sannolikhet $\beta$ att k kanterna antingen kopieras eller läggs till slumpmässigt. Med sannolikheten $\beta$ dras alla ${\displaystyle k} kanter från v till noder valda oberoende och likformigt slumpmässigt.$ Med sannolikhet $(1-\beta )$ kopieras k kanterna från en slumpmässigt vald nod u $\displaystyle u}$ . Det betyder att $k$ grannar till $u$ blir grannar till $v$ . Om $u$$l<k$ en grad högre än $k$ väljs ${\displaystyle k} kanter slumpmässigt och om den har en lägre grad$ < , en nästa nod väljs slumpmässigt och $kl$ av dess kanter kopieras, och så vidare.

Det kan visas att ett sådant nätverk producerar en effektlagsgradsfördelning, med en exponent $\gamma =$${\frac {2-a}{1-a} }$ där $a$ är förhållandet mellan antalet av de slumpmässigt tillagda kanterna och antalet kopierade kanter. Så med ett förhållande mellan noll och 0,5 kan en potenslagsfördelning med en exponent på $2<\gamma <3$ uppnås. Observera också att när förhållandet närmar sig 1, går exponenten till oändlighet.

GNC-modell

En annan enkel modell, föreslagen för att förklara observationen att den genomsnittliga nodgraden växer med systemstorleken lägger till noder en i taget. En ny nod väljer slumpmässigt en nod från de befintliga och förutom att kopiera alla kanter som målnoden tilldelades vid introduktionen, ansluter den till själva noden, vilket ökar medelgraden något. Till exempel om målnoden är den allra första i nätverket, läggs inga ytterligare kanter till, bara den mellan den första noden och den sista. Ta de två extremfallen. Om en ny nod alltid ansluter till den första noden, bildar modellen ett stjärndiagram , där varje nod har grad ett, men den första noden har ökande gradantal. I detta fall ökar medelgraden med ${\frac {1}{N}}$ med varje ytterligare nod, där $N$ är antalet noder. I det andra extremfallet, där de nya noderna ansluter till den som lagts till före den, bildas en komplett graf och medelgraden ökar med 1 för varje ny nod.

Gå modell

En kopieringsmodell som är något av en blandning av de två introducerades av Vazquez. I denna modell, när en ny nod läggs till, ansluter den till en slumpmässigt vald nod som redan finns i nätverket, och till var och en av dess grannar med möjligheten ${\displaystyle p} .$ Så med $p=0$ skapar denna graf en kedja och $p=1$ skapar en komplett graf. Beroende på $p$ kan denna graf producera ett antal effektlagsgradsfördelningar med vissa cutoffs som kännetecknar verkliga nätverk väl.

Biologiska nätverk

Det har funnits ett stort intresse för att modellera biologiska nätverk, såsom proteininteraktionsnätverk och genetiska regulatoriska nätverk med användning av kopieringsnätverksmodeller. Gener som innehåller information om hur en nod i ett nätverk ska interagera med andra tenderar att duplicera i evolutionen, vilket duplicerar kanterna som fanns i nätverket. Dessutom preferentiella anslutningsnätverk inte riktigt modellera biologiska nätverk väl, både för att de inte är rimliga och för att ett antal biologiska nätverk har effektlagsgradsfördelning med exponent $\gamma <2$ som inte produceras av sådana föredragna nätverksmodeller.

Ta en noddupliceringsprocess, där varje nod initialt har samma sannolikhet att dupliceras i ett enda tidssteg. Sannolikheten för duplicering påverkas dock av historiken för tidigare dupliceringar, och inte alla kanter dupliceras, bara en slumpmässigt vald delmängd av dem. En sådan partiell dupliceringsmodell kan producera effektlagsfördelningar med exponenter ${\displaystyle \gamma <2} ,$ i överensstämmelse med gradfördelningen för ett antal biologiska nätverk, oavsett startgrafen.