Liten värld (greve)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 mars 2022; kontroller kräver 15 redigeringar .

Small World-grafen (liten värld)  är en sorts graf som har följande egenskap: om vi tar två godtyckliga hörn a och b , så är de troligen inte intill varandra, men den ena kan nås från den andra genom ett litet antal övergångar genom andra hörn. "Small World"-grafen definieras nämligen som ett nätverk där det typiska avståndet L mellan två godtyckligt valda hörn (antalet steg som krävs för att nå den ena från den andra) växer i proportion till logaritmen av antalet hörn N i nätverket, alltså [1] :

,

men den globala klustringskoefficienten är inte liten. [2]

I samband med ett socialt nätverk leder detta till fenomenet "lilla världen", det vill säga främlingar är sammankopplade med ett litet antal mellanliggande bekanta. Många verkliga grafer är väl modellerade genom Small World-grafer. Sociala nätverk, Internetanslutning, wikis som Wikipedia och gennätverk uppvisar egenskaperna hos "Small World"-grafen. Duncan Watts och Stephen Strogatz identifierade 1998 en viss kategori av "Small World"-grafer som en klass av slumpmässiga grafer [1] . De noterade att sådana grafer kan klassificeras enligt två oberoende strukturella egenskaper, nämligen klustringskoefficienten och det genomsnittliga avståndet från en vertex till en annan (även känd som den genomsnittliga kortaste väglängden ). Helt slumpmässiga grafer byggda i enlighet med Erdős-Rényi-modellen har en liten kortaste väglängd i genomsnitt (den växer som en logaritm av antalet hörn i grafen) och en liten klusteringskoefficient. Watts och Strogatz fann att de flesta verkliga nätverk har en kortast kortast väglängd i genomsnitt, men deras klustringskoefficient är betydligt högre än förväntat av slumpmässigt urval. Efter det föreslog Watts och Strogatz en ny grafmodell, nu kallad Watts-Strogatz-modellen , som kännetecknas av (i) en liten genomsnittlig kortaste väglängd och (ii) en stor klusteringskoefficient. Skärningen i Watts och Strogatz-modellen mellan den "stora världen" (som en gittergraf) och den lilla världen beskrevs första gången av Bartelmy och Amaral 1999 [3] . Detta arbete följdes av ett stort antal studier [4] [5] [6] .

Egenskaper för "Small World"-grafen

Small World-grafer tenderar att innehålla klicker och nära-klickar, som är undernät som har kopplingar mellan nästan alla hörn i dem. Detta följer av definitionen av en sådan grafegenskap som en hög klusteringskoefficient . För det andra kommer de flesta hörnpar att vara sammankopplade med minst en kort väg. Mer strikt är det genomsnittliga avståndet från en vertex till en annan (även känd som den genomsnittliga kortaste väglängden ) relativt liten. Medellängden för den kortaste vägen beräknas med följande formel [7] :

 - avstånd från topp till topp  är antalet hörn i grafen

Vissa andra funktioner, som kommer att beskrivas senare, finns ofta i kolumnerna "Small World". Vanligtvis har sådana grafer många nav  - hörn, vars grad är betydligt (många gånger) större än graden av de flesta av grafens hörn. Det är dessa nav som minskar den genomsnittliga kortaste vägen i grafen. Ett typiskt exempel på "Small World"-grafen är ett nätverk av flygningar med flygplatsnoder. Mellan två städer i världen kommer det förmodligen inte att ta mer än tre flygningar på grund av det faktum att de flesta flygen går genom navflygplatser .

För att analysera denna egenskap (nämligen förekomsten av nav) tas hänsyn till andelen hörn i nätverket som har en stor grad. Nätverk med fler hubbar än förväntat kommer att ha en högre andel höggradiga hörn och väldigt många låggradiga hörn. Därför kommer fördelningen av graderna av grafens hörn att vara en "tung svansfördelning" . Grafer med mycket olika topologier klassificeras som Small World-grafer om ovanstående två villkor är uppfyllda.

