Udviklende netværk

Voksende netværk er netværk, der ændrer som en funktion af tiden. De er en naturlig forlængelse af netværk videnskab da næsten alle virkelige verden netværk udvikle sig over tid, enten ved at tilføje eller fjerne knuder eller links over tid. Ofte er alle disse processer optræder samtidigt, såsom i sociale netværk, hvor folk gør og mister venner over tid og dermed skabe og ødelægge kanter, og nogle mennesker bliver en del af nye sociale netværk eller lade deres netværk, ændre knudepunkterne i netværket. Udviklende netværk koncepter bygger på etablerede netværk teori og bliver nu indført i studere netværk på mange forskellige områder.

Netværk teori baggrund

Studiet af netværk spore sine fonde til udvikling af grafteori, som først blev analyseret af Leonhard Euler i 1736, da han skrev de berømte königsbergs syv broer papir. Probabilistisk netværk teori derefter udviklet med hjælp fra otte berømte papirer studerer tilfældige grafer skrevet af Paul Erdős og Alfréd Renyi. Den Erdős-Renyi model forudsætter, at en graf er sammensat af N mærkede knudepunkter, hvor hvert par af knudepunkter er forbundet ved hjælp af en forudindstillet sandsynlighed p.

Mens ER modellens enkelhed har hjulpet den finde mange applikationer, er det ikke præcist beskriver mange virkelige verden netværk. ER-modellen ikke generere lokale klyngedannelse og triade lukninger så ofte, som de findes i den virkelige verden netværk. Derfor blev Watts og Strogatz model foreslået, hvor et netværk er konstrueret som en almindelig ring gitter, og derefter knudepunkter er rewired ifølge nogle sandsynlighed β. Dette giver en lokalt grupperet netværk og drastisk reducerer den gennemsnitlige vejlængde, skabe netværk, som repræsenterer den lille verden fænomen observeret i mange virkelige verden netværk.

Trods denne præstation, både ER og Watts og Storgatz modeller undlader at redegøre for formuleringen af ​​knudepunkter som observeret i mange virkelige verden netværk. Graden fordeling i ER-modellen følger en Poisson-fordeling, mens Watts og Strogatz model producerer grafer, der er homogene i grad. Mange netværk er stedet skalere fri, hvilket betyder, at deres grad fordeling følger en magt lov af formen:

Denne eksponent viser sig imidlertid at være ca. 3 for mange virkelige verden net, det er ikke en universel konstant og afhænger kontinuerligt på netværkets parametre

Først udviklende netværksmodel - skala gratis netværk

Den Barabasi-Albert model var den første bredt accepteret model til at producere skalafrie netværk. Dette blev opnået ved at inkorporere præferentiel binding og vækst, hvor knudepunkterne er føjet til netværket over tid og er mere tilbøjelige til at linke til andre knudepunkter med høj grad distributioner. BA model blev først anvendt på grad distributioner på nettet, hvor begge disse effekter kan tydeligt ses. Nye websider tilsættes over tid, og hver ny side er mere tilbøjelige til at linke til meget synlige knudepunkter som Google, der har høje grad fordelinger, end til knudepunkter med kun et par links. Formelt denne præferentielle vedhæftede fil er:

Tilføjelser til BA-model

BA model var den første model til at udlede netværkstopologien fra den måde, hvorpå netværket blev konstrueret med knudepunkter og links bliver tilføjet over tid. Men modellen gør kun de simpleste antagelser er nødvendige for en skala-frie net at dukke op, nemlig at der er lineær vækst og lineær præferentiel binding. Denne minimale model ikke fange variationer i form af graden distribution, variationer i graden eksponent, eller størrelsen uafhængige klyngedannelse koefficient. Derfor har den oprindelige model siden blevet ændret til mere fuldt ud at fange egenskaber udviklende netværk ved at indføre et par nye egenskaber.

Fitness

En bekymring med BA-modellen er, at graden fordelinger af hver noder oplever stærk positiv feedback, hvorved de tidligste noder med høj grad distributioner fortsat dominerer netværket på ubestemt tid. Dette kan imidlertid afhjælpes ved at indføre en egnethed til hvert knudepunkt, som ændrer sandsynligheden for nye forbindelser, der er oprettet med det pågældende knudepunkt eller endog links til det pågældende knudepunkt bliver fjernet.

