Gradfördelning - Degree distribution

Nätverksvetenskap
Teori
Graf Komplext nätverk Smitta Liten värld Skalfri Gemenskapsstruktur Perkolering Evolution Kontrollerbarhet Diagramritning Socialt kapital Länkanalys Optimering Ömsesidighet Stängning Homofil Transitivitet Föredragen bilaga Balansteori Nätverkseffekt Socialt inflytande
Nätverkstyper
Informativ (databehandling) Telekommunikation Transport Social Vetenskapligt samarbete Biologisk Konstgjorda neurala Beroende av varandra Semantisk Rumslig Beroende Flöde on-Chip
Grafer
Funktioner Klick Komponent Skära Cykel Datastruktur Kant Slinga Grannskap Väg Vertex Adjacency lista  / matris Incidenslista  / matris Typer Bipartite Komplett Riktad Hyper Mång Slumpmässig Viktad
Metrik Algoritmer
Centralitet Grad Motiv Kluster Gradfördelning Assortativitet Distans Modularitet Effektivitet
Modeller
Topologi Slumpmässigt diagram Erdős – Rényi Barabási – Albert Fitnessmodell Watts – Strogatz Exponential random (ERGM) Slumpmässig geometrisk (RGG) Hyperbolisk (HGN) Hierarkisk Stokastiskt block Maximal entropi Mjuk konfiguration LFR-riktmärke Dynamik Booleskt nätverk agentbaserad Epidemi / SIR
Listor Kategorier
Ämnen programvara Nätverksforskare Kategori: Nätverksteori Kategori: Grafteori
v t e

I studien av grafer och nätverk är graden av en nod i ett nätverk antalet anslutningar den har till andra noder och gradfördelningen är sannolikhetsfördelningen för dessa grader över hela nätverket.

Definition

Den grad av en nod i ett nätverk (ibland kallad felaktigt som konnektivitet ) är antalet anslutningar eller kanter noden har till andra noder. Om ett nätverk är riktat , vilket innebär att kanterna pekar i en riktning från en nod till en annan nod, så har noder två olika grader, in-grad, vilket är antalet inkommande kanter och ut-grad, vilket är antalet av utgående kanter.

Gradfördelningen P ( k ) i ett nätverk definieras sedan som fraktionen av noder i nätverket med grad k . Således om det finns n noder totalt i ett nätverk och n _k av dem har grad k , har vi . ${\ displaystyle P (k) = {\ frac {n_ {k}} {n}}}$

Samma information presenteras ibland också i form av en kumulativ gradfördelning , fraktionen av noder med grad mindre än k , eller till och med den kompletterande kumulativa gradfördelningen , fraktionen av noder med grad större än eller lika med k (1 - C ) om man betraktar C som den kumulativa gradfördelningen ; dvs komplementet till C .

Observerade gradfördelningar

Gradsfördelningen är mycket viktig för att studera både riktiga nätverk, såsom Internet och sociala nätverk , och teoretiska nätverk. Den enklaste nätverksmodell, till exempel, den (Erdős-Renyi modell) slumpgraf , i vilken var och en av n noder är oberoende ansluten (eller ej) med sannolikheten p (eller 1 - p ), har en binomialfördelning grader k :

${\ displaystyle P (k) = {n-1 \ välj k} p ^ {k} (1-p) ^ {n-1-k},}$

(eller Poisson i gränsen för stora n , om den genomsnittliga graden hålls fast). De flesta nätverk i den verkliga världen har dock graddistributioner som skiljer sig mycket från detta. De flesta är mycket snedställda , vilket innebär att en stor majoritet av noder har låg grad men ett litet antal, så kallade "nav", har hög grad. Vissa nätverk, särskilt Internet, world wide web , och vissa sociala nätverk har argumenterat för att ha graders distributioner som ungefär följer en kraft lag : där γ är konstant. Sådana nät kallas skalningsfria nätverk och har uppmärksammats särskilt för sina strukturella och dynamiska egenskaper. En undersökning av ett brett spektrum av verkliga nätverk antyder dock att skalningsfria nätverk är sällsynta när de bedöms med statistiskt noggranna åtgärder. Vissa forskare har ifrågasatt dessa resultat och hävdat att definitionerna som används i studien är felaktigt strikta, medan andra har hävdat att den exakta funktionella formen av gradfördelningen är mindre viktig än att veta om gradfördelningen är fettsvansad eller inte. Övertolkningen av specifika former av examensfördelningen har också kritiserats för att inte ha övervägt hur nätverk kan utvecklas över tiden. ${\ displaystyle \ langle k \ rangle = p (n-1)}$${\ displaystyle P (k) \ sim k ^ {- \ gamma}}$

