Centralidad de intermediación

Medida de la centralidad de un gráfico, basada en los caminos más cortos.

Un gráfico no dirigido coloreado según la centralidad de intermediación de cada vértice desde el menor (rojo) hasta el mayor (azul).

En teoría de grafos , la centralidad de intermediación es una medida de centralidad en un gráfico basada en caminos más cortos . Para cada par de vértices en un gráfico conectado, existe al menos un camino más corto entre los vértices, de modo que el número de aristas por las que pasa el camino (para gráficos no ponderados) o la suma de los pesos de los aristas (para gráficos ponderados) ) se minimiza. La centralidad de intermediación para cada vértice es el número de estos caminos más cortos que pasan por el vértice.

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, incluidos problemas relacionados con las redes sociales , la biología, el transporte y la cooperación científica. Aunque autores anteriores han descrito intuitivamente la centralidad como basada en la intermediación, Freeman (1977) dio la primera definición formal de centralidad de intermediación.

La centralidad de intermediación encuentra una amplia aplicación en la teoría de redes ; Representa el grado en que los nodos se encuentran entre sí. Por ejemplo, en una red de telecomunicaciones , un nodo con mayor centralidad de intermediación tendría más control sobre la red, porque a través de ese nodo pasará más información.

Definición

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

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

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

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

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

lo que resulta en:

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

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

Tenga en cuenta que esto siempre será una escala de un rango más pequeño a un rango más grande, por lo que no se pierde precisión.

Redes ponderadas

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 dentro de 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 bordes adyacentes.

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

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

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

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

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

Centralidad de percolación

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 camino más corto al calcular este peso. La filtración de un "contagio" se produce en redes complejas en varios escenarios. Por ejemplo, una infección viral o bacteriana puede propagarse a través de las redes sociales de personas, conocidas como redes de contacto. La propagación de enfermedades también puede considerarse en un nivel más alto de abstracción, contemplando 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 las redes informáticas. Los rumores o noticias sobre ofertas y acuerdos comerciales también pueden difundirse a través de las redes sociales de las 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 recuperable o no. 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 los nodos individuales pueden tomar en los ejemplos anteriores podrían ser binarios (como recibió/no recibió 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 de todos estos escenarios es que la propagación del contagio da como resultado el cambio de estados de los nodos en las redes. Con esto en mente, se propuso la centralidad de percolación (PC), que mide específicamente la importancia de los nodos en términos de ayudar a la percolación a través de la red. Esta medida fue propuesta por Piraveenan, Prokopenko & Hossain (2013). ^[4]

La centralidad de percolación se define para un nodo determinado, en un momento dado, como la proporción de "caminos filtrados" que pasan por ese nodo. Una 'ruta filtrada' es una ruta más corta entre un par de nodos, donde el nodo fuente se filtra (por ejemplo, se infecta). El nodo objetivo puede estar filtrado o no filtrado, o en un estado parcialmente filtrado.

${\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}}}}$

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

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

Algoritmos

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

Al calcular las centralidades de intermediación y cercanía de todos los vértices de un gráfico, se supone que los gráficos no están dirigidos y están conectados con la tolerancia de bucles y múltiples aristas. Cuando se trata específicamente de gráficos de red, a menudo los gráficos no tienen bucles ni múltiples aristas para mantener relaciones simples (donde las aristas representan conexiones entre dos personas o vértices). En este caso, el uso del algoritmo de Brandes dividirá las puntuaciones de centralidad finales por 2 para tener en cuenta que cada camino más corto se cuenta dos veces. ^[6]

Otro algoritmo generaliza la intermediación de Freeman calculada en geodésicas y la intermediación de Newman calculada en todos los caminos, mediante la introducción de un hiperparámetro que controla el equilibrio entre exploración y explotación. La complejidad temporal es el número de aristas multiplicado por el número de nodos en el gráfico. ^[7]

Se puede obtener una estimación probabilística aproximada de las centralidades de intermediación mucho más rápido muestreando rutas utilizando una búsqueda bidireccional de amplitud primero . ^[8]

Aplicaciones

Redes sociales

En el análisis de redes sociales , la centralidad de intermediación puede tener diferentes implicaciones. Desde una perspectiva macroscópica, las posiciones puente o "agujeros estructurales" (indicados por una alta centralidad de intermediación) reflejan poder, porque permiten a la persona en la posición puente ejercer control (por ejemplo, decidir si compartir información o no) sobre las personas a las que conecta. entre. ^[9] Desde la perspectiva microscópica de las redes del ego (es decir, considerando sólo las conexiones de primer grado), en las redes sociales en línea una alta centralidad de intermediación coincide con las nominaciones de amigos más cercanos (es decir, fuertes vínculos interpersonales ), porque refleja inversiones de capital social en la relación cuando se unen círculos sociales distantes (por ejemplo, la familia y la universidad) (a menudo como resultado de una introducción por parte del ego). ^[10]

