Centralność bliskości

W spójnym grafie centralność bliskości (lub bliskość ) węzła jest miarą centralności w sieci , obliczoną jako odwrotność sumy długości najkrótszych ścieżek między węzłem a wszystkimi innymi węzłami w grafie. Zatem im bardziej centralny jest węzeł, tym bliżej wszystkich innych węzłów.

Distance and shortest path in a simple graph.

Liczba obok każdego węzła to odległość od tego węzła do kwadratowego czerwonego węzła mierzona długością najkrótszej ścieżki. Zielone krawędzie przedstawiają jedną z dwóch najkrótszych ścieżek między węzłem czerwonego kwadratu a węzłem czerwonego koła. Bliskość węzła czerwonego kwadratu wynosi zatem 5/(1+1+1+2+2) = 5/7.

została zdefiniowana przez Bavelasa (1950) jako odwrotność oddalenia , czyli:

{\ Displaystyle C_ {B} (x) = {\ Frac {1} {\ suma _ {y} d (y, x)}}.}

gdzie jest odległością (długością najkrótszej ścieżki) między wierzchołkami i $($ $( y , x )$ $)}$ . Ta nieznormalizowana wersja bliskości jest czasami nazywana statusem. Mówiąc o centralności bliskości, ludzie zwykle odnoszą się do jej znormalizowanej postaci, która reprezentuje średnią długość najkrótszych ścieżek zamiast ich sumy. Ogólnie jest to podane przez poprzedni wzór pomnożony przez , gdzie jest liczbą węzłów na wykresie, co daje: $\ displaystyle N-1$ $}$

{\ Displaystyle C (x) = {\ Frac {N-1} {\ suma _ {y} d (y, x)}}.}

Normalizacja bliskości upraszcza porównywanie węzłów w grafach o różnych rozmiarach. W przypadku dużych wykresów minus jeden w normalizacji staje się nieistotny i często jest odrzucany.

Jako jedna z najstarszych miar centralności, bliskość jest często podawana w ogólnych dyskusjach na temat miar centralności sieci w tekstach wprowadzających lub w artykułach porównujących różne miary centralności. Wartości wytwarzane przez wiele miar centralności mogą być wysoce skorelowane. W szczególności wykazano , że bliskość i stopień są powiązane w wielu sieciach poprzez przybliżony związek

{\ Displaystyle {\ Frac {1} {C (x)}} \ około {\ Frac {-1} {\ ln(z-1)}}\ln(k_{x})+\beta }

gdzie ${\ textstyle k_ {x}}$ to stopień wierzchołka $podczas$ gdy $dopasowanie$ bliskości i stopnia do tego wzoru. Parametr z reprezentuje współczynnik rozgałęzienia, średni stopień węzłów (z wyłączeniem węzła głównego i liści) drzew o najkrótszej ścieżce używanych do przybliżania sieci podczas demonstrowania tej zależności. To nigdy nie jest dokładna zależność, ale oddaje trend obserwowany w wielu rzeczywistych sieciach.

Bliskość jest powiązana z innymi skalami długości używanymi w nauce o sieciach. Na przykład średnia długość najkrótszej ścieżki $wartości$ odległość między wierzchołkami w sieci, jest po prostu średnią odwrotnych

{\ Displaystyle \ langle \ ell \ rangle = {\ Frac {1} {N} }\sum _{x}{\frac {1}{C(x)}}={\frac {1}{N(N-1)}}\sum _{x}\sum _{y}d( y,x)}

.

Przyjmowanie odległości od lub do wszystkich innych węzłów jest nieistotne w przypadku grafów nieskierowanych, podczas gdy w przypadku grafów skierowanych może dać zupełnie inne wyniki (np. witryna internetowa może mieć dużą centralność bliskości z linków wychodzących, ale niską centralność bliskości z linków przychodzących).

Aplikacje

Bliskość jest używana w wielu różnych kontekstach. W bibliometrii bliskość została wykorzystana do przyjrzenia się sposobowi, w jaki naukowcy wybierają swoje czasopisma i bibliografie z różnych dziedzin lub do pomiaru wpływu autora na dziedzinę i jego kapitał społeczny. Gdy jest używany do wybierania potencjalnych potencjalnych klientów w danych klienta, bliskość okazała się prowadzić do znacznego wzrostu wskaźnika sukcesu. Wykazano, że bliskość miasta do sieci transportu lotniczego jest silnie skorelowana ze wskaźnikami społeczno-ekonomicznymi, takimi jak regionalny produkt krajowy brutto. Bliskość została również zastosowana do sieci biologicznych, gdzie na przykład została wykorzystana do zidentyfikowania ponad 50% globalnych regulatorów w obrębie 2% najwyżej sklasyfikowanych genów lub stwierdzono, że geny podstawowe mają większą bliskość niż nieistotne geny w białkach sieci interakcji. W sieci metabolicznej bliskość węzłów może identyfikować najważniejsze metabolity.