För hög grad av fördelning

Överskridande gradfördelning är sannolikhetsfördelningen för en nod som nås genom att följa en kant av antalet andra kanter som är kopplade till den noden. Med andra ord är det distributionen av utgående länkar från en nod som nås genom att följa en länk.

Antag att ett nätverk har en gradfördelning , genom att välja en nod (slumpmässigt eller inte) och gå till en av dess grannar (förutsatt att den åtminstone har en granne), då ges inte sannolikheten för att noden ska ha grannar . Anledningen är att, när någon nod väljs i ett heterogent nätverk, är det mer troligt att nå naven genom att följa en av de befintliga grannarna till den noden. Den verkliga sannolikheten för att sådana noder har grad är vilken som kallas den överskottsgraden för den noden. I konfigurationsmodellen , vilka korrelationer mellan noder som har ignorerats och varje nod antas vara ansluten till andra noder i nätverket med samma sannolikhet, kan överskridande gradfördelning hittas som: ${\ displaystyle P (k)}$${\ displaystyle k}$${\ displaystyle P (k)}$${\ displaystyle k}$${\ displaystyle q (k)}$

${\ displaystyle q (k) = {\ frac {k + 1} {\ langle k \ rangle}} P (k + 1),}$

var är modellens medelgrad (medelgrad). Det följer av det faktum att genomsnittsgraden för vilken nod som helst är större än genoms genomsnittsgrad. I sociala nätverk betyder det att dina vänner i genomsnitt har fler vänner än du. Detta är känt som vänskapsparadoxen . Det kan visas att ett nätverk kan ha en gigantisk komponent om dess genomsnittliga överskottsgrad är större än en: ${\ displaystyle {\ langle k \ rangle}}$

${\ displaystyle \ sum _ {k} kq (k)> 1 \ Rightarrow {\ langle k ^ {2} \ rangle} -2 {\ langle k \ rangle}> 0}$

Tänk på att de två sista ekvationerna bara är för konfigurationsmodellen och för att härleda överdriven gradfördelning av ett riktigt ordnätverk, bör vi också lägga till gradskorrelationer.

Metoden Generera funktioner

Genereringsfunktioner kan användas för att beräkna olika egenskaper hos slumpmässiga nätverk. Med tanke på fördelningen grad och överskottsgrad fördelning av något nätverk, och respektive, är det möjligt att skriva två potensserier i följande former: ${\ displaystyle P (k)}$${\ displaystyle q (k)}$

${\ displaystyle G_ {0} (x) = \ textstyle \ sum _ {k} \ displaystyle P (k) x ^ {k}}$ och ${\ displaystyle G_ {1} (x) = \ textstyle \ sum _ {k} \ displaystyle q (k) x ^ {k} = \ textstyle \ sum _ {k} \ displaystyle {\ frac {k} {\ langle k \ rangle}} P (k) x ^ {k-1}}$

${\ displaystyle G_ {1} (x)}$ kan också erhållas från derivat av : ${\ displaystyle G_ {0} (x)}$

${\ displaystyle G_ {1} (x) = {\ frac {G '_ {0} (x)} {G' _ {0} (1)}}}$

Om vi ​​känner till genereringsfunktionen för en sannolikhetsfördelning kan vi återställa värdena genom att differentiera: ${\ displaystyle P (k)}$${\ displaystyle P (k)}$

${\ displaystyle P (k) = {\ frac {1} {k!}} {\ operatorname {d} ^ {k} \! G \ over \ operatorname {d} \! x ^ {k}} {\ biggl \ vert} _ {x = 0}}$