Att tillhöra klassen av grafer "Small World" uppskattas genom att jämföra klustringen och väglängden för detta nätverk med motsvarande parametrar för ett ekvivalent slumpmässigt nätverk med samma genomsnittliga grad av hörn [8] . En annan metod för att uppskatta om ett nätverk tillhör grafklassen "Small World" använder den ursprungliga definitionen av "Small World"-grafen, och jämför graden av klustring av ett givet nätverk med graden av klustring av en ekvivalent gittergraf och längden av medelvägen med längden på medelvägen i en godtycklig graf [9] . Måttet på grafen som tillhör klassen "Small world" ( ) definieras som

 är den genomsnittliga längden på den kortaste vägen i grafen i fråga  är graden av klustring av den betraktade grafen  är medellängden på den kortaste vägen i en slumpmässig graf  är graden av klustring av grafgittret

R. Cowen och Shlomo Havlin [10] [11] visade analytiskt att skalfria nätverk  är ultrasmå världar. I detta fall, på grund av nav, blir de kortaste vägarna betydligt kortare och skalas som

Exempel på grafer för "liten värld"

Små världsgrafegenskaper har hittats i många verkliga objekt, inklusive vägkartor, näringskedjor, elektriska nätverk, metaboliska processnätverk, neurala nätverk , väljarnätverk, telefonsamtalsgrafer och sociala påverkansnätverk.

Protein-protein-interaktioner har en sådan egenskap hos "Small World"-grafen som motsvarar kraftfördelningslagen [12] .

På liknande sätt har transkriptionsreglering egenskaper hos "Small World"-grafen , där generna motsvarar hörnen , och de är kopplade om en gen har en upp- eller nedreglerande genetisk påverkan på den andra [13] .

Nätverkstillförlitlighet

Vissa forskare (till exempel Barabási ) har föreslagit att förekomsten av små världsgrafer i biologiska system kan återspegla den evolutionära fördelen med en sådan topologi. Anledningen till detta antagande var hypotesen att "Small World"-graferna är mer stabila under olika yttre påverkan jämfört med andra nätverkstopologier. Om denna hypotes var korrekt skulle den ge en fördel för biologiska system som är föremål för mutationer och virusinfektioner [14] .

I Small World-grafer med en kraftlagsfördelning av vertexgrader, orsakar borttagning av en slumpmässig vertex sällan en signifikant ökning av den genomsnittliga kortaste vägen (eller en signifikant minskning av klustringskoefficienten ). Detta följer av det faktum att de flesta av de kortaste vägarna passerar genom navet, och om en perifer nod tas bort är det osannolikt att den kommer att störa passagen mellan andra perifera noder. Eftersom andelen perifera hörn i Small World-kolumnen är betydligt högre än andelen hubbar, är sannolikheten för att ta bort en viktig vertex extremt liten [15] . Till exempel, om den lilla flygplatsen i Petrozavodsk upphör att fungera, kommer detta inte att öka det genomsnittliga antalet flyg som passagerare behöver för att nå sin destination. Men om en slumpmässig radering träffar ett nav, kan den genomsnittliga kortaste väglängden växa ganska avsevärt. Detta kan ses varje år när en flygplats i norra USA som Chicagos O'Hare Airport är täckt av snö, och många människor tvingas byta flyg och ta en rondellväg till sin destination.

Till skillnad från "Small World"-grafen, i ett slumpmässigt nätverk där alla hörn har ungefär samma antal anslutningar, ökar om man tar bort en slumpmässig vertex längden på den kortaste vägen i genomsnitt något, men samma sak för alla borttagna vertex. I denna mening är slumpmässiga nätverk sårbara för slumpmässiga störningar, medan Small World-graferna är stabila [16] . Emellertid är "Small World"-grafer sårbara för riktade attacker mot hubbar, medan det i slumpmässiga nätverk är omöjligt att välja mål vars förstörelse kommer att leda till katastrofala konsekvenser [17] [18] .

Följaktligen har virus utvecklats för att interagera med navproteiner såsom p53 , och därigenom introducera betydande förändringar i cellbeteende som gynnar viral replikation [19] .

