Kompleks nettverk - Complex network

"Komplekse nettverk" omdirigerer her. For selskapet, se Komplekse nettverk .
Nettverksvitenskap
Internett_kart_1024.jpg
Nettverkstyper
Grafer
Funksjoner
Typer
Modeller
Topologi
Dynamikk
  • Lister
  • Kategorier

I sammenheng med nettverksteori er et komplekst nettverk en graf (nettverk) med ikke-trivielle topologiske trekk-funksjoner som ikke forekommer i enkle nettverk som gitter eller tilfeldige grafer, men som ofte forekommer i nettverk som representerer virkelige systemer. Studiet av komplekse nettverk er et ungt og aktivt forskningsområde (siden 2000) inspirert i stor grad av empiriske funn fra virkelige nettverk som datanettverk , biologiske nettverk , teknologiske nettverk, hjernenettverk , klimanettverk og sosiale nettverk .

Definisjon

De fleste sosiale , biologiske og teknologiske nettverk viser betydelige ikke-trivielle topologiske trekk, med forbindelsesmønstre mellom elementene som verken er helt vanlige eller rent tilfeldige. Slike funksjoner omfatter en tung hale i den grad fordeling , en høy gruppering koeffisient , assortativity eller disassortativity blant ekser, fellesskap struktur , og hierarkisk struktur . I tilfelle av dirigerte nettverk inkluderer disse funksjonene også gjensidighet , triadens signifikansprofil og andre funksjoner. I kontrast viser mange av de matematiske modellene for nettverk som har blitt studert tidligere, for eksempel gitter og tilfeldige grafer , ikke disse funksjonene. De mest komplekse strukturene kan realiseres av nettverk med et middels antall interaksjoner. Dette tilsvarer det faktum at maksimalt informasjonsinnhold ( entropi ) er oppnådd for middels sannsynlighet.

To kjente og mye studerte klasser av komplekse nettverk er skalafrie nettverk og småverdenenettverk , hvis oppdagelse og definisjon er kanoniske casestudier i feltet. Begge er preget av spesifikke strukturelle trekk- makt-jus- gradfordelinger for førstnevnte og korte sti-lengder og høy klynging for sistnevnte. Siden studiet av komplekse nettverk har fortsatt å vokse i betydning og popularitet, har også mange andre aspekter ved nettverksstrukturer tiltrukket seg oppmerksomhet.

Nylig har studiet av komplekse nettverk blitt utvidet til nettverk av nettverk. Hvis disse nettverkene er avhengige av hverandre , blir de betydelig mer sårbare enn enkeltnettverk for tilfeldige feil og målrettede angrep og viser kaskaderingsfeil og første-ordens perkoleringsoverganger.

Videre har den kollektive oppførselen til et nettverk i nærvær av noder svikt og gjenoppretting blitt studert. Det er funnet at et slikt nettverk kan ha spontane feil og spontane gjenoppretting.

Feltet fortsetter å utvikle seg i et raskt tempo, og har samlet forskere fra mange områder, inkludert matematikk , fysikk , elektriske kraftsystemer, biologi , klima , informatikk , sosiologi , epidemiologi og andre. Ideer og verktøy fra nettverksvitenskap og ingeniørfag har blitt brukt til analyse av metabolske og genetiske regulatoriske nettverk; studiet av økosystemets stabilitet og robusthet; klinisk vitenskap; modellering og design av skalerbare kommunikasjonsnettverk som generering og visualisering av komplekse trådløse nettverk; utvikling av vaksinasjonsstrategier for kontroll av sykdom; og et bredt spekter av andre praktiske problemstillinger. En anmeldelse av anvendelse av nettverk for geologi har nylig blitt publisert. Nettverksteori har også nylig blitt funnet nyttig for å identifisere flaskehalser i bytrafikk. Nettverksvitenskap er tema for mange konferanser på en rekke forskjellige felt, og har vært gjenstand for mange bøker både for lekmannen og for eksperten.

Skalafrie nettverk

Hovedartikkel: Skalafrie nettverk
Fig. 1: Et eksempel på komplekse skalafrie nettverk.