For at bevare den præferentielle binding fra BA modellen, er denne fitness derefter multipliceret med den præferentielle binding baseret på graden distribution til opnåelse af den sande sandsynlighed for, at en forbindelse oprettes der forbinder til knudepunktet i.

Hvor er egnethed, som også kan afhænge af tiden. En henfald af fitness med hensyn til tid kan forekomme og kan formaliseres ved:

Hvor stiger med

Fjernelse noder og rewiring links

Yderligere komplikationer opstår, fordi knudepunkter kan fjernes fra netværket med en vis sandsynlighed. Derudover kan eksisterende forbindelser blive ødelagt og kan skabes nye forbindelser mellem eksisterende noder. Sandsynligheden for disse handlinger forekommer kan afhænge af tiden og kan også være relateret til node egnethed. Sandsynligheder kan tildeles disse begivenheder ved at studere egenskaberne af netværket pågældende for at vokse en model netværk med identiske egenskaber. Denne vækst vil finde sted med en af ​​følgende handlinger, der forekommer på hver gang trin:

Prob p: tilføj et internt link.

Prob q: slette et link.

Prob r: slette en node.

Prob 1-p-q-r: tilføje en node.

Andre måder at karakterisere udviklende netværk

Ud over voksende netværk modeller som beskrevet ovenfor, kan der være tidspunkter, hvor andre metoder er mere nyttigt eller praktisk til at karakterisere visse egenskaber ved voksende netværk.

Behandl udviklende netværk som successive snapshots af en statisk netværk

Den mest almindelige måde at se voksende netværk er ved at betragte dem som successive statiske netværk. Dette kunne konceptualiseres som de individuelle stillbilleder, der komponere en spillefilm. Mange simple parametre eksisterer for at beskrive en statisk netværk eller til at beskrive specifikke knuder i grafen, såsom antallet af links eller klyngedannelse koefficient. Disse egenskaber kan så individuelt studeres som en tidsserie ved hjælp af signalbehandling begreber. For eksempel kan vi spore antallet af links, der er etableret til en server per minut ved at se på de successive snapshots af netværket og tælle disse links i hvert snapshot.

Desværre analogien af ​​snapshots til en film afslører også den vigtigste problemer med denne tilgang: den tid skridt anvendte meget sjældent foreslået af netværket og er i stedet vilkårlige. Brug ekstremt små tidsskridt mellem hvert snapshot bevarer opløsning, men kan faktisk obskure bredere tendenser, som først bliver synlige over længere tidshorisonter. Omvendt anvendelse af større tidsskalaer mister tidsmæssige rækkefølge inden for hver snapshot. Derfor kan det være svært at finde den passende tidsfrister for at opdele udviklingen af ​​et netværk i statiske snapshots.

Definer dynamiske egenskaber

Det kan være vigtigt at se på egenskaber, som ikke direkte kan observeres ved at behandle udviklende netværk som en sekvens af øjebliksbilleder, såsom varigheden af ​​kontakter mellem noder kan defineres andre lignende egenskaber, og så er det muligt at i stedet spore disse egenskaber gennem evolution af et netværk og visualisere dem direkte.

Et andet problem med at bruge på hinanden snapshots er, at kun små ændringer i netværkstopologi kan have store effekter på udfaldet af algoritmer designet til at finde fællesskaber. Derfor er det nødvendigt at anvende en ikke klassisk definition af samfund, der tillader efter udviklingen i samfundet gennem et sæt regler, såsom fødsel, død, flette, split, vækst og sammentrækning.

Applikationer

Næsten alle virkelige verden netværk udvikler netværk, da de er bygget over tid. Ved at variere de respektive sandsynligheder beskrevet ovenfor, er det muligt at anvende den udvidede model BA til at konstruere et netværk med næsten identiske egenskaber som mange observerede netværk. Desuden er begrebet skala fri netværk viser os, at tid evolution er en nødvendig del af at forstå netværkets egenskaber, og at det er vanskeligt at modellere et eksisterende netværk som værende skabt øjeblikkeligt. Rigtige udviklende netværk, som er ved at blive undersøgt omfatter sociale netværk, kommunikationsnet, internettet, film skuespiller netværk, world wide web, og transportnetværk.

Yderligere læsning

  • "Om Netværk Videnskab," The New Science of Networks ", A.-L. Barabasi Perseus Udgivelse, Cambridge.
  • "Udviklingen Netværk Analyse: En Survey", ACM Computing Surveys, 2014.
  0   0
Forrige artikel En Milli
Næste artikel Benson House

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha