Effektivitet (nätverksvetenskap)

Inom nätverksvetenskap är ett nätverks effektivitet ett mått på hur effektivt det utbyter information och det kallas även kommunikationseffektivitet . Den underliggande idén (och huvudantagandet) är att ju längre bort två noder är i nätverket, desto mindre effektiv blir deras kommunikation. Begreppet effektivitet kan appliceras på både lokal och global skala i ett nätverk. På en global skala kvantifierar effektivitet utbytet av information över hela nätverket där information utbyts samtidigt. Den lokala effektiviteten kvantifierar ett nätverks motstånd mot fel i liten skala. Det är den lokala effektiviteten för en nod $i$ som kännetecknar hur väl information utbyts av dess grannar när den tas bort.

Definition

Definitionen av kommunikationseffektivitet antar att effektiviteten är omvänt proportionell mot avståndet, så i matematiska termer

$\epsilon _{ij}={\frac {1}{d_{ij}}}$

där $\epsilon _{ij}$ är den parvisa effektiviteten för noderna $i,j\in V$ i nätverket $G=( V,E)$ och $d_{ij}$ är deras avstånd .

Den genomsnittliga kommunikationseffektiviteten för nätverket $G$ definieras sedan som genomsnittet över de parvisa effektiviteterna:

$E(G)={\frac {1}{N(N-1)}}\summa _{i \neq j\in V}{\frac {1}{d_{ij}}}$

där $N=|V|$ anger antalet noder i nätverket.

Avstånd kan mätas på olika sätt, beroende på typ av nätverk. Det mest naturliga avståndet för oviktade nätverk är längden på en kortaste väg mellan noderna $i$ och $j$ , dvs en kortaste väg mellan $i,j$ är en väg med minsta antal kanter och antalet kanter är dess längd. Observera att om $i=j$ så $d_{ij}=0$ — och det är därför summan ovan är över $i\neq j$ — medan om det inte finns någon väg som förbinder $i$ och $j$ , $d_{ij}=\infty$ och deras parvisa effektivitet är noll. Att vara $d_{ij}$ räknas, för $i\neq j$$d_{ij}\geq 1$ och så ${ \displaystyle E(G)}$ är avgränsad mellan 0 och 1, dvs det är en normaliserad deskriptor.

Viktade nätverk

Det kortaste vägavståndet kan också generaliseras till viktade nätverk, se det viktade kortaste vägavståndet , men i detta fall $d_{ij}^{W}\in [0,+ \infty ]$ och den genomsnittliga kommunikationseffektiviteten måste normaliseras ordentligt för att vara jämförbar mellan olika nätverk.

I författarna föreslog att normalisera $E(G)$ genom att dividera den med effektiviteten hos en idealiserad version av nätverket $G$ :

$E_{\text{glob}}(G)={\frac {E(G)}{E(G^{\text{ideal}})}}.$

$G^{\text{ideal}}$ är den "ideala" grafen på $N$ -noder där alla möjliga kanter finns. I det oviktade fallet har varje kant enhetsvikt, $G^{\text{ideal}}$ är en klick , ett fullständigt nätverk och $E(G^{\ text{ideal}})=1$ . När kanterna är viktade, ett tillräckligt villkor (för att ha en korrekt normalisering, dvs $E_{\text{glob}}(G)\in [0,1]$ ) på avstånden i det ideala nätverket, som denna gång kallas $l_{ij}$ , är

$l_{ij}\leq d_{ij}$

för $i,j=1,...,N$ . $l_{ij}$ bör vara känd (och skiljer sig från noll) för alla nodpar. Ett vanligt val är att ta dem som de geografiska eller fysiska avstånden i rumsliga nätverk eller som den maximala kostnaden över alla länkar, t.ex. $l_{ij}={\frac {1}{w_{ \max }}}$ där $w_{\max }$ indikerar den maximala interaktionsstyrkan i nätverket. Men i författarna lyfta fram frågorna om dessa val när de hanterar verkliga nätverk, som kännetecknas av heterogen struktur och flöden. Att till exempel välja $l_{ij}={\frac {1}{w_{\max }}}$ gör det globala måttet mycket känsligt för extremvärden i fördelningen av vikter och tenderar att underskatta den faktiska effektiviteten av ett nätverk. Författarna föreslår också en normaliseringsprocedur, dvs ett sätt att bygga $G^{\text{ideal}}$ genom att använda all och endast informationen som finns i kantvikterna (och inga andra metadata såsom geografiska avstånd ), som är statistiskt robust och fysiskt grundad.

Effektivitet och småvärldsbeteende

Den globala effektiviteten för ett nätverk är ett mått som är jämförbart med ${\displaystyle 1/L} ,$ snarare än bara den genomsnittliga väglängden $L$ själv. Den viktigaste skillnaden är att medan $1/L$ mäter effektivitet i ett system där endast ett paket med information flyttas genom nätverket, $E_{\text{glob} }(G)$ mäter effektiviteten av parallell kommunikation, det vill säga när alla noder utbyter informationspaket med varandra samtidigt.

Ett lokalt medelvärde av parvisa kommunikationseffektiviteter kan användas som ett alternativ till klustringskoefficienten för ett nätverk. Den lokala effektiviteten för ett nätverk $G$ definieras som:

$E_{loc}(G,i)={\frac {1}{N}}\summa _{i\ i G}E(G_{i})$

där $G_{i}$ är den lokala subgrafen som endast består av en nod ${\displaystyle i} s omedelbara grannar, men inte$ själva noden ${\displaystyle i} .$

Ansökningar

I stora drag kan ett nätverks effektivitet användas för att kvantifiera små världsbeteende i nätverk. Effektivitet kan också användas för att fastställa kostnadseffektiva strukturer i viktade och ovägda nätverk. Att jämföra de två effektivitetsmåtten i ett nätverk med ett slumpmässigt nätverk av samma storlek för att se hur ekonomiskt ett nätverk är uppbyggt. Dessutom är global effektivitet lättare att använda numeriskt än dess motsvarighet, väglängd.

Av dessa skäl har begreppet effektivitet använts i de många olika tillämpningarna av nätverksvetenskap. Effektivitet är användbart vid analys av konstgjorda nätverk som transportnätverk och kommunikationsnätverk. Den används för att avgöra hur kostnadseffektiv en viss nätverkskonstruktion är, samt hur feltålig den är. Studier av sådana nätverk visar att de tenderar att ha hög global effektivitet, vilket innebär god resursanvändning, men låg lokal effektivitet. Detta beror till exempel på att ett tunnelbanenät inte är stängt, och passagerare kan dirigeras om, till exempel med bussar, även om en viss linje i nätet är nere.

Utöver mänskligt konstruerade nätverk är effektivitet ett användbart mått när man talar om fysiska biologiska nätverk. I alla aspekter av biologi spelar bristen på resurser en nyckelroll, och biologiska nätverk är inget undantag. Effektivitet används inom neurovetenskap för att diskutera informationsöverföring över neurala nätverk , där det fysiska utrymmet och resursbegränsningarna är en viktig faktor. Effektivitet har också använts i studier av myrkolonitunnelsystem , som vanligtvis består av stora rum såväl som många vidsträckta tunnlar. Denna tillämpning på myrkolonier är inte alltför överraskande eftersom den stora strukturen i en koloni måste fungera som ett transportnätverk för olika resurser, de flesta nämligen mat.