Centralność pomiędzy

Wykres nieskierowany pokolorowany na podstawie centralności każdego wierzchołka od najmniejszego (czerwony) do największego (niebieski).

W teorii grafów centralność między grafami jest miarą centralności w grafie opartym na najkrótszych ścieżkach . Dla każdej pary wierzchołków w spójnym grafie istnieje co najmniej jedna najkrótsza ścieżka między wierzchołkami, taka że albo liczba krawędzi, przez które przechodzi ścieżka (dla grafów nieważonych), albo suma wag krawędzi (dla grafów ważonych ) jest zminimalizowany. Centralność pośrednia dla każdego wierzchołka to liczba tych najkrótszych ścieżek, które przechodzą przez wierzchołek.

Międzynarodowość centralność została wymyślona jako ogólna miara centralności: odnosi się do szerokiego zakresu problemów w teorii sieci, w tym problemów związanych z sieciami społecznymi , biologią, transportem i współpracą naukową. Chociaż wcześniejsi autorzy intuicyjnie opisywali centralność jako opartą na pośrednictwie, Freeman (1977) podał pierwszą formalną definicję centralności pomiędzy.

Centralność międzynarodowości znajduje szerokie zastosowanie w teorii sieci ; reprezentuje stopień, w jakim węzły stoją między sobą. Na przykład w sieci telekomunikacyjnej węzeł o większej centralności między połączeniami miałby większą kontrolę nad siecią, ponieważ przez ten węzeł przechodzi więcej informacji.

Definicja

Centralność między węzłami określa wyrażenie: ${\ displaystyle v}$

${\ Displaystyle g (v) = \ suma _ {s \ neq v \ neq t} {\ Frac {\ sigma _ {st} (v)}{\sigma _{st}}}}$

gdzie ${\ Displaystyle \ sigma _ {st}}$ to całkowita liczba najkrótszych ścieżek od węzła $Displaystyle$$σ$ i s $\ sigma _ {st} (v)}$ to liczba tych ścieżek, które przechodzą przez $($ gdzie $.$ punktem końcowym)

Należy zauważyć, że centralność między węzłami skaluje się wraz z liczbą par węzłów, zgodnie z sugestią indeksów sumowania. Dlatego obliczenie można przeskalować, dzieląc przez liczbę par węzłów bez uwzględnienia $tak$ że ${\ displaystyle g \ in [0,1]}$ . Podział jest wykonywany przez ${\ Displaystyle (N-1) (N-2)}$ dla skierowanych wykresów i ${\ Displaystyle (N -1) (N-2)/2}$ dla grafów nieskierowanych, gdzie $jest$ węzłów w gigantycznym komponencie. Należy zauważyć, że skaluje się to dla najwyższej możliwej wartości, gdzie jeden węzeł jest przecinany przez każdą najkrótszą ścieżkę. Często tak nie jest, a normalizację można przeprowadzić bez utraty precyzji

${\ Displaystyle {\ mbox {normalny}} (g (v)) = {\ Frac {g (v) )-\min(g)}{\max(g)-\min(g)}}}$

Co skutkuje w:

${\ Displaystyle \ max (normalny) = 1}$

${\ Displaystyle \ min (normalny) = 0}$

Należy zauważyć, że zawsze będzie to skalowanie z mniejszego zakresu do większego zakresu, więc precyzja nie zostanie utracona.

Sieci ważone

W sieci ważonej łącza łączące węzły nie są już traktowane jako interakcje binarne, ale są ważone proporcjonalnie do ich przepustowości, wpływu, częstotliwości itp., co dodaje kolejny wymiar heterogeniczności w sieci poza efektami topologicznymi. Siła węzła w sieci ważonej jest sumą wag sąsiednich krawędzi.

${\ Displaystyle s_ {i} = \ suma _ {j = 1} ^ {N} a_ {ij} w_ {ij}}$

gdzie ${\ displaystyle w_ {ij}}$$to$ macierze sąsiedztwa i wagi między węzłami $jot$ \ $}$ j . Analogicznie do rozkładu potęgowego stopnia występującego w sieciach bez skali, siła danego węzła jest również zgodna z rozkładem prawa potęgowego.

