Småvärldsnätverk - Small-world network

Småvärldens nätverksexempel
Hubbar är större än andra noder
Genomsnittlig grad = 3,833
Genomsnittlig kortaste väglängd = 1,803.
Klusteringskoefficient = 0,522
Slumpgraf
Genomsnittlig grad = 2,833
Genomsnittlig kortaste banlängden = 2,109.
Klusteringskoefficient = 0,167
Nätverksvetenskap
Internet_karta_1024.jpg
Nätverkstyper
Grafer
Funktioner
Typer
Modeller
Topologi
Dynamik
  • Listor
  • Kategorier

Ett småvärldsnätverk är en typ av matematisk graf där de flesta noder inte är grannar till varandra, men grannarna till en given nod är sannolikt grannar till varandra och de flesta noder kan nås från varannan nod med en liten antal humle eller steg. Specifikt definieras ett småvärldsnätverk som ett nätverk där det typiska avståndet L mellan två slumpmässigt valda noder (antalet steg som krävs) växer proportionellt mot logaritmen för antalet noder N i nätverket, det vill säga:

medan klusteringskoefficienten inte är liten. I samband med ett socialt nätverk resulterar detta i att den lilla världsfenomenet av främlingar kopplas samman med en kort kedja av bekanta . Många empiriska grafer visar småvärldens effekt, inklusive sociala nätverk , wikis som Wikipedia, gennätverk och till och med den underliggande arkitekturen på Internet . Det är inspirationen för många nätverk-på-chip- arkitekturer i modern datorhårdvara .

En viss kategori småvärldsnätverk identifierades som en klass av slumpmässiga grafer av Duncan Watts och Steven Strogatz 1998. De noterade att grafer kunde klassificeras enligt två oberoende strukturella egenskaper, nämligen klusteringskoefficienten och genomsnittlig nod-till- nod avstånd (även känd som genomsnittlig kortaste vägen längd). Rent slumpmässiga grafer, byggda enligt Erdős – Rényi (ER) -modellen , uppvisar en liten genomsnittlig kortaste väglängd (varierar vanligtvis som logaritmen för antalet noder) tillsammans med en liten klusteringskoefficient. Watts och Strogatz mätte att många verkliga nätverk faktiskt har en liten genomsnittlig kortaste väglängd, men också en klusterkoefficient som är betydligt högre än förväntat av slumpmässig slump. Watts och Strogatz föreslog sedan en ny grafmodell, som för närvarande heter Watts och Strogatz -modellen , med (i) en liten genomsnittlig kortaste väglängd och (ii) en stor klusterkoefficient. Korsningen i Watts – Strogatz -modellen mellan en "stor värld" (t.ex. ett galler) och en liten värld beskrevs först av Barthelemy och Amaral 1999. Detta arbete följdes av många studier, inklusive exakta resultat (Barrat och Weigt, 1999; Dorogovtsev och Mendes ; Barmpoutis och Murray, 2010). Braunstein et al fann att för viktade ER -nät där vikterna har en mycket bred fördelning blir de optimala vägvägarna betydligt längre och skala som  N 1/3 .

Egenskaper för småvärldsnätverk

Småvärldsnätverk tenderar att innehålla klickar och nära klick, vilket betyder subnätverk som har förbindelser mellan nästan alla två noder inom dem. Detta följer av den definierande egenskapen för en hög klusteringskoefficient . För det andra kommer de flesta par av noder att anslutas med minst en kort väg. Detta följer av den definierande egenskapen att den genomsnittligt kortaste banlängden är liten. Flera andra fastigheter är ofta förknippade med småvärldsnätverk. Vanligtvis finns det en over-överflöd av hubbar - noder i nätet med ett högt antal anslutningar (kända som hög grad noder). Dessa nav fungerar som de vanliga anslutningarna som förmedlar de korta banlängderna mellan andra kanter. I analogi har det lilla världsnätverket av flygflyg en liten medelvägslängd (dvs. mellan två städer som du sannolikt kommer att behöva ta tre eller färre flygningar) eftersom många flyg dirigeras genom navstäder . Denna egenskap analyseras ofta genom att ta hänsyn till fraktionen av noder i nätverket som har ett visst antal anslutningar som går in i dem (gradfördelningen av nätverket). Nätverk med ett större antal hubbar än förväntat kommer att ha en större andel noder med hög grad, och följaktligen kommer gradfördelningen att berikas med höga gradvärden. Detta är allmänt känt som en fettstjärtad fördelning . Diagram över mycket olika topologi kvalificerar sig som småvärldsnätverk så länge de uppfyller de två definitionskraven ovan.

Nätverkets lilla värld har kvantifierats med en liten koefficient, beräknad genom att jämföra klustering och väglängd för ett givet nätverk med ett ekvivalent slumpmässigt nätverk med samma grad i genomsnitt.

om ( och ) är nätverket en liten värld. Detta mått är dock känt för att fungera dåligt eftersom det påverkas starkt av nätverkets storlek.

En annan metod för att kvantifiera nätverks liten värld utnyttjar den ursprungliga definitionen av småvärldsnätet som jämför klusteringen av ett givet nätverk med ett ekvivalent gitternät och dess väglängd till ett ekvivalent slumpmässigt nätverk. Liten världsmått ( ) definieras som

Där den karakteristiska väglängden L och klusteringskoefficienten C beräknas från det nätverk du testar, är C cl grupperingskoefficienten för ett ekvivalent gitternät och L r är den karakteristiska väglängden för ett ekvivalent slumpmässigt nätverk.

Ytterligare en metod för att kvantifiera småvärlden normaliserar både nätverkets gruppering och väglängd i förhållande till dessa egenskaper i ekvivalenta gitter och slumpmässiga nätverk. Small World Index (SWI) definieras som

Både ω ′ och SWI ligger mellan 0 och 1, och har visat sig fånga aspekter av småvärlden. De antar dock lite olika uppfattningar om idealisk liten värld. För en viss uppsättning begränsningar (t.ex. storlek, densitet, gradfördelning) finns det ett nätverk för vilket ω ′ = 1, och därmed ω syftar till att fånga upp i vilken utsträckning ett nätverk med givna begränsningar är så litet världsligt som möjligt. Däremot finns det kanske inte ett nätverk för vilket SWI = 1, därmed SWI syftar till att fånga i vilken utsträckning ett nätverk med givna begränsningar närmar sig det teoretiska småvärldsidealet för ett nätverk där C ≈ C ℓ och L ≈ L r .

R. Cohen och Havlin visade analytiskt att skalfria nätverk är extremt små världar. I det här fallet, på grund av nav, blir de kortaste vägarna betydligt mindre och skalas som

Exempel på småvärldsnätverk

Småvärldsegenskaper finns i många verkliga fenomen, inklusive webbplatser med navigeringsmenyer, matbanor, elnät, metabolitbehandlingsnätverk, nätverk av hjärnneuroner , väljarnät, telefonsamtal, flygplatsnätverk och sociala nätverk. Kulturella nätverk, semantiska nätverk och nätverkssamverkan har också visat sig vara småvärldsnätverk.

Nätverk av anslutna proteiner har små världsegenskaper, såsom power-law som lyder examensfördelningar. På samma sätt har transkriptionella nätverk , där noderna är gener , och de är länkade om den ena genen har ett upp- eller nedreglerande genetiskt inflytande på den andra, har små världsnätverksegenskaper.

Exempel på icke-småvärldsnätverk

I ett annat exempel, den berömda teorin om " sex grader av separation " mellan människor tyst förutsätter att domän diskursen är den uppsättning av människor vid liv vid något tillfälle. Antalet separationsgrader mellan Albert Einstein och Alexander den store är nästan säkert större än 30 och detta nätverk har inte småvärldsegenskaper. Ett liknande begränsat nätverk skulle vara "gick till skolan med" -nätverket: om två personer gick på samma högskola med tio års mellanrum, är det osannolikt att de har bekanta gemensamt bland studentgruppen.

På samma sätt var antalet relästationer genom vilka ett meddelande måste passera inte alltid litet. Under de dagar då posten fördes för hand eller till häst, hade antalet gånger en bokstav bytt ägare mellan dess källa och destination varit mycket större än den är idag. Antalet gånger ett meddelande bytte ägare under den visuella telegrafens dagar (cirka 1800–1850) bestämdes av kravet på att två stationer skulle anslutas med siktlinje.

Tysta antaganden, om de inte undersöks, kan orsaka en snedvridning i litteraturen om grafer till förmån för att hitta småvärldsnätverk (ett exempel på fillådseffekten som härrör från publiceringsförspänningen ).

Nätverkets robusthet

Det antas av vissa forskare, som Barabási , att förekomsten av små världsnätverk i biologiska system kan återspegla en evolutionär fördel med en sådan arkitektur. En möjlighet är att små världens nätverk är mer robusta mot störningar än andra nätverksarkitekturer. Om så vore fallet skulle det ge en fördel för biologiska system som kan skadas av mutation eller virusinfektion .

