Skalfritt nätverk - Scale-free network

Degradistribution för ett nätverk med 150000 hörn och medelgrad = 6 skapat med Barabási – Albert -modellen (blå prickar). Distributionen följer en analytisk form som ges av förhållandet mellan två gammafunktioner (svart linje) som approximeras som en power-law.

Nätverksvetenskap
Teori
Graf Komplex nätverk Smitta Liten värld Skalfri Gemenskapsstruktur Perkolering Evolution Kontrollerbarhet Diagramritning Socialt kapital Länkanalys Optimering Ömsesidighet Stängning Homofilt Transitivitet Preferensbilaga Balans teori Nätverkseffekt Socialt inflytande
Nätverkstyper
Informativ (dator) Telekommunikation Transport Social Vetenskapligt samarbete Biologisk Konstgjord neural Beroende av varandra Semantisk Rumslig Beroende Flöde on-Chip
Grafer
Funktioner Klick Komponent Skära Cykel Datastruktur Kant Slinga Grannskap Väg Vertex Angränsningslista  / matris Incidenslista  / matris Typer Bipartit Komplett Riktad Hyper Mång Slumpmässig Viktad
Metrik Algoritmer
Centralitet Grad Motiv Kluster Examensfördelning Assortativitet Distans Modularitet Effektivitet
Modeller
Topologi Slumpmässig graf Erdős – Rényi Barabási – Albert Fitnessmodell Watts – Strogatz Exponentiell slumpmässig (ERGM) Slumpmässig geometrisk (RGG) Hyperboliskt (HGN) Hierarkisk Stokastiskt block Blockmodellering Maximal entropi Mjuk konfiguration LFR -riktmärke Dynamik Boolskt nätverk agentbaserad Epidemi / SIR
Listor Kategorier
Ämnen programvara Nätverksforskare Kategori: Nätverksteori Kategori: Grafteori
v t e

Ett skalfritt nät är ett nätverk vars gradfördelning följer en kraftlag , åtminstone asymptotiskt. Det vill säga fraktionen P ( k ) av noder i nätverket som har k -anslutningar till andra noder går för stora värden på k som

${\ displaystyle P (k) \ \ sim \ k^{\ boldsymbol {-\ gamma}}}$