W rozłączonych grafach

Kiedy wykres nie jest $.$ powiązany , Beauchamp zamiast odwrotności sumy odległości, zgodnie z :

{\ Displaystyle H (x) = \ suma _ {y \ neq x} {\ Frac {n-1} {d (y, x)}}.}

Modyfikacja Beauchampa jest zgodna z (znacznie późniejszą) ogólną zasadą zaproponowaną przez Marchiori i Latora (2000), że w grafach o nieskończonych odległościach średnia harmoniczna zachowuje się lepiej niż średnia arytmetyczna. Rzeczywiście, bliskość Bavelasa można opisać jako zdenormalizowaną odwrotność średniej arytmetycznej odległości, podczas gdy centralność Beauchampa jest odwrotnością średniej harmonicznej odległości.

$dla$ kilkakrotnie w literaturze, często bez współczynnika normalizacji grafów nieskierowanych pod nazwą centralność wartościowana przez Dekkera (2005) i pod nazwą harmoniczna autorstwa Rochata (2009) ; if został aksjomatyzowany przez Garga (2009) i ponownie zaproponowany później przez Opsahla (2010). Zostało to zbadane na grafach skierowanych ogólnie przez Boldi i Vigna (2014). Pomysł ten jest również dość podobny do potencjału rynkowego zaproponowanego przez Harrisa (1954), który obecnie często określany jest jako dostęp do rynku.

Warianty

Dangalchev (2006) w pracy na temat podatności sieci proponuje dla grafów nieskierowanych inną definicję:

{\ Displaystyle D (x) = \ suma _ {y \ neq x} {\ Frac {1} {2 ^ {d (y, x)}}}.}

Ta definicja jest skutecznie wykorzystywana do grafów rozłączonych i pozwala tworzyć wygodne formuły operacji na grafach. Na przykład:

Jeśli wykres $G_ {1}$ tworzony przez połączenie węzła wykresu $z$ sol $1$ $Displaystyle$ + $q}$ wykresu, to połączona bliskość to: ${\ displaystyle G_ {2}}$

{\ Displaystyle D (G_ {1} + G_ {2}) = D (G_ {1}) + D (G_ {2}) + (1 + D (p)) (1 + D (q));}

sol ${\ Displaystyle G_ {1} + G_ {2}}$ jest tworzony przez zwijanie węzła $wykresu$ węzła sol $G_ {1}}$ $q}$ $\ Displaystyle$ wykresu w jeden węzeł, to bliskość wynosi: ${\ displaystyle G_ {2}}$

{\ Displaystyle D (G_ {1} + G_ {2}) = D (G_ {1}) + D (G_ {2}) + 2D (p) D (q).}

Jeśli wykres $jest$ wykresem cierniowym wykresu $węzły$ $\ Displaystyle T$ ma , to $sol$ bliskość to:

{\ Displaystyle D (T (G)) = {\ Frac {9} {4}} D (G) + n.}

Naturalnym uogólnieniem tej definicji jest:

{\ Displaystyle D (x) = \ suma _ {y \ neq x} \ {\ alfa ^ {d (y, x)}}}

gdzie $0,1$ ). Wraz ze wzrostem od 0 do 1 uogólniona bliskość zmienia się z charakterystyki lokalnej (stopień) na globalną (liczba połączonych węzłów $)$

Informacyjna centralność Stephensona i Zelena (1989) jest kolejną miarą bliskości, która oblicza średnią harmoniczną odległości rezystancji w kierunku wierzchołka x , która jest mniejsza, jeśli x ma wiele ścieżek o małym oporze łączących go z innymi wierzchołkami.

W klasycznej definicji centralności bliskości rozprzestrzenianie się informacji jest modelowane za pomocą najkrótszych ścieżek. Ten model może nie być najbardziej realistyczny dla wszystkich typów scenariuszy komunikacji. W związku z tym omówiono pokrewne definicje do pomiaru bliskości, takie jak centralność bliskości spaceru losowego wprowadzona przez Noh i Rieger (2004). Mierzy prędkość, z jaką losowo poruszające się wiadomości docierają do wierzchołka z innego miejsca na grafie. Hierarchiczna bliskość Tran i Kwon (2014) to rozszerzona centralność bliskości, która jeszcze w inny sposób radzi sobie z ograniczeniem bliskości w grafach, które nie są silnie powiązane. Hierarchiczna bliskość zawiera jawnie informację o zasięgu innych węzłów, na które dany węzeł może oddziaływać.

Zobacz też