I ett litet världsnätverk med en gradfördelning efter en power-law orsakar radering av en slumpmässig nod sällan en dramatisk ökning av medelkortaste väglängden (eller en dramatisk minskning av grupperingskoefficienten ). Detta följer av det faktum att de kortaste vägarna mellan noder flödar genom nav , och om en perifer nod raderas är det osannolikt att den stör störningar mellan andra perifera noder. Eftersom andelen perifera noder i ett litet världsnätverk är mycket högre än fraktionen av hubbar , är sannolikheten för att radera en viktig nod mycket låg. Till exempel, om den lilla flygplatsen i Sun Valley, Idaho stängdes, skulle det inte öka det genomsnittliga antalet flygningar som andra passagerare som reser i USA skulle behöva ta för att komma fram till sina respektive destinationer. Men om slumpmässig radering av en nod träffar ett nav av en slump kan den genomsnittliga banlängden öka dramatiskt. Detta kan observeras årligen när norra navflygplatser, som Chicagos O'Hare -flygplats , stängs av på grund av snö; många människor måste ta ytterligare flyg.

Däremot, i ett slumpmässigt nätverk, där alla noder har ungefär samma antal anslutningar, kommer radering av en slumpmässig nod sannolikt att öka den medelkortaste banlängden något men betydligt för nästan vilken nod som helst som raderas. I den meningen är slumpmässiga nätverk sårbara för slumpmässiga störningar, medan småvärldsnätverk är robusta. Små världsnätverk är dock sårbara för riktade attacker av hubbar, medan slumpmässiga nätverk inte kan riktas mot katastrofalt misslyckande.

På lämpligt sätt har virus utvecklats för att störa aktiviteten hos navproteiner såsom p53 , och därigenom åstadkomma de massiva förändringarna i cellulärt beteende som bidrar till viral replikation. En användbar metod för att analysera nätverkets robusthet är perkolationsteorin .

Byggande av småvärldsnätverk

Se även: Diffusionsbegränsad aggregering och mönsterbildning

Huvudmekanismen för att bygga småvärldsnätverk är Watts – Strogatz-mekanismen .

Småvärldsnätverk kan också introduceras med tidsfördröjning, vilket inte bara kommer att producera fraktaler utan också kaos under rätt förhållanden, eller övergång till kaos i dynamiska nätverk.

Grafer -diameterdiagram är konstruerade så att antalet grannar som varje hörn i nätverket har är begränsat, medan avståndet från en viss hörnpunkt i nätverket till någon annan toppunkt ( nätverkets diameter ) minimeras. Att bygga sådana småvärldsnätverk görs som en del av ansträngningen att hitta ordningsgrafer nära Moore-gränsen .

Ett annat sätt att bygga ett litet världsnätverk från grunden ges i Barmpoutis et al. , där ett nätverk med mycket litet medelavstånd och mycket stort genomsnittligt kluster konstrueras. En snabb algoritm med konstant komplexitet ges tillsammans med mätningar av robustheten hos de resulterande graferna. Beroende på tillämpningen av varje nätverk kan man börja med ett sådant "ultra small-world" -nätverk och sedan koppla om några kanter, eller använda flera små sådana nätverk som subgrafer till ett större diagram.

Småvärldsfastigheter kan uppstå naturligt i sociala nätverk och andra verkliga system via processen med tvåfasutveckling . Detta är särskilt vanligt när tids- eller rumsliga begränsningar begränsar tillägget av förbindelser mellan hörn. Mekanismen innebär vanligtvis periodiska skift mellan faser, med anslutningar som läggs till under en "global" fas och förstärks eller tas bort under en "lokal" fas.

Småvärldsnätverk kan förändras från skalfri klass till storskalig klass vars anslutningsfördelning har en kraftig avstängning efter en kraftlagsregim på grund av begränsningar som begränsar tillägget av nya länkar. För tillräckligt starka begränsningar kan skalfria nätverk till och med bli enskaliga nätverk vars anslutningsfördelning kännetecknas av en snabb förfall.

Liten värld med en fördelning av länklängd

SW-modellen innehåller en enhetlig fördelning av långdistanslänkar. När fördelningen av länklängder följer en kraftlagsfördelning ändras medelavståndet mellan två platser beroende på fördelningens effekt.

Ansökningar

Ansökningar till sociologi

Fördelarna med småvärldsnätverk för sociala rörelsegrupper är deras motståndskraft mot förändringar på grund av filtreringsapparaten för att använda mycket anslutna noder, och dess bättre effektivitet för att vidarebefordra information samtidigt som antalet länkar som krävs för att ansluta ett nätverk till ett minimum hålls.