var är en parameter vars värde normalt ligger i intervallet 2 << 3 (där det andra momentet ( skalparametern ) är oändligt men det första ögonblicket är ändligt, även om det ibland kan ligga utanför dessa gränser. ${\ displaystyle \ gamma}$${\ displaystyle \ gamma}$${\ displaystyle k^{\ boldsymbol {-\ gamma}}}$

Många nätverk har rapporterats vara skalfria, även om statistisk analys har motbevisat många av dessa påståenden och allvarligt ifrågasatt andra. Dessutom kan vissa har hävdat att veta om en gradfördelning är fett-tailed är viktigare än att veta om ett nätverk är skalfria enligt statist rigorösa definitioner. Preferensbilaga och fitnessmodellen har föreslagits som mekanismer för att förklara gissade makträttsfördelningar i verkliga nätverk. Alternativa modeller som superlinjär preferensbilaga och preferensbilaga för andra grannar kan tyckas generera övergående skalfria nätverk, men gradfördelningen avviker från en kraftlag när nätverk blir mycket stora.

Historia

I studier av nätverk av citat mellan vetenskapliga artiklar visade Derek de Solla Price 1965 att antalet länkar till papper-det vill säga antalet citat de får-hade en kraftig distribution efter en Pareto-distribution eller maktlag , och således att citatnätverket är skalfritt. Han använde dock inte termen "skalfritt nätverk", som inte myntades förrän några decennier senare. I ett senare papper 1976 föreslog Price också en mekanism för att förklara förekomsten av maktlagar i citatnätverk, som han kallade "kumulativ fördel" men som idag är mer allmänt känd under namnet preferensbilaga .

Det senaste intresset för skalfria nätverk startade 1999 med arbete av Albert-László Barabási och kollegor vid University of Notre Dame som kartlade topologin för en del av World Wide Web och fann att några noder, som de kallade "nav", hade många fler anslutningar än andra och att nätet som helhet hade en power-law-fördelning av antalet länkar som ansluter till en nod. Efter att ha funnit att några andra nätverk, däribland några sociala och biologiska nätverk, också hade kraftiga examensfördelningar, myntade Barabási och medarbetare termen "skalfritt nätverk" för att beskriva klassen av nätverk som uppvisar en power-law examensfördelning. Men studerar sju exempel på nätverk i sociala, ekonomiska, tekniska, biologiska och fysiska system, Amaral et al. kunde inte hitta ett skalfritt nätverk bland dessa sju exempel. Endast ett av dessa exempel, filmskådespelarnätverket, hade gradfördelning P ( k ) efter en maktlagsregim för måttliga k , men så småningom följdes denna maktlagsregim av en kraftig avstängning som visar exponentiellt förfall för stora k .

Barabási och Réka Albert föreslog en generativ mekanism för att förklara utseendet på maktlagsdistributioner, som de kallade " preferensbindning " och som i huvudsak är densamma som den som Price föreslog. Analytiska lösningar för denna mekanism (liknar också lösning av Price) presenterades år 2000 av Dorogovtsev, Mendes och Samukhin och oberoende av Krapivsky, Redner och Leyvraz, och senare noggrant bevisat av matematikern Béla Bollobás . Noterbart är dock att denna mekanism bara producerar en specifik delmängd av nätverk i den skalfria klassen, och många alternativa mekanismer har upptäckts sedan.

Historien om skalfria nätverk innehåller också viss oenighet. På empirisk nivå har flera nätverks skalfria karaktär ifrågasatts. Till exempel trodde de tre bröderna Faloutsos att Internet hade en makträttsfördelning på grundval av spårvägsdata ; emellertid har det föreslagits att detta är en lager 3- illusion skapad av routrar, som framstår som höggradiga noder samtidigt som den döljer den inre skikt 2- strukturen för de ASer de sammankopplar.

På en teoretisk nivå har förfiningar till den abstrakta definitionen av skalfri föreslagits. Till exempel Li et al. (2005) erbjöd nyligen en potentiellt mer exakt "skalfri metrisk". Låt i korthet G vara en graf med kantuppsättning E och ange graden av en toppunkt (det vill säga antalet kanter som infaller till ) med . Definiera ${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle \ deg (v)}$

${\ displaystyle s (G) = \ sum _ {(u, v) \ in E} \ deg (u) \ cdot \ deg (v).}$

Detta maximeras när höggradiga noder är anslutna till andra höggradiga noder. Definiera nu

${\ displaystyle S (G) = {\ frac {s (G)} {s _ {\ max}}},}$

där s _max är det maximala värdet på s ( H ) för H i uppsättningen av alla grafer med graden fördelning identiska med den för  G . Detta ger ett mått mellan 0 och 1, där en graf G med liten S ( G ) är "skalrik" och en graf G med S ( G ) nära 1 är "skalfri". Denna definition fångar begreppet självlikhet som antyds i namnet "skalfritt".

Översikt

Det finns två huvudkomponenter som förklarar uppkomsten av den skalfria egendomen i komplexa nätverk: tillväxten och den förmånliga anknytningen. Med "tillväxt" kallas en tillväxtprocess där nya noder under en längre tid ansluter till ett redan befintligt system, ett nätverk (som World Wide Web som har ökat med miljarder webbsidor under 10 år). Slutligen kallas "preferensbilaga" för en ny kommande nod som föredrar att ansluta till en annan nod som redan har ett visst antal länkar med andra. Således finns det en högre sannolikhet för att fler och fler noder kommer att länka sig till den som redan har många länkar, vilket leder denna nod till ett nav i fina . Beroende på nätverket kan naven antingen vara assortativa eller disassortativa. Assortativitet skulle finnas i sociala nätverk där välanslutna/kända personer tenderar att lära känna varandra bättre. Disassortativitet skulle finnas i tekniska (Internet, World Wide Web) och biologiska (proteininteraktion, metabolism) nätverk.

Egenskaper

Slumpmässigt nätverk (a) och skalfritt nätverk (b). I det skalfria nätverket markeras de större naven.

Komplex nätverksgradsfördelning av slumpmässiga och skalfria

Den mest anmärkningsvärda egenskapen i ett skalfritt nätverk är den relativa gemenskapen av hörn med en grad som mycket överstiger genomsnittet. De högsta gradens noder kallas ofta "hubbar" och anses tjäna specifika syften i deras nätverk, även om detta beror mycket på domänen.

Perkolering

Den skalfria egenskapen korrelerar starkt med nätverkets robusthet mot misslyckande. Det visar sig att de stora naven följs tätt av mindre. Dessa mindre nav följs i sin tur av andra noder med ännu mindre grad och så vidare. Denna hierarki möjliggör ett feltolerant beteende. Om misslyckanden inträffar slumpmässigt och de allra flesta noder är de med liten grad, är sannolikheten att ett nav skulle påverkas nästan försumbar. Även om ett hubb-fel inträffar kommer nätverket i allmänhet inte att förlora sin anslutning på grund av de återstående naven. Å andra sidan, om vi väljer några stora hubbar och tar ut dem från nätverket, förvandlas nätverket till en uppsättning ganska isolerade grafer. Således är hubbar både en styrka och en svaghet för skalfria nätverk. Dessa egenskaper har studerats analytiskt med hjälp av perkolationsteori av Cohen et al och Callaway et al. Det bevisades av Cohen et al att för ett brett spektrum av skalfria nätverk för den kritiska tröskeln infiltration, . Detta innebär att borttagning av en slumpmässig del av noder från nätverket inte förstör nätverket. Detta står i kontrast till Erdős – Rényi -grafen där , var är den genomsnittliga graden. Misslyckandena som diskuteras ovan är slumpmässiga, som vanligtvis antas i perkolationsteorin. Vid generalisering av perkolering även till icke-slumpmässiga men riktade attacker, t.ex. på högsta grad noder , förändras resultaten, t.ex. Nyligen har en ny typ av fel i nätverk utvecklats, kallade lokaliserade attacker. I detta fall väljer man slumpmässigt en nod och tar bort sina grannar och nästa närmaste grannar tills en bråkdel av 1-p-noder har tagits bort. Lokaliserade attacker gör skalfria nätverk mer sårbara jämfört med slumpmässiga attacker och . De kritiska exponenterna för perkolering i skalfria nätverk skiljer sig från slumpmässiga Erdős – Rényi -nätverk. ${\ displaystyle 2 <\ gamma <3}$ ${\ displaystyle p_ {c} = 0}$${\ displaystyle p_ {c} = 1/{\ bar {k}}}$${\ displaystyle {\ bar {k}}}$${\ displaystyle p_ {c}}$${\ displaystyle p_ {c}> 0}$

Kluster

En annan viktig egenskap hos skalfria nätverk är klusteringskoefficientfördelningen , som minskar när nodgraden ökar. Denna fördelning följer också en maktlag. Detta innebär att låggradiga noder tillhör mycket täta undergrafer och dessa undergrafer är anslutna till varandra via nav. Tänk på ett socialt nätverk där noder är människor och länkar är bekanta relationer mellan människor. Det är lätt att se att människor tenderar att bilda gemenskaper, dvs små grupper där alla känner alla (man kan tänka sig ett sådant samhälle som ett komplett diagram ). Dessutom har medlemmarna i en gemenskap också några bekanta relationer till människor utanför den gemenskapen. Vissa människor är dock anslutna till ett stort antal samhällen (t.ex. kändisar, politiker). Dessa människor kan betraktas som de nav som är ansvariga för fenomenet i den lilla världen .

För närvarande varierar de mer specifika egenskaperna hos skalfria nätverk med den generativa mekanism som används för att skapa dem. Till exempel placerar nätverk som genereras genom förmånlig koppling vanligtvis höggradiga hörn i mitten av nätverket och förbinder dem tillsammans för att bilda en kärna, med gradvis lägre gradnoder som utgör regionerna mellan kärnan och periferin. Slumpmässigt borttagande av till och med en stor del av hörnen påverkar nätverkets övergripande anslutning väldigt lite, vilket tyder på att sådana topologier kan vara användbara för säkerheten , medan riktade attacker förstör anslutningen mycket snabbt. Andra skalfria nätverk, som placerar höggradiga hörn vid periferin, uppvisar inte dessa egenskaper. På samma sätt kan klusteringskoefficienten för skalfria nät variera avsevärt beroende på andra topologiska detaljer.

Avstånd i skalfria nätverk

En ytterligare egenskap gäller det genomsnittliga avståndet mellan två hörn i ett nätverk. Som med de flesta störda nätverk, till exempel den lilla världens nätverksmodell , är detta avstånd mycket litet i förhållande till ett högordnat nätverk, till exempel ett gallerdiagram . I synnerhet kommer en okorrelerad power-law-graf med 2 <γ <3 att ha ultraliten diameter d ~ ln ln  N där N är antalet noder i nätverket, vilket bevisats av Cohen och Havlin. Således kan diametern för ett växande skalfritt nät anses i praktiken nästan konstant.

Immunisering

Frågan om hur man effektivt immuniserar fria nätverk som representerar realistiska nätverk som Internet och sociala nätverk har studerats ingående. En sådan strategi är att immunisera de största gradnoderna, dvs riktade (avsiktliga) attacker eftersom p för detta fall är relativt högt och mindre noder behövs för att immuniseras. Men i många realistiska fall är den globala strukturen inte tillgänglig och de största gradnoderna är inte kända. För sådana fall har metoden för bekant -immunisering utvecklats. I det här fallet, vilket är ganska effektivt väljer man slumpmässigt noder men immuniserar sina grannar. En annan och ännu effektivare metod är baserad på grafparitionsmetoden. ${\ displaystyle c}$

Egenskaper för slumpmässig graf kan förändras eller förbli oföränderliga under grafomvandlingar. Mashaghi A. et al., Till exempel, visade att en transformation som omvandlar slumpmässiga grafer till sina kant-dubbla grafer (eller linjediagram) producerar en ensemble av grafer med nästan samma gradfördelning, men med gradskorrelationer och en betydligt högre gruppering. koefficient. Skalfria grafer, som sådana, förblir skalfria under sådana transformationer.

Exempel

Även om många verkliga nätverk anses vara skalfria, förblir bevisen ofta otydliga, främst på grund av utvecklingen av medvetenheten om strängare dataanalystekniker. Som sådan diskuteras fortfarande den skalfria karaktären hos många nätverk av det vetenskapliga samfundet. Några exempel på nätverk som påstås vara skalfria inkluderar:

• Vissa sociala nätverk , inklusive samarbetsnätverk. Två exempel som har studerats utförligt är filmskådespelares samarbete i filmer och medförfattare av matematiker av papper .
• Många typer av datornätverk , inklusive internet och webgrafiken över World Wide Web .
• Programvaruberoende grafer, några av dem beskrivs med en generativ modell.
• Vissa finansiella nätverk, t.ex. interbankbetalningsnät
• Protein-protein-interaktionsnätverk .
• Semantiska nätverk .
• Flygbolagsnät.

En ögonblicksbild av det vägda plana stokastiska gitteret (WPSL).

Skalfri topologi har också hittats i högtemperatur superledare. Egenskaperna hos en högtemperatur supraledare-en förening där elektroner följer kvantfysikens lagar och flödar i perfekt synkronisering, utan friktion-verkar vara kopplade till fraktala arrangemang av till synes slumpmässiga syreatomer och gitterförvrängning.

En rymdfyllande cellstruktur, viktat plan stokastiskt gitter (WPSL) har nyligen föreslagits vars samordningstalfördelning följer en kraftlag. Det innebär att gallret har några kvarter som har förvånansvärt många grannar som de delar gemensamma gränser med. Konstruktionen börjar med en initiator, säg en kvadrat med enhetsarea och en generator som delar den slumpmässigt i fyra block. Generatorn appliceras därefter sekventiellt om och om igen på endast ett av de tillgängliga blocken som företrädesvis plockas med avseende på sina områden. Det resulterar i uppdelning av torget i allt mindre ömsesidigt uteslutande rektangulära block. Dubbeln av WPSL (DWPSL) erhålls genom att varje block ersätts med en nod i mitten och gemensam gräns mellan block med en kant som förenar de två motsvarande hörnen framträder som ett nät vars gradfördelning följer en power-law. Anledningen till det är att den växer efter medlingsstyrd anknytningsmodellregel som också förkroppsligar preferensbindningsregel men i förklädnad.

Generativa modeller

Skalfria nätverk uppstår inte bara av en slump. Erdős och Rényi (1960) studerade en tillväxtmodell för grafer där två steg i varje steg väljs enhetligt slumpmässigt och en länk infogas mellan dem. Egenskaperna för dessa slumpmässiga grafer skiljer sig från egenskaperna i skalfria nätverk, och därför behövs en modell för denna tillväxtprocess.

Den mest kända generativa modellen för en delmängd av skalfria nätverk är Barabási och Alberts (1999) rika blir rikare generativa modell där varje ny webbsida skapar länkar till befintliga webbsidor med en sannolikhetsfördelning som inte är enhetlig, men proportionell mot den aktuella graden av webbsidor. Denna modell uppfanns ursprungligen av Derek J. de Solla Price 1965 under termen kumulativ fördel , men nådde inte popularitet förrän Barabási återupptäckte resultaten under sitt nuvarande namn ( BA Model ). Enligt denna process kommer en sida med många länkar att locka fler länkar än en vanlig sida. Detta genererar en power-law men den resulterande grafen skiljer sig från det faktiska webbdiagrammet i andra egenskaper, såsom närvaron av små tätt anslutna grupper. Mer generella modeller och nätverksegenskaper har föreslagits och studerats. Till exempel, Pachon et al. (2018) föreslog en variant av den rika bli rikare generativa modellen som tar hänsyn till två olika bifogningsregler: en preferensfästningsmekanism och ett enhetligt val endast för de senaste noder. För en recension se boken av Dorogovtsev och Mendes . Vissa mekanismer som superlinjär förmånsbilaga och andra grannbilaga genererar nätverk som är övergående skalfria, men avviker från en kraftlag när nätverk växer sig stora.

En något annorlunda generativ modell för webblänkar har föreslagits av Pennock et al. (2002). De undersökte samhällen med intressen i ett specifikt ämne, till exempel universitetens hemsidor, offentliga företag, tidningar eller forskare, och kastade de viktigaste naven på webben. I detta fall var fördelningen av länkar inte längre en maktlag utan liknade en normal fördelning . Baserat på dessa observationer föreslog författarna en generativ modell som blandar preferensbilaga med en sannolikhet för att få en länk.

En annan generativ modell är kopimodellen som studerats av Kumar et al. (2000), där nya noder slumpmässigt väljer en existerande nod och kopierar en bråkdel av länkarna i den existerande noden. Detta genererar också en maktlag.

Den tillväxt av nätverken (lägga nya noder) är inte ett nödvändigt villkor för att skapa ett skalfria nätverk. En möjlighet (Caldarelli et al. 2002) är att betrakta strukturen som statisk och dra en länk mellan hörn enligt en särskild egenskap hos de två berörda hörnen. När den statistiska fördelningen för dessa vertexegenskaper (fitnesses) har specificerats visar det sig att under vissa omständigheter även statiska nätverk utvecklar skalfria egenskaper.

Generaliserad skalfri modell

Det har skett en aktivitet i modelleringen av skalfria komplexa nätverk . Receptet av Barabási och Albert har följts av flera variationer och generaliseringar och uppgradering av tidigare matematiska verk. Så länge det finns en kraftlagsfördelning i en modell, är det ett skalfritt nät, och en modell av det nätverket är en skalfri modell.

Funktioner

Många riktiga nätverk är (ungefär) skalfria och kräver därför skalfria modeller för att beskriva dem. I Price-schemat behövs två ingredienser för att bygga upp en skalfri modell:

1. Lägga till eller ta bort noder . Vanligtvis koncentrerar vi oss på att växa nätverket, dvs lägga till noder.

2. Preferensbilaga : Sannolikheten för att nya noder kommer att anslutas till den "gamla" noden. ${\ displaystyle \ Pi}$

Observera att Fitness -modeller (se nedan) också kan fungera statiskt utan att ändra antalet noder. Det bör också komma ihåg att det faktum att modeller med "preferensbilaga" ger upphov till skalfria nätverk inte bevisar att detta är den mekanism som ligger bakom utvecklingen av verkliga skalfria nätverk, eftersom det kan finnas olika mekanismer vid arbete i verkliga system som ändå ger upphov till skalning.

Exempel

Det har gjorts flera försök att generera skalfria nätverksegenskaper. Här är några exempel:

Modellen Barabási – Albert

Den modell Barabási-Albert , en oriktad version av prismodellen har en linjär företrädesrätt fäste och lägger en ny nod vid varje tidssteg. ${\ displaystyle \ Pi (k_ {i}) = {\ frac {k_ {i}} {\ sum _ {j} k_ {j}}}}$

(Observera, en annan allmän egenskap hos verkliga nätverk är att det vill säga det finns en icke -noll sannolikhet att en ny nod fäster till en isolerad nod. Således har den generellt formen , var är nodens initiala attraktionskraft.) ${\ displaystyle \ Pi (k)}$${\ displaystyle \ Pi (0) \ neq 0}$${\ displaystyle \ Pi (k)}$${\ displaystyle \ Pi (k) = A+k^{\ alpha}}$${\ displaystyle A}$

Två nivåer nätverksmodell

Dangalchev bygger en 2-L-modell genom att överväga vikten av var och en av grannarna till en målnod i preferensfästning. Att en nod är attraktiv i 2-L-modellen beror inte bara på antalet noder som är länkade till den utan också på antalet länkar i var och en av dessa noder.

${\ displaystyle \ Pi (k_ {i}) = {\ frac {k_ {i}+C \ sum _ {(i, j)} k_ {j}} {\ sum _ {j} k_ {j}+C \ sum _ {j} k_ {j}^{2}}},}$

där C är en koefficient mellan 0 och 1.

En variant av 2-L-modellen, k2-modellen, där första och andra grannnoder bidrar lika till en målnods attraktivitet, visar uppkomsten av övergående skalfria nätverk. I k2-modellen verkar gradfördelningen ungefär skalfri så länge nätverket är relativt litet, men betydande avvikelser från den skalfria regimen dyker upp när nätverket växer sig större. Detta resulterar i att den relativa attraktiviteten hos noder med olika grader förändras över tiden, en funktion som också observeras i verkliga nätverk.

Medlingsdriven bilaga (MDA) modell

I modellen för medlingsdriven bilaga (MDA) väljer en ny nod som kommer med kanter en befintlig ansluten nod slumpmässigt och ansluter sedan sig själv, inte med den, utan med sina grannar, som också väljs slumpmässigt. Sannolikheten att noden för den befintliga noden som valts är ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle \ Pi (i)}$${\ displaystyle i}$