Et nettverk kalles skalafritt hvis gradfordelingen, dvs. sannsynligheten for at en node som er valgt jevnt tilfeldig har et visst antall lenker (grad), følger en matematisk funksjon som kalles en kraftlov . Maktloven innebærer at gradfordelingen av disse nettverkene ikke har noen karakteristisk skala. I kontrast er nettverk med en enkelt veldefinert skala noe som ligner et gitter ved at hver node har (omtrent) samme grad. Eksempler på nettverk med en enkelt skala inkluderer Erdős - Rényi (ER) tilfeldig graf , tilfeldige vanlige grafer , vanlige gitter og hyperkuber . Noen modeller for voksende nettverk som produserer skala-invariante gradfordelinger er Barabási-Albert-modellen og treningsmodellen . I et nettverk med en skalafri gradfordeling har noen hjørner en grad som er størrelsesordener større enn gjennomsnittet - disse hjørnene kalles ofte "knutepunkter", selv om dette språket er misvisende, ettersom det per definisjon ikke er noen terskel over hvilken en node kan ses som et knutepunkt. Hvis det var en slik terskel, ville ikke nettverket vært skalafritt.

Interessen for skalafrie nettverk begynte på slutten av 1990-tallet med rapportering om funn av makt-lov-distribusjoner i virkelige nettverk som World Wide Web , nettverket av autonome systemer (AS), noen nettverk av Internett-rutere, proteininteraksjon nettverk, e-postnettverk, etc. De fleste av disse rapporterte "maktlovene" mislykkes når de blir utfordret med strenge statistiske tester, men den mer generelle ideen om tunge haleutdelinger-som mange av disse nettverkene virkelig viser (før endelige effekter oppstår ) - er veldig forskjellige fra hva man ville forvente hvis kanter eksisterte uavhengig og tilfeldig (dvs. hvis de fulgte en Poisson -fordeling ). Det er mange forskjellige måter å bygge et nettverk med en makt-jus grad fordeling. Den Yule prosessen er en kanonisk generative prosess for potenslov, og har vært kjent siden 1925. Men det er kjent av mange andre navn på grunn av sin hyppige gjenoppfinnelse, for eksempel, den Gibrat prinsippet av Herbert Simon , den Matthew effekt , kumulativ fordel og, fortrinnsvis vedlegg av Barabási og Albert for maktrettsfordelinger . Nylig har hyperboliske geometriske grafer blitt foreslått som enda en måte å konstruere skalafrie nettverk på. En nylig gjennomgang av nettverksgeometri har blitt presentert av Boguna et al.

Noen nettverk med en power-law gradfordeling (og spesifikke andre typer strukturer) kan være svært motstandsdyktige mot tilfeldig sletting av hjørner-det vil si at de aller fleste hjørnene forblir koblet sammen i en gigantisk komponent. Slike nettverk kan også være ganske følsomme for målrettede angrep som tar sikte på å bryte nettverket raskt. Når grafen er jevnt tilfeldig bortsett fra gradfordelingen, er disse kritiske hjørnene de med høyest grad, og har dermed blitt implisert i spredning av sykdom (naturlig og kunstig) i sosiale og kommunikasjonsnettverk og i spredning av moter. (som begge er modellert av en perkolasjons- eller forgreningsprosess ). Mens tilfeldige grafer (ER) har en gjennomsnittlig avstand for ordenslogg N mellom noder, hvor N er antall noder, kan skala fri graf ha en avstand til logglogg N. Slike grafer kalles ultra -småverdenettverk.

Småverdenenettverk

Hovedartikkel: Small-world network

Et nettverk kalles et småverdenettverk analogt med fenomenet i liten verden (populært kjent som seks grader av separasjon ). Den lille verdenshypotesen, som først ble beskrevet av den ungarske forfatteren Frigyes Karinthy i 1929, og testet eksperimentelt av Stanley Milgram (1967), er ideen om at to vilkårlige mennesker bare er forbundet med seks grader av separasjon, det vil si diameteren til den tilsvarende graf over sosiale forbindelser er ikke mye større enn seks. I 1998 publiserte Duncan J. Watts og Steven Strogatz den første lilleverdenen nettverksmodellen, som gjennom en enkelt parameter jevnt interpolerer mellom en tilfeldig graf og et gitter. Modellen deres viste at med tillegg av bare et lite antall langdistanse lenker, kan en vanlig graf, der diameteren er proporsjonal med størrelsen på nettverket, omdannes til en "liten verden" der gjennomsnittlig antall kantene mellom to hjørner er veldig små (matematisk sett bør den vokse som logaritmen til størrelsen på nettverket), mens grupperingskoeffisienten forblir stor. Det er kjent at et stort utvalg av abstrakte grafer viser eiendommen til den lille verden, f.eks. Tilfeldige grafer og skalafrie nettverk. Videre viser den virkelige verdenen nettverk som World Wide Web og det metabolske nettverket også denne eiendommen.

