Ömsesidighet (nätverksvetenskap)

Inom nätverksvetenskap är reciprocitet ett mått på sannolikheten för att hörn i ett riktat nätverk är ömsesidigt sammanlänkade. Liksom klustringskoefficienten , skalfri examensfördelning eller samhällsstruktur , är ömsesidighet ett kvantitativt mått som används för att studera komplexa nätverk .

Motivering

I verkliga nätverksproblem är människor intresserade av att bestämma sannolikheten för att det uppstår dubbla länkar (med motsatta riktningar) mellan vertexpar. Detta problem är grundläggande av flera skäl. För det första, i de nätverk som transporterar information eller material (som e-postnätverk, World Wide Web (WWW), World Trade Web eller Wikipedia ), underlättar ömsesidiga länkar transportprocessen. För det andra, när man analyserar riktade nätverk, behandlar människor dem ofta som oriktade för enkelhetens skull; därför hjälper informationen som erhålls från ömsesidighetsstudier att uppskatta felet som introduceras när ett riktat nätverk behandlas som oriktat (till exempel vid mätning av klustringskoefficienten ) . Slutligen kan upptäcka icke-triviala mönster av ömsesidighet avslöja möjliga mekanismer och organiserande principer som formar det observerade nätverkets topologi.

Hur definieras det?

Traditionell definition

Ett traditionellt sätt att definiera ömsesidigheten r är att använda förhållandet mellan antalet länkar som pekar i båda riktningarna $L^{<->}$ och det totala antalet länkar L $r={\frac {L^{<->}}{L}}$

Med denna definition är $r=1$ för ett rent dubbelriktat nätverk medan $r=0$ för ett rent enkelriktat. Verkliga nätverk har ett mellanvärde mellan 0 och 1.

Denna definition av ömsesidighet har dock vissa brister. Den kan inte säga den relativa skillnaden i ömsesidighet jämfört med ett rent slumpmässigt nätverk med samma antal hörn och kanter. Den användbara informationen från ömsesidighet är inte värdet i sig, utan om ömsesidiga länkar inträffar mer eller mindre ofta än vad som förväntas av en slump. Dessutom, i de nätverk som innehåller självlänkande slingor (länkar som börjar och slutar vid samma vertex), bör de självlänkande slingorna uteslutas vid beräkning av L.

Garlaschelli och Loffredos definition

För att övervinna bristerna i definitionen ovan definierade Garlaschelli och Loffredo reciprocitet som korrelationskoefficienten mellan ingångarna i närliggande matris i en riktad graf (a i j = 1 {\ $=1}$ om en länk från i till j finns där, och $a_{ij}=0$ om inte):

$\rho \equiv {\frac {\sum _{ i\neq j}(a_{ij}-{\bar {a}})(a_{ji}-{\bar {a}})}{\sum _{i\neq j}(a_{ij}- {\bar {a}})^{2}}}$ ,

där medelvärdet ${\bar {a}}\equiv {\frac {\sum _{i\ neq j}a_{ij}}{N(N-1)}}={\frac {L}{N(N-1)}}$ .

${\bar {a}}$ mäter förhållandet mellan observerade och möjliga riktade länkar (länkdensitet), och självlänkande loopar är nu exkluderade från L eftersom i inte är lika med j.

Definitionen kan skrivas i följande enkla form:

$\rho ={\frac {r-{\bar {a}}}{1-{\bar {a}}}}$

Den nya definitionen av ömsesidighet ger en absolut kvantitet som direkt gör att man kan skilja mellan ömsesidiga ( $\rho >0$ ) och antireciproka ( ${\displaystyle \rho <0} )$ nätverk, med ömsesidiga länkar som förekommer mer och mindre ofta än slumpmässigt.

Om alla länkar förekommer i ömsesidiga par, $\rho =1$ ; om r=0, $\rho =\rho _{min}$ . $\rho _{min}\equiv {\frac {-{\bar {a}}}{1-{\bar {a}}}}$

Detta är ytterligare en fördel med att använda $\rho$ , eftersom det införlivar tanken att fullständig antireciprok är mer statistiskt signifikant i nätverk med större densitet, medan det måste betraktas som en mindre uttalad effekt i glesare nätverk.