${\ displaystyle \ Pi (i) = {\ frac {k_ {i}} {N}} {\ frac {\ sum _ {j = 1}^{k_ {i}} {\ frac {1} {k_ { j}}}} {k_ {i}}}.}$

Faktorn är den inversa av det harmoniska medelvärdet (IHM) för grader hos en nods grannar . Omfattande numerisk undersökning tyder på att ungefär det genomsnittliga IHM -värdet i den stora gränsen blir en konstant vilket betyder . Det innebär att ju högre länkar (grad) en nod har, desto större är chansen att få fler länkar eftersom de kan nås på ett större antal sätt genom mediatorer som i huvudsak förkroppsligar den intuitiva idén om att rik blir rikare mekanism (eller den förmånliga tilläggsregel för modellen Barabasi – Albert). Därför kan man se MDA -nätverket följa PA -regeln men i förklädnad. ${\ displaystyle {\ frac {\ sum _ {j = 1}^{k_ {i}} {\ frac {1} {k_ {j}}}} {k_ {i}}}}}$${\ displaystyle k_ {i}}$${\ displaystyle i}$${\ displaystyle m> 14}$${\ displaystyle N}$${\ displaystyle \ Pi (i) \ propto k_ {i}}$

Men för det beskriver vinnaren tar det hela mekanismen som vi finner att nästan av de totala noder har grad ett och en är superrik i grad. När värdet ökar minskar skillnaden mellan de superrika och fattiga och när vi finner en övergång från rik blir superrikare till rik blir rikare mekanism. ${\ displaystyle m = 1}$${\ displaystyle 99 \%}$${\ displaystyle m}$${\ displaystyle m> 14}$