Konstruktion av små världsgrafer

Huvudmekanismen för att konstruera grafer "Small World" - Watts-Strogatz Model

Konstruktionen av små världsgrafer med tidsfördröjning [20] låter dig skapa inte bara fraktaler, utan även kaos under rätt förhållanden [21] eller övergång till kaos i dynamiska nätverk [22] .

När man löser problemet med diametergraden konstrueras en graf där antalet grannar till varje vertex är begränsat, medan avståndet mellan valfritt par av hörn ( nätverksdiameter ) minimeras. Konstruktionen av sådana "Small World"-grafer utförs som en del av ansträngningen att hitta grafer av ordning nära Moore-gränsen .

Ett annat sätt att konstruera "Small World"-grafer från grunden visas av Barmputis och Murray [23] , där ett nätverk byggs med ett mycket litet medelavstånd och en mycket stor medelklustring. En snabb algoritm med konstant komplexitet ges tillsammans med mätningar av tillförlitligheten hos de erhållna graferna. Beroende på området kan man börja med en sådan "ultra small-world"-graf, och sedan återinkludera några kanter, eller använda några små sådana nätverk som en subgraf till en större graf.

Applikationer och applikationer

Grafen "Small World" används för modellering inom olika områden.

Ansökningar i sociologi

En av fördelarna med Small World-grafer för social rörelse är deras skydd mot filtreringsenheter som använder starkt sammankopplade hörn . En annan fördel är bättre effektivitet i informationsöverföringen samtidigt som antalet länkar som krävs för att ansluta till nätverket hålls till ett minimum [24] .

Grafmodellen "Small World" är direkt tillämplig på teorin om affinitetsgrupper , presenterad i sociologiska argument av William Finnegan . Affinitetsgrupper är sociala rörelser som är små och halvoberoende, men som har betydande mål och mål. Trots att enskilda deltagare är relativt självständiga och självständiga, motsvarar flera deltagare med hög grad av uppkoppling hubbar i "Small World"-grafen – de är sammankopplande noder som kopplar samman olika grupper. Denna Small World Earl-modell visade sig vara en extremt effektiv taktik för att organisera protester mot polisaktioner [25] . Clay Shirky hävdar att ju mer ett socialt nätverk är baserat på små nätverk, som bildar grafen "Small World", desto mer värdefulla är högt anslutna noder i detta nätverk [24] . Detsamma kan sägas om affinitetsgruppsmodellen, där ett fåtal personer i varje grupp är kopplade till utomstående grupper som tillåts en mycket större grad av mobilisering och anpassning. Ett praktiskt exempel på detta är "Small World"-grafen genom affinitetsgrupper som William Finnegan beskrev i 1999 års protester i Seattle

Ansökan till geovetenskaper

Många nätverk som studerats i geologi och geofysik liknar till egenskaperna hos Small World-grafen. Nätverk som definieras i ett system av sprickor och porösa ämnen uppvisar dessa egenskaper [26] . De seismiska nätverken i regionen i södra Kalifornien kan vara "Small World"-grafer [27] . Exemplen ovan förekommer i en mängd olika rumsliga skalor, vilket visar skalinvariansen för ett fenomen inom geovetenskaperna .

Applikationer för datorer

Kolumnerna "Small World" användes för att bedöma möjligheten att använda information lagrad i stora databaser. Utvärderingsåtgärden kallas "Small World Data Transformation Measure" [28] [29] . Ju mer databaslänkarna ser ut som en liten världsgraf, desto mer sannolikt kommer användaren att kunna extrahera information i framtiden. Denna bekvämlighet uppnås vanligtvis på bekostnad av mängden information som kan lagras i samma lagring.

Freenet P2P-nätverket bildar en "Small World"-graf, [30] som ger möjlighet att lagra och lokalisera information på ett sätt som skalas effektivt när nätverket växer.

Räknar "Small World" i neurala nätverk i hjärnan

Anatomiska kopplingar i hjärnan [31] och synkroniseringsnätverk av kortikala neuroner [32] är exempel på Small World-grafer.