Vissa egenskaper, t.ex. momenten, kan enkelt beräknas från och dess derivat: ${\ displaystyle G_ {0} (x)}$

• ${\ displaystyle {\ langle k \ rangle} = G '_ {0} (1)}$
• ${\ displaystyle {\ langle k ^ {2} \ rangle} = G '' _ {0} (1) + G '_ {0} (1)}$

Och i allmänhet:

• ${\ displaystyle {\ langle k ^ {m} \ rangle} = {\ Biggl [} {{\ bigg (} \ operatorname {x} {\ operatorname {d} \! \ over \ operatorname {dx} \!} { \ biggl)} ^ {m}} G_ {0} (x) {\ Biggl]} _ {x = 1}}$

För Poisson -fördelade slump nätverk, såsom ER diagrammet , är att anledningen till teorin om slumpmässiga nätverk av denna typ är särskilt enkel. Sannolikhetsfördelningarna för 1: a och 2: a närmaste grannar genereras av funktionerna och . I förlängningen genereras distributionen av -th grannar av: ${\ displaystyle G_ {1} (x) = G_ {0} (x)}$${\ displaystyle G_ {0} (x)}$${\ displaystyle G_ {0} (G_ {1} (x))}$${\ displaystyle m}$

${\ displaystyle G_ {0} {\ bigl (} G_ {1} (... G_ {1} (x) ...) {\ bigr)}}$ , med iterationer av funktionen som verkar på sig själv. ${\ displaystyle m-1}$${\ displaystyle G_ {1}}$

Det genomsnittliga antalet första grannar, är, och det genomsnittliga antalet andra grannar är: ${\ displaystyle c_ {1}}$${\ displaystyle {\ langle k \ rangle} = {dG_ {0} (x) \ över dx} | _ {x = 1}}$${\ displaystyle c_ {2} = {\ biggl [} {d \ over dx} G_ {0} {\ big (} G_ {1} (x) {\ big)} {\ biggl]} _ {x = 1 } = G_ {1} '(1) G' _ {0} {\ big (} G_ {1} (1) {\ big)} = G_ {1} '(1) G' _ {0} (1 ) = G '' _ {0} (1)}$

Graddistribution för riktade nätverk

In / ut-gradfördelning för Wikipedia's hyperlänkgraf (logaritmiska skalor)

I ett riktat nätverk har varje nod en viss grad och en viss grad som är antalet länkar som har gått in och ut ur den noden med respekt. Om är sannolikheten för att en slumpmässigt vald nod har in- och utgrad kan genereringsfunktionen tilldelad denna gemensamma sannolikhetsfördelning skrivas med två värdesaker och som: ${\ displaystyle k_ {in}}$${\ displaystyle k_ {ut}}$${\ displaystyle P (k_ {in}, k_ {out})}$${\ displaystyle k_ {in}}$${\ displaystyle k_ {ut}}$${\ displaystyle x}$${\ displaystyle y}$

${\ displaystyle {\ mathcal {G}} (x, y) = \ sum _ {k_ {in}, k_ {out}} \ displaystyle P ({k_ {in}, k_ {out}}) x ^ {k_ {in}} y ^ {k_ {ut}}.}$

Eftersom varje länk i ett riktat nätverk måste lämna någon nod och ange en annan, är det genomsnittliga antalet länkar som går in i en noll noll. Därför,

${\ displaystyle \ langle {k_ {in} -k_ {out}} \ rangle = \ sum _ {k_ {in}, k_ {out}} \ displaystyle (k_ {in} -k_ {out}) P ({k_ {in}, k_ {out}}) = 0}$ ,

vilket innebär att generationens funktion måste uppfylla:

${\ displaystyle {\ partial {\ mathcal {G}} \ over \ partial x} \ vert _ {x, y = 1} = {\ partial {\ mathcal {G}} \ over \ partial y} \ vert _ { x, y = 1} = c,}$

var är medelvärdet (både in och ut) för noderna i nätverket; ${\ displaystyle c}$${\ displaystyle \ langle {k_ {in}} \ rangle = \ langle {k_ {out}} \ rangle = c.}$

Med hjälp av funktionen kan vi återigen hitta genereringsfunktionen för in / ut-gradfördelningen och i / ut-överdriven gradfördelning, som tidigare. kan definieras som genereringsfunktioner för antalet ankommande länkar vid en slumpmässigt vald nod, och kan definieras som antalet ankommande länkar till en nod som nås genom att följa en slumpmässigt vald länk. Vi kan också definiera genereringsfunktioner och för antalet som lämnar en sådan nod: ${\ displaystyle {\ mathcal {G}} (x, y)}$${\ displaystyle G_ {0} ^ {in} (x)}$${\ displaystyle G_ {1} ^ {in} (x)}$${\ displaystyle G_ {0} ^ {ut} (y)}$${\ displaystyle G_ {1} ^ {ut} (y)}$

• ${\ displaystyle G_ {0} ^ {in} (x) = {\ mathcal {G}} (x, 1)}$
• ${\ displaystyle G_ {1} ^ {in} (x) = {\ frac {1} {c}} {\ partial {\ mathcal {G}} \ over \ partial x} \ vert _ {y = 1}}$
• ${\ displaystyle G_ {0} ^ {out} (y) = {\ mathcal {G}} (1, y)}$
• ${\ displaystyle G_ {1} ^ {out} (y) = {\ frac {1} {c}} {\ partial {\ mathcal {G}} \ over \ partial y} \ vert _ {x = 1}}$

Här, det genomsnittliga antalet 1st grannar, eller som tidigare infördes som är och det genomsnittliga antalet 2nd grannar kan nås från en slumpmässigt vald nod ges av: . Detta är också antalet första och andra grannar från vilka en slumpmässig nod kan nås, eftersom dessa ekvationer är uppenbart symmetriska i och . ${\ displaystyle c}$${\ displaystyle c_ {1}}$${\ displaystyle {\ partial {\ mathcal {G}} \ over \ partial x} {\ biggl \ vert} _ {x, y = 1} = {\ partial {\ mathcal {G}} \ over \ partial y} {\ biggl \ vert} _ {x, y = 1}}$${\ displaystyle c_ {2} = G_ {1} '(1) G' _ {0} (1) = {\ partial ^ {2} {\ mathcal {G}} \ over \ partial x \ partial y} { \ biggl \ vert} _ {x, y = 1}}$${\ displaystyle x}$${\ displaystyle y}$

Graddistribution för signerade nätverk

I ett signerat nätverk har varje nod en positiv och en negativ grad som är det positiva antalet länkar och det negativa antalet länkar som är kopplat till den noden med respekt. Så och beteckna negativ gradfördelning och positiv gradfördelning för det signerade nätverket. ${\ displaystyle k _ {+}}$${\ displaystyle k _ {-}}$${\ displaystyle P (k _ {+})}$${\ displaystyle P (k _ {-})}$

Se även

• Grafteori
• Komplext nätverk
• Skalfritt nätverk
• Slumpmässigt diagram
• Strukturell avskärning

Referenser

• Albert, R .; Barabasi, A.-L. (2002). "Statistisk mekanik för komplexa nätverk". Recensioner av modern fysik . 74 (1): 47–97. arXiv : cond-mat / 0106096 . Bibcode : 2002RvMP ... 74 ... 47A . doi : 10.1103 / RevModPhys.74.47 .
• Dorogovtsev, S .; Mendes, JFF (2002). "Utveckling av nätverk". Framsteg inom fysik . 51 (4): 1079–1187. arXiv : cond-mat / 0106144 . Bibcode : 2002AdPhy..51.1079D . doi : 10.1080 / 00018730110112519 .
• Newman, MEJ (2003). "Strukturen och funktionen hos komplexa nätverk". SIAM Review . 45 (2): 167–256. arXiv : cond-mat / 0303516 . Bibcode : 2003SIAMR..45..167N . doi : 10.1137 / S003614450342480 .
• Shlomo Havlin & Reuven Cohen (2010). Komplexa nätverk: struktur, robusthet och funktion . Cambridge University Press.