Icke-linjär preferensbilaga

Den Barabási-Albert modell antar att sannolikheten att en nod fäster vid nod är proportionell mot graden av noden . Detta antagande innefattar två hypoteser: det första, det beror på , i motsats till slumpmässiga grafer där , och för det andra, den funktionella formen är linjär . Den exakta formen av är inte nödvändigtvis linjär, och färska studier har visat att gradfördelningen beror starkt på${\ displaystyle \ Pi (k)}$${\ displaystyle i}$ ${\ displaystyle k}$${\ displaystyle i}$${\ displaystyle \ Pi (k)}$${\ displaystyle k}$${\ displaystyle \ Pi (k) = p}$${\ displaystyle \ Pi (k)}$${\ displaystyle k}$${\ displaystyle \ Pi (k)}$${\ displaystyle \ Pi (k)}$

Krapivsky, Redner och Leyvraz visar att nätets skalfria natur förstörs på grund av icke-linjär preferensbindning. Det enda fall där topologin för nätverket är skalan fri är den i vilken preferentiell bindning är asymptotiskt linjär, dvs som . I detta fall leder kursekvationen till ${\ displaystyle \ Pi (k_ {i}) \ sim a _ {\ infty} k_ {i}}$${\ displaystyle k_ {i} \ to \ infty}$

