Slumpmässig promenad närhet centralitet

Random walk closeness centrality är ett mått på centralitet i ett nätverk , som beskriver den genomsnittliga hastighet med vilken slumpmässiga gångprocesser når en nod från andra noder i nätverket. Det liknar närhetscentraliteten förutom att avståndet mäts av den förväntade längden på en slumpmässig promenad snarare än av den kortaste vägen .

Konceptet föreslogs först av White och Smyth (2003) under namnet Markov centrality .

Intuition

Betrakta ett nätverk med ett ändligt antal noder och en slumpmässig gångprocess som börjar i en viss nod och fortsätter från nod till nod längs kanterna. Från varje nod väljer den slumpmässigt den kant som ska följas. I ett oviktat nätverk är sannolikheten att välja en viss kant lika över alla tillgängliga kanter, medan den i ett viktat nätverk är proportionell mot kantvikterna. En nod anses vara nära andra noder, om den slumpmässiga gångprocessen som initieras från någon nod i nätverket anländer till just denna nod i relativt få steg i genomsnitt.

Definition

Betrakta ett viktat nätverk – antingen riktat eller oriktat – med n noder betecknade med j=1, …, n; och en slumpmässig vandringsprocess på detta nätverk med en övergångsmatris M. ${\displaystyle m_{ij}}-$ elementet i M beskriver sannolikheten för att den slumpmässiga vandraren som har nått nod i, fortsätter direkt till nod j. Dessa sannolikheter definieras på följande sätt.

$m_{ij}={\frac {a_{ij}}{\sum _{k=1}^{n}a_{ik}} }$

där $a_{ij}$ är det (i,j):e elementet i nätverkets viktningsmatris A. När det inte finns någon kant mellan två noder är motsvarande element i A-matrisen noll.

Den slumpmässiga promenadnärhetens centralitet för en nod i är inversen av den genomsnittliga medeltiden för första passage till den noden:

$C_{i}^{RWC}={\frac {n}{\sum _{j=1}^{n}H (j,i)}}$

där $H(j,i)$ är medeltiden för första passage från nod j till nod i.

Genomsnittlig första passagetid

Den genomsnittliga första passagetiden från nod i till nod j är det förväntade antalet steg det tar för processen att nå nod j från nod i för första gången:

$H(i,j)=\summa _{r=1}^{\infty }rP(i,j, r)$

där P(i,j,r) anger sannolikheten att det krävs exakt r steg för att nå j från i för första gången. För att beräkna dessa sannolikheter för att nå en nod för första gången i r steg är det användbart att betrakta målnoden som en absorberande nod och introducera en transformation av M genom att ta bort dess j:te rad och kolumn och beteckna den med $M_{-j}$ . Eftersom sannolikheten för att en process börjar vid i och är i k efter r-1 steg helt enkelt ges av det (i,k):e elementet i $M_{-j}^{r-1 }$ , P(i,j,r) kan uttryckas som

$P(i,j,r)=\summa _{k\neq j}( (M_{-j}^{r-1}))_{ik}m_{kj}$

Att ersätta detta med uttrycket för genomsnittlig första passagetid ger

$H(i,j)=\summa _{r=1} ^{\infty }r\sum _{k\neq j}((M_{-j}^{r-1}))_{ik}m_{kj}$

Att använda formeln för summering av geometriska serier för matriser ger

$H(i,j)=\summa _{k\neq j}((I- M_{-j})^{-2})_{ik}m_{kj}$

där I är den n-1 dimensionella identitetsmatrisen .

För beräkningsbekvämlighet kan detta uttryck vektoriseras som

$H(.,j)=(I-M_{-j})^{-1}e$

där $H(.,j)$ är vektorn för första passagetider för en promenad som slutar vid nod j, och e är en n-1 dimensionell vektor av ettor.

Den genomsnittliga första passagetiden är inte symmetrisk, inte ens för oriktade grafer.

I modellnätverk

) bestäms fördelningen av random walk closeness centrality i en Barabási-Albert-modell huvudsakligen av gradfördelningen . I ett sådant nätverk är den slumpmässiga promenadnärhetens centralitet för en nod ungefär proportionell mot, men ökar inte monotont med dess grad.

Applikationer för riktiga nätverk

Random walk närhetscentralitet är mer relevant mått än den enkla närhetscentraliteten vid tillämpningar där begreppet kortaste vägar inte är meningsfullt eller är mycket restriktivt för en rimlig bedömning av systemets karaktär. Detta är till exempel fallet när den analyserade processen utvecklas i nätverket utan någon specifik avsikt att nå en viss punkt, eller utan möjlighet att hitta den kortaste vägen för att nå sitt mål. Ett exempel på en slumpmässig vandring i ett nätverk är hur ett visst mynt cirkulerar i en ekonomi: det överförs från en person till en annan genom transaktioner, utan avsikt att nå en specifik individ. Ett annat exempel där konceptet med kortaste vägar inte är särskilt användbart är ett tätt sammankopplat nätverk. Dessutom, eftersom kortaste vägar inte påverkas av självslingor , är random walk closeness centrality ett mer adekvat mått än närhet centralitet när man analyserar nätverk där självloopar är viktiga.

En viktig tillämpning på ekonomiområdet är analysen av input-output-modellen för en ekonomi, som representeras av ett tätt sammankopplat vägt nätverk med viktiga självslingor .

Konceptet används flitigt även inom naturvetenskap. En biologisk tillämpning är analysen av protein-protein-interaktioner .

Random walk betweenness centralitet

Ett relaterat koncept, som föreslås av Newman, är random walk betweenness centrality . Precis som random walk closeness centrality är en random walk motsvarighet till närhet centrality , random walk betweenness centrality är på samma sätt den random walk motsvarighet till mellanness centrality . Till skillnad från det vanliga måttet mellanness centralitet, räknar det inte bara de kortaste vägarna som passerar genom den givna noden, utan alla möjliga vägar som korsar den.

Formellt är den random walk betweenness centraliteten för en nod

$C_{i}^{RWB}=\summa _{j\neq i\neq k}r_{jk}$

där elementet $r_{jk}$ i matris R innehåller sannolikheten för att en slumpmässig vandring börjar vid nod j med absorberande nod k, som går genom nod i.

Att beräkna random walk betweenness i stora nätverk är beräkningsmässigt mycket intensivt.

Andra ordningens centralitet

En annan slumpmässig vandringsbaserad centralitet är andra ordningens centralitet . Istället för att räkna de kortaste vägarna som går genom en given nod (som för slumpmässig vandring mellan centralitet), fokuserar den på en annan egenskap hos slumpmässiga vandringar på grafer. Förväntningen på standardavvikelsen för returtiderna för en slumpmässig promenad till en nod utgör dess centralitet . Ju lägre avvikelse, desto mer central är den noden.

Att beräkna andra ordningens mellanrum på stora godtyckliga grafer är också intensivt, eftersom dess komplexitet är $O(n^{3})$ (värsta fallet uppnås på Lollipop-grafen ).

Se även

• Centralitet