${\ Displaystyle s (k) \ około k ^ {\ beta}}$

Badanie średniej wartości siły dla wierzchołków z pośrednimi pokazuje $,$ że zachowanie funkcjonalne można przybliżyć za pomocą formy skalowania: ${\ Displaystyle s (b)$

${\ Displaystyle s (b) \ około b ^ {\ alfa}}$

Centralność perkolacji

Centralność perkolacji jest wersją centralności ważonej pomiędzy, ale uwzględnia „stan” węzłów źródłowych i docelowych każdej najkrótszej ścieżki przy obliczaniu tej wagi. Perkolacja „zarażenia” występuje w złożonych sieciach w wielu scenariuszach. Na przykład infekcja wirusowa lub bakteryjna może rozprzestrzeniać się w sieciach społecznościowych ludzi, zwanych sieciami kontaktów. Rozprzestrzenianie się chorób można również rozpatrywać na wyższym poziomie abstrakcji, rozważając sieć miast lub skupisk ludności połączonych połączeniami drogowymi, kolejowymi lub lotniczymi. Wirusy komputerowe mogą rozprzestrzeniać się w sieciach komputerowych. Plotki lub wiadomości o ofertach biznesowych i umowach mogą również rozprzestrzeniać się za pośrednictwem sieci społecznościowych. We wszystkich tych scenariuszach „zaraza” rozprzestrzenia się na łącza złożonej sieci, zmieniając „stany” węzłów w miarę rozprzestrzeniania się, w sposób możliwy do odzyskania lub w inny sposób. Na przykład w scenariuszu epidemiologicznym osoby przechodzą ze stanu „podatnego” do „zakażonego” w miarę rozprzestrzeniania się infekcji. Stany, które poszczególne węzły mogą przyjmować w powyższych przykładach, mogą być binarne (takie jak otrzymanie/nieotrzymanie wiadomości), dyskretne (podatne/zainfekowane/wyleczone) lub nawet ciągłe (takie jak odsetek zarażonych osób w mieście ), w miarę rozprzestrzeniania się zarazy. Wspólną cechą wszystkich tych scenariuszy jest to, że rozprzestrzenianie się zarazy powoduje zmianę stanów węzłów w sieciach. Mając to na uwadze, zaproponowano centralność perkolacji (PC), która konkretnie mierzy znaczenie węzłów pod względem wspomagania perkolacji przez sieć. Miara ta została zaproponowana przez Piraveenana, Prokopenko i Hossaina (2013) .

Centralność perkolacji jest zdefiniowana dla danego węzła w danym czasie jako odsetek „ścieżek perkolacji”, które przechodzą przez ten węzeł. „Ścieżka przesiąknięta” to najkrótsza ścieżka między parą węzłów, gdzie węzeł źródłowy jest przesiąknięty (np. zainfekowany). Węzeł docelowy może być przesiąknięty lub nie przesiąknięty lub w stanie częściowo przesiąkniętym.

${\ Displaystyle PC ^ {t} (v) ={\frac {1}{N-2}}\sum _{s\neq v\neq r}{\frac {\sigma _{sr}(v)}{\sigma _{sr}}}{\ frac {{x^{t}}_{s}}{{\suma {[{x^{t}}_{i}}]}-{x^{t}}_{v}}}}$

gdzie ${\ Displaystyle \ sigma _ {sr}}$ to całkowita liczba najkrótszych ścieżek od węzła $displaystyle$ węzła i $r}$ i ${\ Displaystyle \ sigma _ { sr} (v)}$ to liczba tych ścieżek, które przechodzą przez ${\ displaystyle v}$ . Stan perkolacji węzła w czasie jest oznaczony przez ${\ Displaystyle {x ^ {t}} _$$i}},$${$ to ${\ Displaystyle {x ^ {t}} _ {i} = 0},$ co wskazuje na stan nieprzesiąknięty w czasie ${\ displaystyle t}$ podczas gdy ${\ displaystyle {x ^ {t}} _ {i} = 1}$ , co wskazuje na stan w pełni przesiąknięty w czasie ${\ displaystyle t}$ . Wartości pośrednie wskazują stany częściowo przesiąknięte (np. w sieci miasteczek byłby to odsetek osób zarażonych w tym mieście).

Wagi dołączone do ścieżek perkolacji zależą od poziomów perkolacji przypisanych do węzłów źródłowych, w oparciu o założenie, że im wyższy jest poziom perkolacji węzła źródłowego, tym ważniejsze są ścieżki, które pochodzą z tego węzła. Węzły, które leżą na najkrótszych ścieżkach pochodzących z węzłów o wysokim stopniu perkolacji, są zatem potencjalnie ważniejsze dla perkolacji. Definicję PC można również rozszerzyć, aby obejmowała również wagi węzłów docelowych. Obliczenia centralności perkolacji przebiegają w $szybkiego$ algorytmu Brandesa i jeśli obliczenia muszą uwzględniać wagi węzłów docelowych, ${\ Displaystyle O (N ^ {3})}$ .

Algorytmy

Obliczenie centralności między i bliskości wszystkich wierzchołków na grafie obejmuje obliczenie najkrótszych ścieżek między wszystkimi parami wierzchołków na wykresie, co zajmuje ${\ Displaystyle \ Theta (| V | ^ {3}) }$ czas z algorytmem Floyda-Warshalla , zmodyfikowanym tak, aby nie tylko znaleźć jedną, ale policzyć wszystkie najkrótsze ścieżki między dwoma węzłami. Na rzadkim wykresie algorytm Johnsona lub algorytm Brandesa mogą być bardziej wydajne, przy czym oba przyjmują ${\ Displaystyle O (| V | ^ {2} \ log |V|+|V||E|)}$ czas. $Na$ zajmuje Brandesa

Przy obliczaniu centralności między i bliskości wszystkich wierzchołków grafu zakłada się, że grafy są nieskierowane i połączone z uwzględnieniem pętli i wielu krawędzi. Kiedy mamy do czynienia z grafami sieciowymi, często grafy są pozbawione pętli lub wielu krawędzi, aby zachować proste relacje (gdzie krawędzie reprezentują połączenia między dwiema osobami lub wierzchołkami). W takim przypadku użycie algorytmu Brandesa podzieli końcowe wyniki centralności przez 2, aby uwzględnić dwukrotne liczenie każdej najkrótszej ścieżki.

Inny algorytm uogólnia rozbieżności Freemana obliczone na podstawie geodezji i rozbieżności Newmana obliczone na wszystkich ścieżkach, wprowadzając hiperparametr kontrolujący kompromis między eksploracją a eksploatacją. Złożoność czasowa to liczba krawędzi pomnożona przez liczbę węzłów w grafie.

Przybliżoną, probabilistyczną ocenę centralności pośrednich można uzyskać znacznie szybciej poprzez próbkowanie ścieżek przy użyciu dwukierunkowego przeszukiwania wszerz .

Aplikacje

Portale społecznościowe

W analizie sieci społecznościowych centralność między powiązaniami może mieć różne implikacje. Z perspektywy makroskopowej pozycje pomostowe lub „dziury strukturalne” (na co wskazuje wysoka centralność pomiędzy) odzwierciedlają władzę, ponieważ pozwalają osobie na pozycji pomostowej sprawować kontrolę (np. decydować, czy dzielić się informacjami, czy nie) nad osobami, które łączy między. Z mikroskopijnej perspektywy sieci ego (tj. biorąc pod uwagę tylko połączenia pierwszego stopnia), w sieciach społecznościowych online wysoka centralność zbiega się z nominacjami najbliższych przyjaciół (tj. silne więzi międzyludzkie ), ponieważ odzwierciedla inwestycje kapitału społecznego w związek, kiedy łączenie odległych kręgów społecznych (np. rodziny i uczelni) (często wynikające z wprowadzenia przez ego).

Sieci rzeczne

złożoności topologicznej sieci rzecznych oraz ich wykorzystania w handlu morskim wykorzystano centralność międzysieciową .

Pojęcia pokrewne

Centralność między powiązaniami jest powiązana z łącznością sieci , ponieważ wierzchołki o wysokim powiązaniu mogą potencjalnie rozłączyć grafy, jeśli zostaną usunięte (patrz zbiór cięć ).

Zobacz też

• Centralność

Bibliografia

•     Barrat, A.; i in. (2004). „Architektura złożonych sieci ważonych” . Proceedings of the National Academy of Sciences of the United States of America . 101 (11): 3747–3752. arXiv : cond-mat/0311416 . Bibcode : 2004PNAS..101.3747B . doi : 10.1073/pnas.0400087101 . ISSN 0027-8424 . PMC 374315 . PMID 15007165 .
•    Borassi, Michele; Natale, Emanuele (2019). „KADABRA to algorytm adaptacyjny dla międzypośrednictwa poprzez losowe przybliżenie” . ACM Journal of Experimental Algorithmics . 24 : 1,2:1–1,2:35. doi : 10.1145/3284359 . ISSN 1084-6654 . S2CID 67871875 .
•    Brandes, Ulrik (2001). „Szybszy algorytm centralności pomiędzy” (PDF) . Dziennik socjologii matematycznej . 25 (2): 163–177. CiteSeerX 10.1.1.11.2024 . doi : 10.1080/0022250x.2001.9990249 . hdl : 10983/23603 . S2CID 13971996 . Zarchiwizowane (PDF) od oryginału w dniu 29 marca 2021 r . Źródło 29 marca 2021 r .
•    Burt, Ronald (2009). Dziury strukturalne: struktura społeczna konkurencji . Cambridge: Harvard University Press . ISBN 978-0-674-02909-5 . OCLC 1041149426 . Źródło 29 marca 2021 r .
•   Freemana, Lintona (1977). „Zestaw miar centralności opartych na pokrewieństwie”. Socjometria . 40 (1): 35–41. doi : 10.2307/3033543 . JSTOR 3033543 .
•     Goh, KI; Kahng, B.; Kim, D. (2001). „Uniwersalne zachowanie rozkładu obciążenia w sieciach bezskalowych”. Fizyczne listy przeglądowe . 87 (27): 278701. arXiv : cond-mat/0106565 . Bibcode : 2001PhRvL..87A8701G . doi : 10.1103/PhysRevLett.87.278701 . ISSN 0031-9007 . PMID 11800921 . S2CID 15746304 .
•    Mantrach, Amin; i in. (2010). „Jądro kowariancji sumy po ścieżkach: nowatorska miara kowariancji między węzłami grafu skierowanego”. Transakcje IEEE dotyczące analizy wzorców i inteligencji maszynowej . 32 (6): 1112–1126. doi : 10.1109/tpami.2009.78 . PMID 20431135 . S2CID 4807216 .
•   Moxley, Robert L.; Moxley, Nancy F. (1974). „Określanie punktu centralnego w niewymyślonych sieciach społecznościowych”. Socjometria . 37 (1): 122–130. doi : 10.2307/2786472 . JSTOR 2786472 .
•    Newman, Mark EJ (2010). Sieci: wprowadzenie . Oksford: Oxford University Press . ISBN 978-0-19-920665-0 . OCLC 964511577 .
•     Piraveenan, Mahendra; Prokopenko, Michaił; Hossain, Liaquat (2013). Holme, Petter (red.). „Centralność perkolacji: ilościowy teoretyczny wpływ węzłów na wykresy podczas perkolacji w sieciach” . PLOS JEDEN . 8 (1): e53095. Bibcode : 2013PLoSO...853095P . doi : 10.1371/journal.pone.0053095 . ISSN 1932-6203 . PMC 3551907 . PMID 23349699 .
•     Sarker, Shiblu; i in. (2019). „Krytyczne węzły w sieciach rzecznych” . Raporty naukowe . 9 (1): 11178. Bibcode : 2019NatSR...911178S . doi : 10.1038/s41598-019-47292-4 . ISSN 2045-2322 . PMC 6672004 . PMID 31371735 .
•   Stolz, Szymon; Schlereth, chrześcijanin (2021). „Przewidywanie siły powiązania za pomocą struktur sieciowych ego”. Dziennik marketingu interaktywnego . 54 (maj): 40–52. doi : 10.1016/j.intmar.2020.10.001 . S2CID 229403802 .