${\ displaystyle P (k) \ sim k^{-\ gamma} {\ text {med}} \ gamma = 1+{\ frac {\ mu} {a _ {\ infty}}}.}$

På så sätt kan exponenten för gradfördelningen ställas in på valfritt värde mellan 2 och . ${\ displaystyle \ infty}$

Hierarkisk nätverksmodell

Hierarkiska nätverksmodeller är, genom design, skalfria och har en hög gruppering av noder.

Den iterativa konstruktionen leder till ett hierarkiskt nätverk. Med utgångspunkt från ett fullt anslutet kluster med fem noder skapar vi fyra identiska repliker som förbinder perifera noder i varje kluster med den centrala noden i det ursprungliga klustret. Från detta får vi ett nätverk av 25 noder ( N  = 25). Genom att upprepa samma process kan vi skapa ytterligare fyra kopior av det ursprungliga klustret - de fyra perifera noderna för var och en ansluter till den centrala noden för noderna som skapades i det första steget. Detta ger N  = 125, och processen kan fortsätta på obestämd tid.

Fitnessmodell

Tanken är att länken mellan två hörn inte tilldelas slumpmässigt med en sannolikhet p lika för alla hörnpar. Snarare, för varje hörn j finns en inneboende kondition x _j och en länk mellan hörn i och j skapas med sannolikhet . När det gäller World Trade Web är det möjligt att rekonstruera alla fastigheter genom att använda landets fitness som BNP, och ta ${\ displaystyle p (x_ {i}, x_ {j})}$

