Centralidad de intermediación

En teoría de grafos , la centralidad de intermediación es una medida de centralidad en un grafo basada en los caminos más cortos . La centralidad de intermediación mide con qué frecuencia un nodo aparece en el camino más corto entre otros nodos del grafo. Para cada par de vértices en un grafo conexo , existe al menos un camino más corto entre ellos; es decir, existe al menos un camino tal que se minimiza el número de aristas por las que pasa (para grafos no ponderados) o la suma de los pesos de las aristas (para grafos ponderados).

La centralidad de intermediación se ideó como una medida general de centralidad: ^{[ 1 ]} . Se aplica a una amplia gama de problemas en la teoría de redes, incluyendo problemas relacionados con redes sociales , biología, transporte y cooperación científica. Si bien autores anteriores habían descrito intuitivamente la centralidad en términos de intermediación, Freeman (1977) dio la primera definición formal de centralidad de intermediación.

La centralidad de intermediación tiene una amplia aplicación en la teoría de redes ; mide el grado de proximidad entre los nodos. Por ejemplo, en una red de telecomunicaciones , un nodo con mayor centralidad de intermediación tendría más control sobre la red, ya que fluye más información a través de él.

La centralidad de intermediación de un nodo${\displaystyle v}$viene dada por la expresión:

${\displaystyle g(v)=\sum _{s\neq v\neq t}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}$

dónde${\displaystyle \sigma _{st}}$es el número total de caminos más cortos desde el nodo${\displaystyle s}$al nodo${\displaystyle t}$y${\displaystyle \sigma _ {st}(v)}$es el número de esos caminos que pasan por${\displaystyle v}$(no dónde${\displaystyle v}$es un punto final). ^{[ 2 ]}

La centralidad de intermediación de un nodo se escala con el número de pares de nodos como sugieren los índices de suma. Por lo tanto, el cálculo puede reescalarse dividiendo por el número de pares de nodos sin incluir${\displaystyle v}$, de modo que${\displaystyle g\in [0,1]}$La división se realiza mediante${\displaystyle (N-1)(N-2)}$para grafos dirigidos y${\displaystyle (N-1)(N-2)/2}$para grafos no dirigidos , donde${\displaystyle N}$es el número de nodos en el componente gigante . Tenga en cuenta que esto se escala para el valor más alto posible, donde un nodo es atravesado por cada camino más corto. Esto no suele ser así, y se puede realizar una normalización sin pérdida de precisión.

${\displaystyle {\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}}$

lo cual resulta en:

${\displaystyle \max({\mbox{normal}})=1}$

${\displaystyle \min({\mbox{normal}})=0}$

Tenga en cuenta que siempre se tratará de una ampliación de un rango menor a un rango mayor, por lo que no se pierde precisión.

En una red ponderada, los enlaces que conectan los nodos ya no se tratan como interacciones binarias, sino que se ponderan en proporción a su capacidad, influencia, frecuencia, etc., lo que añade otra dimensión de heterogeneidad a la red, más allá de los efectos topológicos. La fuerza de un nodo en una red ponderada viene dada por la suma de los pesos de sus aristas adyacentes.

${\displaystyle s_{i}=\sum _ {j=1}^{N}a_ {ij}w_ {ij}}$

Con${\displaystyle a_{ij}}$y${\displaystyle w_{ij}}$siendo matrices de adyacencia y peso entre nodos${\displaystyle i}$y${\displaystyle j}$, respectivamente. De forma análoga a la distribución de ley de potencias del grado que se encuentra en las redes libres de escala, la fuerza de un nodo dado también sigue una distribución de ley de potencias.

${\displaystyle s(k)\approx k^{\beta }}$

Un estudio del valor promedio${\displaystyle s(b)}$de la fuerza para vértices con intermediación${\displaystyle b}$muestra que el comportamiento funcional puede aproximarse mediante una forma de escala: ^{[ 3 ]}

${\displaystyle s(b)\approx b^{\alpha }}$