Redes fluviales

La centralidad de intermediación se ha utilizado para analizar la complejidad topológica de las redes fluviales , así como su uso en el comercio marítimo. ^{[11] [12]}

Conceptos relacionados

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

Ver también

• Centralidad

Referencias

1. Hombre libre (1977), pág. 39.
2. "Cálculo de la centralidad de intermediación en Gephi". YouTube .
3. Barrat y col. (2004).
4. Piraveenan, Prokopenko y Hossain (2013).
5. Brandes (2001), pág. 1.
6. Brandes (2001), pág. 9.
7. Mantrach y otros. (2010).
8. Borassi y Natale (2019).
9. Burt (2009).
10. Stolz y Schlereth (2021).
11. Sarker y col. (2019).
12. Eiland, Murray (2020). "Redes de Roma, Bizancio y China". Antiqvvs . 4 (1). Entrevista con Johannes Preiser-Kapeller: 41–45.

Bibliografía

• Barrat, A.; et al. (2004). "La arquitectura de redes ponderadas complejas". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 101 (11): 3747–3752. arXiv : cond-mat/0311416 . Código bibliográfico : 2004PNAS..101.3747B. doi : 10.1073/pnas.0400087101 . ISSN  0027-8424. PMC  374315 . PMID  15007165.
• Borassi, Michele; Natale, Emanuele (2019). "KADABRA es un algoritmo adaptativo para la intermediación mediante aproximación aleatoria". Revista ACM de algorítmica experimental . 24 : 1,2:1–1,2:35. arXiv : 1604.08553 . doi :10.1145/3284359. ISSN  1084-6654. S2CID  67871875.
• Brandes, Ulrik (2001). "Un algoritmo más rápido para la centralidad de intermediación" (PDF) . Revista de Sociología Matemática . 25 (2): 163-177. CiteSeerX  10.1.1.11.2024 . doi :10.1080/0022250x.2001.9990249. hdl :10983/23603. S2CID  13971996. Archivado (PDF) desde el original el 29 de marzo de 2021 . Consultado el 29 de marzo de 2021 .
• Burt, Ronald (2009). Agujeros estructurales: La estructura social de la competencia. Cambridge: Prensa de la Universidad de Harvard . ISBN 978-0-674-02909-5. OCLC  1041149426 . Consultado el 29 de marzo de 2021 .
• Freeman, Linton (1977). "Un conjunto de medidas de centralidad basadas en la intermediación". Sociometría . 40 (1): 35–41. doi :10.2307/3033543. JSTOR  3033543.
• Goh, K.-I.; Kahng, B.; Kim, D. (2001). "Comportamiento universal de la distribución de carga en redes sin escala". Cartas de revisión física . 87 (27): 278701. arXiv : cond-mat/0106565 . Código Bib : 2001PhRvL..87A8701G. doi : 10.1103/PhysRevLett.87.278701. ISSN  0031-9007. PMID  11800921. S2CID  15746304.
• Mantrach, Amin; et al. (2010). "El núcleo de covarianza de suma sobre rutas: una nueva medida de covarianza entre nodos de un gráfico dirigido". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 32 (6): 1112-1126. doi :10.1109/tpami.2009.78. PMID  20431135. S2CID  4807216.
• Moxley, Robert L.; Moxley, Nancy F. (1974). "Determinación de la centralidad del punto en redes sociales no artificiales". Sociometría . 37 (1): 122-130. doi :10.2307/2786472. JSTOR  2786472.
• Newman, Mark EJ (2010). Redes: una introducción . Oxford: Prensa de la Universidad de Oxford . ISBN 978-0-19-920665-0. OCLC  964511577.
• Piraveenan, Mahendra; Prokopenko, Mijaíl; Hossain, Liaquat (2013). Holme, Petter (ed.). "Centralidad de la percolación: cuantificación del impacto teórico de gráficos de los nodos durante la percolación en redes". MÁS UNO . 8 (1): e53095. Código Bib : 2013PLoSO...853095P. doi : 10.1371/journal.pone.0053095 . ISSN  1932-6203. PMC  3551907 . PMID  23349699.
• Sarker, Shiblu; et al. (2019). "Nodos críticos en redes fluviales". Informes científicos . 9 (1): 11178. Código bibliográfico : 2019NatSR...911178S. doi :10.1038/s41598-019-47292-4. ISSN  2045-2322. PMC  6672004 . PMID  31371735.
• Stolz, Simón; Schlereth, cristiano (2021). "Predecir la fuerza del vínculo con las estructuras de la red del ego". Revista de marketing interactivo . 54 (mayo): 40–52. doi :10.1016/j.intmar.2020.10.001. S2CID  229403802.