Betweenness centrality

Percolation centrality jest wersją ważonej betweenness centrality, ale bierze pod uwagę „stan” węzłów źródłowych i docelowych każdej najkrótszej ścieżki w obliczaniu tej wagi. Perkolacja „zarażania” występuje w złożonych sieciach w wielu scenariuszach. Na przykład, infekcja wirusowa lub bakteryjna może rozprzestrzeniać się w społecznych sieciach ludzi, zwanych sieciami kontaktowymi. Rozprzestrzenianie się choroby można również rozważać na wyższym poziomie abstrakcji, rozważając sieć miast lub skupisk ludności, połączonych drogami, koleją lub połączeniami lotniczymi. Wirusy komputerowe mogą rozprzestrzeniać się przez sieci komputerowe. Plotki lub wiadomości o ofertach biznesowych i transakcjach mogą również rozprzestrzeniać się poprzez sieci społeczne ludzi. We wszystkich tych scenariuszach „zaraza” rozprzestrzenia się przez ogniwa złożonej sieci, zmieniając „stany” węzłów w miarę rozprzestrzeniania się, w sposób możliwy do odzyskania lub inny. Na przykład w scenariuszu epidemiologicznym jednostki przechodzą ze stanu „podatnego” do „zakażonego” w miarę rozprzestrzeniania się infekcji. Stany, które poszczególne węzły mogą przyjąć w powyższych przykładach mogą być binarne (takie jak otrzymanie/nieotrzymanie wiadomości), dyskretne (podatny/zarażony/zdrowiał), lub nawet ciągłe (takie jak proporcja zarażonych ludzi w mieście), w miarę rozprzestrzeniania się zarażenia. Wspólną cechą wszystkich tych scenariuszy jest to, że rozprzestrzenianie się zarazy powoduje zmianę stanu węzłów w sieciach. Z myślą o tym zaproponowano centralność perkolacyjną (PC), która mierzy znaczenie węzłów pod względem wspomagania perkolacji w sieci. Miara ta została zaproponowana przez Piraveenan et al.

Centralność perkolacyjna jest definiowana dla danego węzła, w danym czasie, jako odsetek „ścieżek perkolacyjnych”, które przechodzą przez ten węzeł. Ścieżka perkolacyjna” to najkrótsza ścieżka pomiędzy parą węzłów, gdzie węzeł źródłowy jest perkolowany (np. zainfekowany). Węzeł docelowy może być perkolowany lub nieperkolowany, lub w stanie częściowej perkolacji.

P C t ( v ) = 1 N – 2 ∑ s ≠ v ≠ r σ s r ( v ) σ s r x t s ∑ – x t v { {styl PC^{t}(v)={frac {1}{N-2}} suma {{sigma _{sr}(v)}}{{sigma _{sr}}}}{}frac {{x^{t}}}_{s}}{{suma {}-{x^{t}}_{v}}}}

gdzie σ s r {{displaystyle \sigma _{sr}}

jest całkowitą liczbą najkrótszych ścieżek od węzła s {{displaystyle s}

do węzła r {{displaystyle r}}

oraz σ s r ( v ) {{displaystyle \sigma _{sr}(v)}

jest liczbą tych ścieżek, które przechodzą przez v {displaystyle v}

. Stan perkolacji węzła i {{displaystyle}

w czasie t {{displaystyle t}

jest oznaczany przez x t i {{displaystyle {x^{t}}_{i}}

, a dwa szczególne przypadki to gdy x t i = 0 {{displaystyle {x^{t}}_{i}=0}

co oznacza stan nieperkolowany w czasie t {displaystyle t}

natomiast gdy x t i = 1 {{displaystyle {x^{t}}_{i}=1}

co oznacza stan pełnej perkolacji w czasie t {{displaystyle t}

. Wartości pomiędzy nimi wskazują na stany częściowo przesiąknięte (np. w sieci miast byłby to procent osób zainfekowanych w danym mieście).

Wagi przypisane 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 wychodzące z tego węzła. Węzły, które leżą na najkrótszych ścieżkach pochodzących od węzłów o wysokim poziomie perkolacji są zatem potencjalnie ważniejsze dla perkolacji. Definicja PC może być również rozszerzona o wagi węzłów docelowych. Percolation centrality calculations run in O ( N M ) {displaystyle O(NM)}

czasu przy wydajnej implementacji zaadoptowanej z szybkiego algorytmu Brandesa, a jeśli w obliczeniach trzeba uwzględnić wagi węzłów docelowych, najgorszy czas wynosi O ( N 3 ) {displaystyle O(N^{3})}