${\ displaystyle p (x_ {i}, x_ {j}) = {\ frac {\ delta x_ {i} x_ {j}} {1+ \ delta x_ {i} x_ {j}}}.}$

Hyperboliska geometriska grafer

Förutsatt att ett nätverk har en underliggande hyperbolisk geometri kan man använda ramarna för rumsliga nätverk för att generera skalfria graddistributioner. Denna heterogena gradfördelning återspeglar då helt enkelt den negativa krökningen och de metriska egenskaperna hos den underliggande hyperboliska geometrin.

Edge dual transformation för att generera skalfria grafer med önskade egenskaper

Börjar med skalfria grafer med låg gradskorrelation och klusteringskoefficient kan man generera nya grafer med mycket högre gradskorrelationer och klusteringskoefficienter genom att tillämpa kant-dubbel transformation.

Uniform-preferens-bifogad modell (UPA-modell)

UPA -modellen är en variant av den preferentiella bilagningsmodellen (föreslagen av Pachon et al.) Som tar hänsyn till två olika anslutningsregler: en preferensfästningsmekanism (med sannolikhet 1 − p) som betonar de rika bli rikare systemet och ett enhetligt val (med sannolikhet p) för de senaste noder. Denna modifiering är intressant att studera robustheten hos det skalfria beteendet för examensfördelningen. Det bevisas analytiskt att den asymptotiskt makträttsliga examensfördelningen bevaras.

Skalfria idealiska nätverk

I nätverksteorins sammanhang är ett skalfritt idealnätverk ett slumpmässigt nätverk med en gradfördelning efter den skalfria ideala gasdensitetsfördelningen . Dessa nätverk kan återge stadsfördelningar och valresultat genom att reda ut storleksfördelningen för sociala grupper med informationsteori om komplexa nätverk när en konkurrensutsatt tillväxtprocess tillämpas på nätverket. I modeller av skalfria ideala nätverk är det möjligt att visa att Dunbars antal är orsaken till fenomenet som kallas " sex grader av separation ".

Nya egenskaper

För ett skalfritt nätverk med noder och power-law exponent är den inducerade subgrafen konstruerad av hörn med grader större än ett skalfritt nätverk med , nästan säkert . ${\ displaystyle n}$${\ displaystyle \ gamma> 3}$${\ displaystyle \ log {n} \ times \ log ^{*} {n}}$${\ displaystyle \ gamma '= 2}$

Se även

• Slumpmässig graf  - Graf som genereras av en slumpmässig process
• Erdős – Rényi -modell  - Två närbesläktade modeller för att generera slumpmässiga grafer
• Icke-linjär preferensbilaga
• Bose -Einstein -kondens (nätverksteori)
• Skalainvarians  - funktioner som inte ändras om längd eller energivågar multipliceras med en gemensam faktor
• Komplex nätverk-  Nätverk med icke-triviala topologiska funktioner
• Webbgraf
• Barabási – Albert modell
• Bianconi – Barabási -modell

Referenser

Vidare läsning

• Albert R .; Barabási A.-L. (2002). "Statistisk mekanik i komplexa nätverk" . Rev. Mod. Phys . 74 (1): 47–97. arXiv : kond-matta/0106096 . Bibcode : 2002RvMP ... 74 ... 47A . doi : 10.1103/RevModPhys.74.47 . S2CID  60545 .
• Amaral LAN, Scala A, Barthelemy M, Stanley HE (2000). "Klasser av småvärldsnätverk" . PNAS . 97 (21): 11149–52. arXiv : kond-matta/0001458 . Bibcode : 2000PNAS ... 9711149A . doi : 10.1073/pnas.200327197 . PMC  17168 . PMID  11005838 .
• Barabási, Albert-László (2004). Länkat: Hur allt är kopplat till allt annat . ISBN 0-452-28439-2.
• Barabási, Albert-László; Bonabeau, Eric (maj 2003). "Skalfria nätverk" (PDF) . Scientific American . 288 (5): 50–9. Bibcode : 2003SciAm.288e..60B . doi : 10.1038/scientificamerican0503-60 . PMID  12701331 .
• Dan Braha; Yaneer Bar-Yam (2004). "Topologi för storskaliga tekniska problemlösande nätverk" (PDF) . Phys. Rev. E . 69 (1): 016113. Bibcode : 2004PhRvE..69a6113B . doi : 10.1103/PhysRevE.69.016113 . PMID  14995673 . S2CID  1001176 .
• Caldarelli G. " Skalfria nätverk" Oxford University Press, Oxford (2007).
• Caldarelli G .; Capocci A .; De Los Rios P ​​.; Muñoz MA (2002). "Skalfria nätverk från varierande vertex intrinsic fitness". Fysiska granskningsbrev . 89 (25): 258702. arXiv : cond-mat/0207366 . Bibcode : 2002PhRvL..89y8702C . doi : 10.1103/PhysRevLett.89.258702 . PMID  12484927 .
• R. Cohen; K. Erez; D. ben-Avraham; S. Havlin (2000). "Internets motståndskraft mot slumpmässiga sammanbrott". Phys. Rev Lett . 85 (21): 4626–8. arXiv : kond-matta/0007048 . Bibcode : 2000PhRvL..85.4626C . doi : 10.1103/PhysRevLett.85.4626 . PMID  11082612 . S2CID  15372152 .
• R. Cohen; K. Erez; D. ben-Avraham; S. Havlin (2001). "Nedbrytning av Internet under avsiktlig attack". Phys. Rev Lett . 86 (16): 3682–5. arXiv : cond-mat/0010251 . Bibcode : 2001PhRvL..86.3682C . doi : 10.1103/PhysRevLett.86.3682 . PMID  11328053 . S2CID  3852896 .
• R. Cohen; K. Erez; D. ben-Avraham; S. Havlin (2002). "Skalfria nätverk på galler" . Phys. Rev Lett . 89 (21): 218701. arXiv : cond-mat/0205613 . Bibcode : 2002PhRvL..89u8701R . doi : 10.1103/physrevlett.89.218701 . PMID  12443452 . S2CID  13379794 .
• Dangalchev, Ch. (2004). "Generationsmodeller för skalfria nätverk" . Physica A . 338 (3–4): 659–671. Bibcode : 2004PhyA..338..659D . doi : 10.1016/j.physa.2004.01.056 .
• Dorogovtsev, SN; Mendes, JFF; Samukhin, AN (2000). "Struktur för växande nätverk: Exakt lösning av Barabási — Alberts modell". Phys. Rev Lett . 85 (21): 4633–6. arXiv : kond-matta/0004434 . Bibcode : 2000PhRvL..85.4633D . doi : 10.1103/PhysRevLett.85.4633 . PMID  11082614 .
• Dorogovtsev, SN; Mendes, JFF (2003). Utveckling av nätverk: från biologiska nätverk till Internet och WWW . Oxford University Press. ISBN 0-19-851590-1.
• Dorogovtsev, SN; Goltsev AV; Mendes, JFF (2008). "Kritiska fenomen i komplexa nätverk". Rev. Mod. Phys . 80 (4): 1275–1335. arXiv : 0705.0010 . Bibcode : 2008RvMP ... 80.1275D . doi : 10.1103/RevModPhys.80.1275 . S2CID  3174463 .
• Dorogovtsev, SN; Mendes, JFF (2002). "Utveckling av nätverk". Framsteg inom fysik . 51 (4): 1079–1187. arXiv : kond-matta/0106144 . Bibcode : 2002AdPhy..51.1079D . doi : 10.1080/00018730110112519 . S2CID  429546 .
• Erdős, P .; Rényi, A. (1960). Om utvecklingen av slumpmässiga grafer (PDF) . 5 . Publicering av Mathematical Institute of the Hungarian Academy of Science. s. 17–61.
• Faloutsos, M .; Faloutsos, P .; Faloutsos, C. (1999). "Om makträttsrelationer för internettopologin". Komp. Comm. Rev . 29 (4): 251–262. doi : 10.1145/316194.316229 .
• Li, L .; Alderson, D .; Tanaka, R .; Doyle, JC; Willinger, W. (2005). "Mot en teori om skalfria grafer: definition, egenskaper och konsekvenser (utökad version)". arXiv : kond-matta/0501169 .
• Kumar, R .; Raghavan, P .; Rajagopalan, S .; Sivakumar, D .; Tomkins, A .; Upfal, E. (2000). "Stokastiska modeller för webbgrafen" (PDF) . Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS) . Redondo Beach, CA: IEEE CS Press. s. 57–65.
• Matlis, Jan (4 november 2002). "Skalfria nätverk" .
• Newman, Mark EJ (2003). "Komplexa nätverks struktur och funktion". SIAM Review . 45 (2): 167–256. arXiv : kond-matta/0303516 . Bibcode : 2003SIAMR..45..167N . doi : 10.1137/S003614450342480 . S2CID  221278130 .
• Pastor-Satorras, R .; Vespignani, A. (2004). Utveckling och struktur på Internet: En statistisk fysikmetod . Cambridge University Press. ISBN 0-521-82698-5.
• Pennock, DM; Flake, GW; Lawrence, S .; Glover, EJ; Giles, CL (2002). "Vinnare tar inte allt: Karaktäriserar konkurrensen om länkar på webben" . PNAS . 99 (8): 5207–11. Bibcode : 2002PNAS ... 99.5207P . doi : 10.1073/pnas.032085699 . PMC  122747 . PMID  16578867 .
• Robb, John. Skalfria nätverk och terrorism , 2004.
• Keller, EF (2005). "Återbesöker" skalfria "nätverk" . BioEssays . 27 (10): 1060–8. doi : 10.1002/bies.20294 . PMID  16163729 . Arkiverad från originalet 2011-08-13.
• Onody, RN; de Castro, PA (2004). "Komplex nätverksstudie av brasiliansk fotbollsspelare". Phys. Rev. E . 70 (3): 037103. arXiv : kond-matta/0409609 . Bibcode : 2004PhRvE..70c7103O . doi : 10.1103/PhysRevE.70.037103 . PMID  15524675 . S2CID  31653489 .
• Reuven Cohen; Shlomo Havlin (2003). "Skalfria nätverk är ultraljud" . Phys. Rev Lett . 90 (5): 058701. arXiv : cond-mat/0205476 . Bibcode : 2003PhRvL..90e8701C . doi : 10.1103/PhysRevLett.90.058701 . PMID  12633404 . S2CID  10508339 .
• Kasthurirathna, D .; Piraveenan, M. (2015). "Komplex nätverksstudie av brasiliansk fotbollsspelare". Sci. Rep . I pressen.