"Small World"-grafen över neuroner kan uppvisa arbetsminnesegenskaper . Datormodellen utvecklad av Solla et al [33] [34] har två stabila tillstånd; denna egenskap kallas bistabilitet och anses viktig i minneslagring . Den aktiverande impulsen genereras av självuppehållande loopar av kommunikationsaktivitet mellan neuroner. Den andra pulsen avslutar denna aktivitet. Pulser växlar systemet mellan stabila tillstånd: flöde (registrerar "minne") och viloläge (minneslagring).

På en mer allmän nivå uppvisar många stora neurala nätverk i hjärnan, såsom det visuella systemet och hjärnstammen , egenskaperna hos "Small World"-grafen [35] .

Grafen "Small World" i beräkningslingvistik och textbehandlingsproblem

Lite är känt om språkens historia och utveckling. Alla språk har gemensamma egenskaper: till exempel syntaktiska och semantiska kategorier. De flesta språk kännetecknas av Zipfs lag . För att studera språkens olika egenskaper används nätverk av ord (det vill säga nätverk där hörn motsvarar ord, och kanter till eventuella kopplingar mellan ord). De kan också användas för att underbygga olika hypoteser om språkens utveckling. Till exempel, baserat på likheten mellan språk, dras slutsatsen att de har en gemensam förfader. Likheten kan dock orsakas av språkens inverkan på varandra och lån av ord [36] .

I det semantiska nätverket för det engelska språket WordNet har polysemi en enorm inverkan på organisationen av den semantiska grafen. På grund av det är den semantiska grafen "Small World"-grafen [37] . Höggradiga hörn (nav) är hörn som representerar abstrakta begrepp som en linje, huvud eller cirkel [38] .

En av uppgifterna för bearbetning av naturligt språk  är uppgiften att identifiera författarskapet till en text. En av metoderna är att hitta författarens invariant . Först bearbetas texten, brusord (prepositioner, konjunktioner etc.) tas bort från den. Sedan byggs ett nätverk där hörnen motsvarar orden, och kanterna dras mellan de hörn som motsvarar orden som ligger bredvid varandra i texten. Det har fastställts att den resulterande grafen är "Small World"-grafen [39] . Om vi ​​beräknar några parametrar för ett nätverk byggt på ett litterärt verk (till exempel den genomsnittliga graden av ett vertex, klusteringskoefficienten, korrelationen mellan graden av vertex), så kan vi se att i en författares verk dessa parametrar förändring i ett relativt litet intervall, medan för olika författare skiljer dessa parametrar sig mycket kraftigare [40] .

Om vi ​​representerar Wikipedia-artiklar som hörn, och representerar länkar mellan sidor som kanter mellan motsvarande hörn, så får vi en graf som har egenskaperna hos en Small World-graf. Skälen till detta är den ovan nämnda tillhörigheten till klassen av grafer "Small World" i det semantiska nätverket av ord, samt närvaron i Wikipedia av listor och kategorier som fungerar som nav. Wikipedias höga anslutningsgrad stöds ytterligare av Connectedness-projektet [41] .

Small World-graf med länklängdsfördelning

Grafmodellen "Small World" inkluderar en enhetlig fördelning av länklängder, som följer en kraftlagsfördelning, det genomsnittliga avståndet mellan två hörn varierar beroende på fördelningens styrka [42] .

Decentraliserad sökalgoritm

Om forskaren i Stanley Milgrams experiment behöver hitta exakt den kortaste vägen , måste han skicka brev till alla sina bekanta och få dem att göra detsamma. En sådan " flod " i nätverket kommer att nå målet så snabbt som möjligt, men ett sådant massutskick är nästan omöjligt. En annan variant av experimentet är att skicka ett e-postmeddelande till endast en person åt gången. Som ett resultat av Small World- experimentet gjordes en slående algoritmisk upptäckt: i Small World-kolumnen lyckas människor som inte känner till hela strukturen på grafen, utan bara har lokal information (om sina bekanta), kollektivt hitta en relativt kort väg till målet (närvaron av en relativt kort väg är en välkänd egenskap hos grafer av typen "Small world") [43] .