I den vitenskapelige litteraturen om nettverk er det en viss uklarhet knyttet til begrepet "liten verden". I tillegg til å referere til størrelsen på diameteren på nettverket, kan det også referere til samtidig forekomst av en liten diameter og en høy grupperingskoeffisient . Klyngekoeffisienten er en beregning som representerer tettheten av trekanter i nettverket. For eksempel har sparsomme tilfeldige grafer en forsvinnende liten grupperingskoeffisient, mens virkelige nettverk ofte har en koeffisient som er betydelig større. Forskere peker på denne forskjellen som antyder at kanter er korrelert i virkelige nettverk.

Romlige nettverk

Hovedartikkel: Romlig nettverk

Mange virkelige nettverk er innebygd i verdensrommet. Eksempler inkluderer transport og andre infrastrukturnettverk, hjernenettverk. Flere modeller for romlige nettverk er utviklet.

Romlige modulære nettverk

Fig. 2: Illustrasjon av modellen. Den heterogene romlige modulmodellen representerer en struktur av et nettverk inne i byer og mellom byer. Inne i en by er det enkelt å komme seg fra et sted til et annet (grønne koblinger) som Erdős - Rényi -nettverk som har tilfeldig lignende struktur, mens det vanligvis er mulig å reise fra en by til en annen mellom nabobyer som har romlig struktur (blå lenker).

En modell for romlig modulære nettverk er utviklet av Gross et al. Modellen beskriver f.eks. Infrastrukturer i et land der lokalsamfunn (moduler) representerer byer med mange forbindelser plassert i todimensjonalt rom. Koblingen mellom lokalsamfunn (byer) er mindre og vanligvis til nærmeste naboer (se fig. 2).

Se også

Bøker

  • BS Manoj, Abhishek Chakraborty og Rahul Singh, Complex Networks: A Networking and Signal Processing Perspective , Pearson, New York, USA, februar 2018. ISBN  978-0134786995
  • SN Dorogovtsev og JFF Mendes, evolusjon av nettverk: Fra biologiske nettverk til Internett og WWW , Oxford University Press, 2003, ISBN  0-19-851590-1
  • Duncan J. Watts, Six Degrees: The Science of a Connected Age , WW Norton & Company, 2003, ISBN  0-393-04142-5
  • Duncan J. Watts, Small Worlds: The Dynamics of Networks between Order and Randomness , Princeton University Press, 2003, ISBN  0-691-11704-7
  • Albert-László Barabási, lenket: Hvordan alt er koblet til alt annet , 2004, ISBN  0-452-28439-2
  • Alain Barrat, Marc Barthelemy, Alessandro Vespignani, Dynamiske prosesser på komplekse nettverk , Cambridge University Press, 2008, ISBN  978-0-521-87950-7
  • Stefan Bornholdt (redaktør) og Heinz Georg Schuster (redaktør), Handbook of Graphs and Networks: From the Genom to the Internet , 2003, ISBN  3-527-40336-1
  • Guido Caldarelli, skalafrie nettverk , Oxford University Press, 2007, ISBN  978-0-19-921151-7
  • Guido Caldarelli, Michele Catanzaro, Networks: A Very Short Introduction Oxford University Press, 2012, ISBN  978-0-19-958807-7
  • E. Estrada, "The Structure of Complex Networks: Theory and Applications", Oxford University Press, 2011, ISBN  978-0-199-59175-6
  • Reuven Cohen og Shlomo Havlin, Komplekse nettverk: Struktur, robusthet og funksjon , Cambridge University Press, 2010, ISBN  978-0-521-84156-6
  • Mark Newman, Networks: An Introduction , Oxford University Press, 2010, ISBN  978-0-19-920665-0
  • Mark Newman, Albert-László Barabási og Duncan J. Watts, The Structure and Dynamics of Networks , Princeton University Press, Princeton, 2006, ISBN  978-0-691-11357-9
  • R. Pastor-Satorras og A. Vespignani, Evolution and Structure of the Internet: A statistical physics approach , Cambridge University Press, 2004, ISBN  0-521-82698-5
  • Lewis, Network Science, Wiley 2009,
  • Niloy Ganguly (redaktør), Andreas Deutsch (redaktør) og Animesh Mukherjee (redaktør), Dynamics On and Of Complex Networks Applications to Biology, Computer Science, and the Social Sciences , 2009, ISBN  978-0-8176-4750-6
  • Vito Latora, Vincenzo Nicosia, Giovanni Russo, komplekse nettverk: prinsipper, metoder og applikasjoner , Cambridge University Press, 2017, ISBN  978-1107103184

Referanser