Betweenness-Zentralität

Die Percolations-Zentralität ist eine Version der gewichteten Betweenness-Zentralität, berücksichtigt aber bei der Berechnung dieses Gewichts den „Zustand“ der Quell- und Zielknoten jedes kürzesten Pfades. Die Perkolation einer „Ansteckung“ tritt in komplexen Netzen in einer Reihe von Szenarien auf. So kann sich beispielsweise eine virale oder bakterielle Infektion über soziale Netze von Menschen, so genannte Kontaktnetze, ausbreiten. Die Ausbreitung von Krankheiten kann auch auf einer höheren Abstraktionsebene betrachtet werden, indem man sich ein Netz von Städten oder Bevölkerungszentren vorstellt, die durch Straßen-, Eisenbahn- oder Flugverbindungen miteinander verbunden sind. Computerviren können sich über Computernetzwerke verbreiten. Gerüchte oder Nachrichten über Geschäftsangebote und -abschlüsse können sich auch über soziale Netzwerke von Menschen verbreiten. In all diesen Szenarien breitet sich eine „Ansteckung“ über die Verbindungen eines komplexen Netzes aus und verändert die „Zustände“ der Knotenpunkte, während sie sich ausbreitet, entweder auf erholsame oder andere Weise. In einem epidemiologischen Szenario zum Beispiel gehen Individuen bei der Ausbreitung der Infektion von einem „anfälligen“ in einen „infizierten“ Zustand über. Die Zustände, die die einzelnen Knoten in den oben genannten Beispielen einnehmen können, können binär (z. B. eine Nachricht erhalten/nicht erhalten), diskret (anfällig/infiziert/erholt) oder sogar kontinuierlich (z. B. der Anteil der infizierten Personen in einer Stadt) sein, wenn sich die Ansteckung ausbreitet. Das gemeinsame Merkmal all dieser Szenarien ist, dass die Ausbreitung der Ansteckung zu einer Veränderung der Knotenzustände in den Netzwerken führt. Vor diesem Hintergrund wurde die Perkolationszentralität (PC) vorgeschlagen, die speziell die Bedeutung von Knoten in Bezug auf die Unterstützung der Perkolation durch das Netzwerk misst. Dieses Maß wurde von Piraveenan et al.

Die Perkolationszentralität ist für einen bestimmten Knoten zu einem bestimmten Zeitpunkt definiert als der Anteil der „Perkolationspfade“, die durch diesen Knoten verlaufen. Ein „Perkolationspfad“ ist der kürzeste Pfad zwischen einem Knotenpaar, bei dem der Ausgangsknoten perkoliert (z. B. infiziert) ist. Der Zielknoten kann perkoliert oder nicht perkoliert sein oder sich in einem teilweise perkolierten Zustand befinden.

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

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

die Gesamtzahl der kürzesten Wege vom Knoten s {\displaystyle s}

zum Knoten r {\displaystyle r}

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

ist die Anzahl der Pfade, die durch v {\displaystyle v}

verlaufen. Der Perkolationszustand des Knotens i {\displaystyle i}

zum Zeitpunkt t {\displaystyle t}

wird bezeichnet durch x t i {\displaystyle {x^{t}}_{i}}

und zwei Sonderfälle sind, wenn x t i = 0 {\displaystyle {x^{t}}_{i}=0}

, was einen nicht-perkolierten Zustand zum Zeitpunkt t bedeutet {\displaystyle t}

, während bei x t i = 1 {\displaystyle {x^{t}}_{i}=1}

, was auf einen vollständig durchgesickerten Zustand zum Zeitpunkt t {\displaystyle t}

. Die Werte dazwischen geben teilweise durchlässige Zustände an (in einem Netz von Gemeinden wäre dies z. B. der Prozentsatz der Infizierten in dieser Stadt).

Die Gewichtung der Perkolationspfade hängt von den Perkolationsgraden ab, die den Quellknoten zugeordnet sind, wobei davon ausgegangen wird, dass die Pfade, die von diesem Knoten ausgehen, umso wichtiger sind, je höher der Perkolationsgrad eines Quellknotens ist. Knoten, die auf kürzesten Wegen liegen, die von Knoten mit hohem Perkolationsgrad ausgehen, sind daher potenziell wichtiger für die Perkolation. Die Definition der PC kann auch um die Gewichte der Zielknoten erweitert werden. Perkolationszentralitätsberechnungen laufen in O ( N M ) {\displaystyle O(NM)}

Zeit mit einer effizienten Implementierung, die von Brandes‘ schnellem Algorithmus übernommen wurde, und wenn die Berechnung Zielknotengewichte berücksichtigen muss, beträgt die Zeit im schlimmsten Fall O ( N 3 ) {\displaystyle O(N^{3})}