La centralidad de percolación es una versión de la centralidad de intermediación ponderada, pero considera el "estado" de los nodos de origen y destino de cada ruta más corta al calcular este peso. La percolación de un "contagio" ocurre en redes complejas en diversos escenarios. Por ejemplo, una infección viral o bacteriana puede propagarse a través de redes sociales de personas, conocidas como redes de contacto. La propagación de enfermedades también puede considerarse a un nivel de abstracción superior, al contemplar una red de ciudades o centros de población conectados por carreteras, ferrocarriles o vías aéreas. Los virus informáticos pueden propagarse a través de redes informáticas. Los rumores o noticias sobre ofertas y acuerdos comerciales también pueden propagarse a través de redes sociales de personas. En todos estos escenarios, un "contagio" se propaga a través de los enlaces de una red compleja, alterando los "estados" de los nodos a medida que se propaga, ya sea de forma reversible o irreversible. Por ejemplo, en un escenario epidemiológico, los individuos pasan del estado "susceptible" al estado "infectado" a medida que se propaga la infección. Los estados que pueden adoptar los nodos individuales en los ejemplos anteriores podrían ser binarios (como haber recibido o no una noticia), discretos (susceptible/infectado/recuperado) o incluso continuos (como la proporción de personas infectadas en una ciudad), a medida que se propaga el contagio. La característica común en todos estos escenarios es que la propagación del contagio provoca un cambio en los estados de los nodos en las redes. La centralidad de percolación (PC) se propuso teniendo esto en cuenta, y mide específicamente la importancia de los nodos en términos de facilitar la percolación a través de la red. Esta medida fue propuesta por Piraveenan, Prokopenko y Hossain (2013) . ^{[ 4 ]}

La centralidad de percolación se define para un nodo dado, en un momento dado, como la proporción de "caminos percolados" que pasan por ese nodo. Un "camino percolado" es el camino más corto entre un par de nodos, donde el nodo de origen está percolado (por ejemplo, infectado). El nodo de destino puede estar percolado o no percolado, o en un estado parcialmente percolado.

${\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}}_{i}}]}-{x^{t}}_{v}}}}$

dónde${\displaystyle \sigma _{sr}}$es el número total de caminos más cortos desde el nodo${\displaystyle s}$al nodo${\displaystyle r}$y${\displaystyle \sigma _{sr}(v)}$es el número de esos caminos que pasan por${\displaystyle v}$. El estado de percolación del nodo${\displaystyle i}$en ese momento${\displaystyle t}$se denota por${\displaystyle {x^{t}}_{i}}$y dos casos especiales son cuando${\displaystyle {x^{t}}_{i}=0}$lo que indica un estado no percolado en el tiempo${\displaystyle t}$mientras que cuando${\displaystyle {x^{t}}_{i}=1}$lo que indica un estado de percolación completa en el tiempo${\displaystyle t}$Los valores intermedios indican estados parcialmente percolados (por ejemplo, en una red de municipios, este sería el porcentaje de personas infectadas en ese municipio).

Los pesos adjuntos a las rutas de percolación dependen de los niveles de percolación asignados a los nodos de origen, basándose en la premisa de que cuanto mayor sea el nivel de percolación de un nodo de origen, más importantes serán las rutas que se originan en ese nodo. Por lo tanto, los nodos que se encuentran en las rutas más cortas que se originan en nodos altamente percolados son potencialmente más importantes para la percolación. La definición de PC también puede extenderse para incluir los pesos de los nodos de destino. Los cálculos de centralidad de percolación se ejecutan en${\displaystyle O(|V||E|)}$tiempo con una implementación eficiente adaptada del algoritmo de Brandes . Si el cálculo necesita considerar los pesos de los nodos objetivo, el tiempo en el peor de los casos es${\displaystyle O(|V|^{3})}$.

Calcular las centralidades de intermediación y cercanía de todos los vértices de un grafo implica calcular los caminos más cortos entre todos los pares de vértices del grafo, lo que lleva${\displaystyle \Theta (|V|^{3})}$tiempo con el algoritmo de Floyd-Warshall , modificado para no solo encontrar uno sino contar todos los caminos más cortos entre dos nodos. En un grafo disperso, el algoritmo de Johnson o el algoritmo de Brandes pueden ser más eficientes, ambos tomando${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$tiempo. En gráficos no ponderados, calcular la centralidad de intermediación lleva${\displaystyle O(|V||E|)}$tiempo utilizando el algoritmo de Brandes. ^{[ 5 ]}

Al calcular las centralidades de intermediación y cercanía de todos los vértices de un grafo, se asume que los grafos son no dirigidos y conectados, permitiendo bucles y aristas múltiples. En el caso específico de los grafos de red, a menudo no presentan bucles ni aristas múltiples para mantener relaciones simples (donde las aristas representan conexiones entre dos personas o vértices). En este caso, el algoritmo de Brandes divide las puntuaciones de centralidad finales entre 2 para tener en cuenta que cada ruta más corta se cuenta dos veces. ^{[ 6 ]}

Otro algoritmo generaliza la centralidad de Freeman calculada sobre geodésicas y la centralidad de Newman calculada sobre todos los caminos, introduciendo un hiperparámetro que controla el equilibrio entre exploración y explotación. La complejidad temporal es igual al número de aristas multiplicado por el número de nodos del grafo. ^{[ 7 ]}

La centralidad de intermediación está relacionada con la conectividad de una red , en la medida en que los vértices con alta centralidad de intermediación tienen el potencial de desconectar grafos si se eliminan (ver conjunto de corte ).

• Centralidad