Centralna bliskość losowego spaceru

Centralność przypadkowego spaceru jest miarą centralności w sieci , która opisuje średnią prędkość, z jaką procesy losowego spaceru docierają do węzła z innych węzłów sieci. Jest podobny do centralności bliskości , z wyjątkiem tego, że odległość jest mierzona oczekiwaną długością przypadkowego spaceru , a nie najkrótszą ścieżką .

Koncepcja została po raz pierwszy zaproponowana przez White'a i Smytha (2003) pod nazwą centralność Markowa .

Intuicja

Rozważmy sieć ze skończoną liczbą węzłów i procesem błądzenia losowego, który rozpoczyna się w określonym węźle i przechodzi od węzła do węzła wzdłuż krawędzi. Z każdego węzła wybiera losowo krawędź, za którą ma podążać. W sieci nieważonej prawdopodobieństwo wybrania określonej krawędzi jest równe dla wszystkich dostępnych krawędzi, podczas gdy w sieci ważonej jest proporcjonalne do wag krawędzi. Węzeł jest uważany za znajdujący się blisko innych węzłów, jeśli proces błądzenia losowego zainicjowany z dowolnego węzła sieci dociera do tego konkretnego węzła średnio w stosunkowo kilku krokach.

Definicja

Rozważmy sieć ważoną – skierowaną lub niekierowaną – z n węzłami oznaczonymi przez j=1, …, n; i proces błądzenia losowego w tej sieci z macierzą przejścia M. $Element$ opisuje prawdopodobieństwo, że element błądzenia losowego, który dotarł do węzła i, przejdzie bezpośrednio do węzła Prawdopodobieństwa te definiuje się w następujący sposób.

$\ Displaystyle m_ {ij} = {\ Frac {a_ {ij}}} {\ suma _ {k = 1} ^ {n} a_ {ik}} }}$

gdzie $j$ ) tym elementem macierzy wag A sieci. za ja jot {\ displaystyle a_ {ij} Kiedy nie ma krawędzi między dwoma węzłami, odpowiedni element macierzy A wynosi zero.

Centralność bliskości spaceru losowego węzła i jest odwrotnością średniego średniego czasu pierwszego przejścia do tego węzła:

${\ Displaystyle C_ {i} ^ {RWC} = {\ Frac {n} {\ suma _ {j = 1} ^ {n} H (j, i)}}}$

gdzie jest średnim czasem pierwszego przejścia z węzła j do węzła i. ${\ Displaystyle H (j, i)}$

Średni czas pierwszego przejścia

Średni czas pierwszego przejścia z węzła i do węzła j to oczekiwana liczba kroków potrzebnych procesowi do osiągnięcia węzła j z węzła i po raz pierwszy:

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

gdzie P(i,j,r) oznacza prawdopodobieństwo, że potrzeba dokładnie r kroków, aby osiągnąć j z i po raz pierwszy. Aby obliczyć te prawdopodobieństwa dotarcia do węzła po raz pierwszy w r krokach, warto uznać węzeł docelowy za absorbujący i wprowadzić transformację M poprzez usunięcie jego j-tego wiersza i kolumny i oznaczenie go przez ${\ Displaystyle M_ {- j}}$ . Ponieważ prawdopodobieństwo procesu rozpoczynającego się od i i znajdującego się w k po krokach r-1 jest po prostu określone przez (i, k) -ty element $- j} ^ {r-1 }}$ , P(i,j,r) można wyrazić jako

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

Podstawiając to do wyrażenia na średni czas pierwszego przejścia, otrzymujemy

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

Wykorzystanie wzoru na sumowanie szeregów geometrycznych dla macierzy wydajności

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

gdzie I jest n-1-wymiarową macierzą tożsamości .

Dla wygody obliczeniowej to wyrażenie można zwektoryzować jako

${\ Displaystyle H (., j) = (IM_ {- j}) ^ {- 1} e}$

gdzie jest $wektorem$ czasów pierwszego przejścia dla spaceru kończącego się w węźle j, a e jest n-

Średni czas pierwszego przejścia nie jest symetryczny, nawet dla grafów nieskierowanych.

W sieciach modelowych

Zgodnie z symulacjami przeprowadzonymi przez Noh i Rieger (2004), rozkład centralności spaceru losowego w modelu Barabásiego-Alberta jest determinowany głównie przez rozkład stopni . W takiej sieci centralność bliskości węzła losowego jest z grubsza proporcjonalna do, ale nie rośnie monotonicznie wraz z jej stopniem.

Aplikacje dla rzeczywistych sieci

Losowa centralność bliskości jest bardziej odpowiednią miarą niż prosta centralność bliskości w przypadku aplikacji, w których koncepcja najkrótszych ścieżek nie ma sensu lub jest bardzo restrykcyjna dla rozsądnej oceny natury systemu. Dzieje się tak na przykład wtedy, gdy analizowany proces ewoluuje w sieci bez konkretnej intencji dotarcia do określonego punktu lub bez możliwości znalezienia najkrótszej drogi do celu. Jednym z przykładów błądzenia losowego w sieci jest sposób, w jaki pewna moneta krąży w gospodarce: jest przekazywana od jednej osoby do drugiej poprzez transakcje, bez zamiaru dotarcia do konkretnej osoby. Innym przykładem, w którym koncepcja najkrótszych ścieżek nie jest zbyt użyteczna, jest gęsto połączona sieć. Co więcej, na najkrótsze ścieżki nie mają wpływu pętle własne , centralność bliskości losowego spaceru jest bardziej odpowiednią miarą niż centralność bliskości podczas analizowania sieci, w których ważne są pętle własne .

Ważnym zastosowaniem w dziedzinie ekonomii jest analiza modelu przepływów międzygałęziowych gospodarki, który jest reprezentowany przez gęsto połączoną ważoną sieć z ważnymi pętlami własnymi .

Pojęcie to jest szeroko stosowane również w naukach przyrodniczych. Jednym z zastosowań biologicznych jest analiza interakcji białko-białko .

Losowy spacer między centralnością

Pokrewną koncepcją, zaproponowaną przez Newmana, jest losowe spacerowanie pomiędzy centralnością . Podobnie jak losowy spacer bliskości centralności jest odpowiednikiem losowego spaceru bliskości centralności , losowy spacer między centralności jest podobnie przypadkowym odpowiednikiem spaceru centralności między . W przeciwieństwie do zwykłej miary centralności pomiędzy, nie tylko zlicza najkrótsze ścieżki przechodzące przez dany węzeł, ale wszystkie możliwe ścieżki przez niego przecinające.

Formalnie centralność węzła w przypadku błądzenia losowego między węzłami wynosi

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

gdzie $macierzy$ zawiera prawdopodobieństwo błądzenia losowego rozpoczynającego się w węźle j z węzłem pochłaniającym k, przechodzącego przez węzeł i

Obliczanie losowego spaceru między dużymi sieciami jest bardzo intensywne obliczeniowo.

Centralność drugiego rzędu

Inną centralnością opartą na błądzeniu losowym jest centralność drugiego rzędu . Zamiast liczyć najkrótsze ścieżki przechodzące przez dany węzeł (jak w przypadku losowego spaceru między centralnością), skupia się na innej charakterystyce spacerów losowych na grafach. Oczekiwanie odchylenia standardowego czasów powrotu błądzenia losowego do węzła stanowi o jego centralności . Im mniejsze odchylenie, tym bardziej centralny jest ten węzeł.

$przypadek$ pośredniości drugiego rzędu na dużych dowolnych wykresach jest również intensywne, ponieważ jego złożoność jest osiągnięty na wykresie )

Zobacz też

• Centralność