Frågan uppstår: varför är det sociala nätverket uppbyggt på ett sådant sätt att en sådan decentraliserad sökalgoritm ger optimala resultat? Liknande decentraliserade sökalgoritmer fungerar också på World Wide Web , i neurala nätverk och i många andra områden. Därför kommer förståelse av algoritmerna för decentraliserade sökalgoritmer att säkerställa deras breda tillämpning [44] .

För ytterligare resonemang är det nödvändigt att formulera en mer rigorös definition av en decentraliserad sökalgoritm. Algoritmen är rekursiv: vi står på toppen , vi måste nå toppen , vi känner bara grannarna till toppen , bland dem måste vi välja en topp och köra algoritmen från den. Den decentraliserade algoritmen uppskattas av leveranstiden  - det förväntade antalet steg som krävs för att nå målet, medan Small World-grafen, start- och målpunkten genereras slumpmässigt. Syftet med forskningen är att hitta decentraliserade sökalgoritmer som är polylogaritmiska med avseende på. Dessa studier utfördes av John Kleinberg i hans arbete "Complex networks and decentralized search algorithms" [44] .

Se även

Anteckningar

  1. ↑ 1 2 Kollektiv dynamik i nätverk i den lilla världen .
  2. ↑ Alexey Savvateev: Modeller av internet och sociala nätverk / Habr . Hämtad 27 april 2022. Arkiverad från originalet 27 april 2022.
  3. ↑ Barthelmy och Amaral, 1999 .
  4. ↑ Barrat och Weigt .
  5. ↑ Dorogovtsev och Mendes .
  6. ↑ Barmpoutis och Murray .
  7. ↑ Komplexa nätverk Struktur och dynamik , sid. åtta.
  8. ↑ Humphries, 2007 .
  9. ↑ Telesford, Joyce, Hayasaka, Burdette, Laurienti, 2011 .
  10. ↑ Cohen och Havlin och ben-Avraham, 2002 .
  11. ↑ Skalfria nätverk är ultrasmå, 2003 .
  12. ↑ Proteins, 2004 , sid. 292–299.
  13. ↑ Gennätverk, 2004 , sid. 280-4.
  14. ↑ Che, Ali, Reynolds, 2010 .
  15. ↑ Handbok om biologiska nätverk, 2010 , sid. 23.
  16. ↑ patent .
  17. ↑ Lamanna, Longo, 2007 , sid. 90.
  18. ↑ Designing Robust Road Networks, 2010 , s. 13.
  19. ↑ Protein Interaction, 2006 , sid. 17.
  20. ↑ Fraktaler med tidsfördröjning, 2002 , sid. 215-219.
  21. ↑ Chaos in small-world networks, 2001 .
  22. ↑ Övergång till kaos .
  23. ↑ Barmpoutis, Murray, 2010 .
  24. ↑ 12 Shirky , 2008 .
  25. ↑ Finnegan, 2003 .
  26. ↑ Yang, 2001 .
  27. ↑ Jimenez, Tiampo, Posadas, 2008 .
  28. ↑ Informationsteori & affärsintelligensstrategi .
  29. ↑ Hillard, 2010 .
  30. ↑ Sandberg .
  31. ↑ Sporns, 2004 .
  32. ↑ Yu, 2008 .
  33. ↑ Cohen .
  34. ↑ Solla .
  35. ↑ Humphries, 2007 , sid. 367-375.
  36. ↑ Sula .
  37. ↑ WordNet , sid. ett.
  38. ↑ WordNet .
  39. ↑ Antiqueira , sid. fyra.
  40. ↑ Antiqueira .
  41. ↑ Masucci .
  42. ↑ Dimension av rumsligt inbäddade nätverk, 2011 .
  43. ↑ Kleinberg, 2006 , sid. 5.
  44. ↑ 12 Kleinberg , 2006 , sid. 6.

Litteratur

Länkar