Den lilla världens nätverksmodell är direkt tillämplig på affinitetsgruppsteori som representeras i sociologiska argument av William Finnegan . Affinitetsgrupper är sociala rörelsegrupper som är små och halvoberoende lovade till ett större mål eller en större funktion. Även om de i stort sett inte är anslutna på nodnivå, fungerar några medlemmar av hög anslutning som anslutningsnoder, som länkar de olika grupperna via nätverk. Denna lilla världsmodell har visat sig vara en extremt effektiv protestorganisationstaktik mot polisens agerande. Clay Shirky hävdar att ju större det sociala nätverket skapas genom småvärldsnätverk, desto mer värdefulla noder för hög anslutning inom nätverket. Detsamma kan sägas om affinitetsgruppsmodellen, där de få personerna inom varje grupp som är anslutna till externa grupper möjliggjorde en stor mängd mobilisering och anpassning. Ett praktiskt exempel på detta är små världsnätverk genom affinitetsgrupper som William Finnegan skisserar med hänvisning till Seattle WTO -protesterna 1999 .

Tillämpningar inom geovetenskap

Många nätverk som studerats inom geologi och geofysik har visat sig ha egenskaper hos småvärldsnätverk. Nätverk definierade i spricksystem och porösa ämnen har visat dessa egenskaper. Det seismiska nätverket i södra Kalifornien kan vara ett nätverk med liten värld. Exemplen ovan uppträder på mycket olika rumsliga skalor, vilket visar skala invarians av fenomenet i geovetenskap. Klimatnät kan betraktas som små världsnätverk där länkarna är av olika längd.

Applikationer till datorer

Små världsnätverk har använts för att uppskatta användbarheten av information som lagras i stora databaser. Åtgärden kallas Small World Data Transformation Measure. Ju större databaslänkarna anpassas till ett småvärldsnätverk, desto mer sannolikt kommer en användare att kunna extrahera information i framtiden. Denna användbarhet kommer vanligtvis att kosta mängden information som kan lagras i samma arkiv.

Den Freenets peer-to-peer-nätverk har visat sig bilda en liten-world nätverk i simulering, vilket tillåter information som skall lagras och hämtas på ett sätt som skalor effektivitet eftersom nätverket växer.

Småvärda neurala nätverk i hjärnan

Både anatomiska förbindelser i hjärnan och synkroniseringsnätverk av kortikala neuroner uppvisar liten världstopologi.

Strukturell och funktionell anslutning i hjärnan har också visat sig återspegla den lilla världens topologi med kort väglängd och hög gruppering. Nätverksstrukturen har hittats i däggdjursbarken över arter såväl som i storskaliga avbildningsstudier på människor. Framsteg inom connectomics och nätverksneurovetenskap har funnit att neurala nätverks liten värld är förknippad med effektiv kommunikation.

I neurala nätverk stöder kort väglängd mellan noder och hög gruppering vid nätverksnav effektiv kommunikation mellan hjärnregioner till den lägsta energikostnaden. Hjärnan bearbetar och anpassar sig ständigt till ny information och små världens nätverksmodell stöder de intensiva kommunikationskraven hos neurala nätverk. Hög gruppering av noder bildar lokala nätverk som ofta är funktionellt relaterade. Kort väglängd mellan dessa nav stöder effektiv global kommunikation. Denna balans möjliggör effektiviteten i det globala nätverket samtidigt som hjärnan utrustas för att hantera störningar och upprätthålla homeostas, på grund av att lokala undersystem är isolerade från det globala nätverket. Förlust av liten världs nätverksstruktur har visat sig indikera förändringar i kognition och ökad risk för psykiska störningar.

Förutom att känneteckna helhjärnans funktionella och strukturella anslutning, uppvisar specifika neurala system, såsom det visuella systemet, småvärldsnätverk.

Ett småvärldsnätverk av neuroner kan uppvisa korttidsminne . En datormodell utvecklad av Solla et al. hade två stabila tillstånd, en egenskap (kallad bistabilitet ) som tros vara viktig för minneslagring . En aktiverande puls genererade självbärande loopar av kommunikationsaktivitet bland neuronerna. En andra puls avslutade denna aktivitet. Pulserna växlade systemet mellan stabila tillstånd: flöde (registrerar ett "minne") och stasis (håller det). Små världens neuronala nätverk har också använts som modeller för att förstå anfall .

Se även

Referenser

Vidare läsning

Böcker

Tidskriftsartiklar

externa länkar