Teoría económica: Centralidad en juegos cooperativos en redes

Centralidad en teoría de juegos de un vistazo (una nueva clase de herramientas de análisis de red).

Game Theoretic Centrality


La idea clave detrás de las medidas de centralidad de la teoría del juego es tratar a los nodos como jugadores en un juego cooperativo, donde el valor de cada coalición de nodos está determinado por ciertas propiedades de teoría de gráficos. La ventaja clave de este enfoque es que los nodos se clasifican no solo según sus roles individuales en la red, sino también de acuerdo con la forma en que contribuyen al rol desempeñado por todos los posibles subconjuntos (o grupos) de nodos. Esto es importante en diversas aplicaciones en las que el rendimiento de un grupo no puede describirse simplemente como la suma de las actuaciones individuales de los nodos implicados.



Considere, por ejemplo, una aplicación de epidemiología, cuyo objetivo es contener la propagación de una enfermedad. Si nos preguntamos si la vacunación de un nodo individual es suficiente para detener la propagación de la enfermedad, probablemente la respuesta sea No. Una forma mucho más probable de contener la enfermedad es vacunar simultáneamente a un grupo (posiblemente relativamente pequeño) de nodos. En base a esto, para cuantificar la importancia de un nodo, debemos considerar la ganancia potencial de vacunarlo como parte de un grupo más grande, en lugar de solo considerar la ganancia potencial de vacunarlo solo.

Tal análisis de grupos de nodos en la red corresponde directamente a la teoría de juegos de coalición, donde el rendimiento de los jugadores se estudia en `` coaliciones '' (es decir, subconjuntos de jugadores). Es importante destacar que, al imponer la estructura combinatoria de un juego de coalición a través de una red, es posible analizar el rendimiento de los nodos usando una gran cantidad de conceptos de soluciones teóricas de juegos desarrolladas durante décadas para analizar el rendimiento de los jugadores. Un concepto de solución teórico-juego bien conocido es el valor de Shapley, que recibió amplia atención en la literatura debido a sus propiedades deseables. Otro es el índice de poder de Banzhaf.

Una ventaja particular de esta perspectiva teórica de juego del análisis de redes es que expone la posibilidad de extender una amplia variedad de medidas de centralidad. Esto se debe a que un juego cooperativo generalmente no establece suposiciones o restricciones sobre cómo se evalúan los grupos. Esta evaluación se puede adaptar para ajustarse mejor a la medida de centralidad en cuestión. Por ejemplo, un grupo de nodos se puede evaluar en función del grado promedio en el mismo, o en función de su diámetro, o su cercanía a otros nodos, etc.

Una posible desventaja de las centralidades de red teóricas de juegos es que se basan en conceptos de solución que son difíciles de calcular. Por ejemplo, dado un juego de coalición definido sobre una red de nodos O(|V|), un cálculo directo del valor de Shapley requiere considerar todas las posibles coaliciones O(2|V|) (es decir, grupos) de nodos. Esto es claramente prohibitivo para redes con cientos, o incluso decenas, de nodos. De hecho, se ha demostrado que en algunos casos el número exponencial de cálculos no se puede evitar, es decir, es imposible calcular ciertas centralidades de red teóricas de juegos en polinomios temporales en el tamaño de la red. Este resultado negativo se cumple, por ejemplo, para las centralidades de redes teóricas de juegos en el espíritu de los juegos restringidos por gráficos de Myerson (1977).

Afortunadamente, también se han encontrado varios resultados computacionales positivos. En particular, Michalak et al. (2013) analizaron varias extensiones basadas en el valor de Shapley de la centralidad de grados y mostraron que es posible aprovechar el hecho de que los valores de los grupos de nodos dependen de la topología de la red. Como resultado, mostraron que algunas medidas de centralidad de la teoría del juego pueden ser computables en tiempo polinomial. De manera similar, los resultados del tiempo polinomial son conocidos por la centralidad de interrelación basada en el valor de Shapley (Szczepański et al., 2012).

Principales resultados computacionales (qué tan rápido podemos calcular las centralidades teóricas de juegos).

En general, los conceptos de soluciones teóricas de juegos como el valor de Shapley o el índice de poder de Banzhaf son desafiantes desde el punto de vista informático; el número de cálculos requeridos es exponencial en la cantidad de jugadores. Afortunadamente, este no es necesariamente el caso cuando la evaluación de coaliciones (es decir, grupos de nodos) depende de la topología de la red. En particular, para la centralidad teórica del juego, se han encontrado varios resultados computacionales positivos. Los enumeramos a continuación:

Nombre de centralidad	Grafos no ponderadas	Grafos ponderados	Artículo (PDF)
Semivalue-based Degree Centrality	O(|V|3)	O(|V|3)	Szczepański et al. (2015)
Shapley value-based Degree Centrality	O(|V|+|E|)	O(|V|+|E|)	Michalak et al. (2013)
Coalitional Semivalue-based Degree Centrality	O(|V|4)	O(|V|4)	Szczepański et al. (2014)
Owen value-based Degree Centrality	O(|V|+|E|)	O(|V|+|E|)	Szczepański et al. (2014)
Semivalue-based Betweenness Centrality	O(|V|2|E|)	O(|V|3|E| + |V|3log|V|)	mimeo, University of Oxford
Shapley value-based Betweenness Centrality	O(|V||E|)	O(|V|2|E| + |V|2log|V|)	Szczepański et al. (2012)
Semivalue-based Closeness Centrality	O(|V|5)	O(|V|5)	Szczepański et al. (2015)
Shapley value-based Closeness Centrality	O(|V||E|)	O(|V||E| + |V|2log|V|)	Michalak et al. (2013)

Aplicaciones de la centralidad teórica de juegos para el análisis de redes sociales.

Capital social.

El valor de Owen (Owen 1977) es una extensión del valor de Shapley a situaciones en las que los jugadores han acordado a priori dividirse en uniones. En este contexto, los miembros de un sindicato interactúan con otros sindicatos en su conjunto (es decir, no es posible que solo algunos de los miembros colaboren o unan fuerzas con otro sindicato). Los jugadores en cualquier unión colaboran estrictamente en el juego. De forma similar al valor de Shapley, el valor de Owen cuantifica el rol de un jugador individual, pero ahora teniendo en cuenta el papel de la unión a priori a la que pertenece este jugador. Por ejemplo, un jugador puede ser débil por sí mismo, pero si él / ella pertenece a una unión importante, entonces su rol se fortalecerá de acuerdo con el valor de Owen.

Recientemente, Szczepanski et al. (2014) propuso la extensión teórica de juego de la centralidad de grado basada en el valor de Owen. Curiosamente, esta centralidad tiene una interpretación no trivial como medida del capital social. En particular, el capital social de un individuo aumenta (disminuye) si pertenece a una comunidad que es rica (pobre) en términos de capital social. Por ejemplo, si un abogado no está particularmente bien conectado, su capital social todavía se incrementa por el hecho de que pertenece a la comunidad de abogados bien conectada. Por lo tanto, esta es la primera medida de capital social que evalúa a los actores individuales tanto en el contexto de sus relaciones con el mundo externo como en el contexto del rol externo de la comunidad a la que pertenecen.



Como una aplicación de muestra de esta medida, Szczepanski et al. (2014) estudió una red que consta de artículos conectados por citas de relaciones. Aquí, todas las publicaciones de una revista en particular, o la serie de actas de una conferencia en particular, pueden verse como una comunidad científica naturalmente definida. El objetivo de Szczepanski et al. fue estudiar cómo la importancia de una determinada comunidad científica influye en el papel de un solo artículo en la red de citas. La red de la vida real utilizada para simulaciones es una red de citas que consta de 2.084.055 publicaciones y 2.244.018 relaciones de citas. Todas las publicaciones están clasificadas en 22,954 comunidades únicas que representan revistas, actas de congresos o títulos de libros individuales. En lo que sigue, de los 2.084.055 nodos, la Figura 1 se centra en los primeros 11 según la centralidad de grado. Más específicamente, la Figura 1 (a) ilustra el poder relativo de las comunidades a las que pertenecen estos nodos (cuanto más grande es el círculo, más poderosa es la comunidad). Como se puede ver, los nodos clasificados 5, 6 y 8 pertenecen a comunidades significativamente menos poderosas que los nodos 1, 2, 3, 4, 7, 9, 10 y 11. La Figura 1 (b) muestra cómo cambia el ranking de esos 11 nodos de acuerdo con las centralidades basadas en valores de Shapley y Owen. Mientras que para la mayoría de los nodos las perturbaciones no son tan intensas, observamos una degradación significativa de la posición de los nodos 5, 6 y 8 en el ranking Owen, que demuestra cómo es capaz de reconocer el hecho de que estos tres nodos pertenecen a comunidades más débiles .

En cuanto a los problemas computacionales, Szczepanski et al. (2014) mostraron que la centralidad de grados basada en el valor de Owen puede calcularse en O(|V|+|E|) tiempo, lo que hace que este concepto sea práctico incluso para redes grandes de la vida real.

Aplicaciones de la centralidad teórica de juegos a la biología.

En biología e investigación médica, se utilizan diversas tecnologías experimentales de alto rendimiento para recopilar una gran cantidad de datos sobre funciones biológicas interactivas. En muchos casos, las interacciones entre estas características se pueden representar como una red, cuyo análisis implica la definición de medidas apropiadas de relevancia para los nodos y para los enlaces. Para este propósito, varias medidas de centralidad basadas en la teoría de juegos de coalición se han aplicado con éxito a diferentes tipos de redes biológicas.

Redes cerebrales.

Las observaciones clínicas de las funciones cerebrales se representan actualmente en la actualidad como una red que consta de regiones y estructuras cerebrales (por ejemplo, estructuras neuronales) y sus interconexiones. Por ejemplo, las redes cerebrales están representadas por gráficos dirigidos cuyos nodos son estructuras neuronales (núcleos o regiones corticales) y cuyo conjunto de arcos dirigidos representa el conjunto de conexiones dirigidas (proyecciones) entre estas estructuras. En Kötter et al. (2007), los juegos de coalición y el valor de Shapley se han utilizado para medir la importancia de las estructuras cerebrales individuales para la conectividad de la gráfica derivada de las propiedades globales de las redes formadas por las neuronas y sus interconexiones. El valor de cada coalición no vacía de estructuras neuronales en el juego se define como la cantidad de componentes conectados en la red cerebral y el valor de Shapley de este juego se utiliza para comprender las consecuencias funcionales de una lesión en las diferentes áreas del cerebro. Las aplicaciones del valor de Shapley para el análisis de redes cerebrales reales que representan áreas corticales visuales y áreas corticales prefrontales del macaco, respectivamente, se presentan y discuten en Kötter et al. (2007).

Redes de genes.

Las redes génicas (p. Ej., Que representan las interacciones proteína-proteína, coexpresión de genes, etc.) se utilizan cada vez más para explorar la funcionalidad a nivel de sistema de proteínas y genes. Recientemente, se ha introducido un nuevo método basado en juegos de coalición en Moretti et al. (2010) para evaluar la centralidad en las redes de genes, teniendo en cuenta las interacciones entre los genes. La idea básica del enfoque en Moretti et al. (2010) se basa en el análisis de dos juegos de coalición: un juego de asociación, definido como un juego de coalición sobre un conjunto de genes donde el valor de cada coalición S mide la "interacción" entre los genes en S y un conjunto dado de un una familia a priori de genes clave, y un juego restringido por gráficos, donde la interacción genética se restringe a las conexiones proporcionadas por una red genética. La diferencia de los valores de Shapley calculados en los dos juegos de coalición antes mencionados se usa en Moretti et al. (2010) como una medida de centralidad génica en una red de genes real derivada de datos de expresión génica.




La figura anterior muestra la red de interacción entre los genes (nodos) de las células sanguíneas de los niños de la región de Teplice (TP) en la República Checa, un distrito minero caracterizado por altos niveles de contaminantes transportados por el aire que incluyen carcinógenos. Las interacciones entre pares de genes están representadas por aristas. Los bordes más gruesos muestran los caminos más cortos entre los genes más asociados. Fuente: Moretti et al. (2010).

Redes metabólicas

Las redes metabólicas representan sistemas biológicos complejos compuestos de reacciones bioquímicas a través de las cuales se transforman los metabolitos. El análisis de balance de flujo (FBA) de redes metabólicas se ha utilizado en Sajitz-Hermstein y Zoran (2012) para introducir juegos de FBA, que son juegos de coalición donde el conjunto de jugadores es el conjunto de reacciones que forman la red metabólica y una coalición S corresponde a la subred inducida por las reacciones incluidas en S. El valor dado a la coalición S por la función característica de un juego FBA es entonces el valor óptimo de la función objetivo determinada por FBA en la subred correspondiente en S. El valor de Shapley solo considerando el conjunto restringido de subredes capaces de realizar la función bioquímica investigada se ha utilizado en Sajitz-Hermstein y Zoran (2012) como una medida de centralidad funcional para cuantificar las contribuciones de las reacciones individuales a las capacidades de conversión bioquímica. Las aplicaciones a redes metabólicas reales, como un modelo de glicólisis y vía de la pentosa fosfato, se presentan en [Sajitz-Hermstein y Zoran (2012), Sajitz-Hermstein y Zoran (2013)].

Redes quimiosensoriales.

El Multi-perturbation Shapley Value Analysis (MSA) (Keinan et al., 2004) es un método para deducir la localización de la función causal a partir de múltiples datos de perturbaciones, donde el valor de Shapley se utiliza para cuantificar la importancia de cada uno de los elementos de un complejo sistema en la realización de diferentes funciones. Siguiendo este enfoque, el valor de cada coalición de elementos del sistema es una medida del rendimiento del sistema biológico para una determinada función (por ejemplo, la capacidad del sistema para sobrevivir a la radiación UV). Los autores en Kaufman et al. (2005) utilizaron el método MSA para analizar la localización de funciones en el sistema nervioso, basándose en los experimentos de ablación con láser de las neuronas quimiosensoriales en C. elegans.

Aplicaciones de la centralidad teórica de juegos a la tecnología de las comunicaciones de información.

Red de computadoras.

Con el fin de reducir su huella de carbono, las TIC emergentes están integradas con protocolos de consumo de energía y técnicas de ahorro de energía. Un enfoque de enrutamiento consciente de la energía se estudia en [Bianzino et al. (2011), Bianzino et al. (2012)] con el objetivo de resumir la contribución de dispositivos que usan índices de poder (y en particular el valor de Shapley) de determinados juegos de coalición definidos sobre el conjunto de los elementos de una red troncal. Tales juegos de coalición incorporan la información sobre la estructura de la red (por ejemplo, la conectividad de subredes), la cantidad de tráfico que enrutan los dispositivos y la robustez de la red (es decir, posibles escenarios de falla). La clasificación proporcionada por el valor de Shapley de tales juegos se ha utilizado para impulsar la selección de dispositivos menos críticos que deberían desconectarse primero a fin de reducir el consumo de energía y tener en cuenta el rendimiento global esperado de la red. La clasificación proporcionada por el valor de Shapley se ha comparado en escenarios de red realistas con clasificaciones dadas por métodos basados ​​en nociones de centralidad clásica. Esta comparación muestra que la clasificación de valores de Shapley puede proporcionar un alto ahorro de energía con un impacto menor en los niveles de QoS (calidad de servicio) esperados en la red.



En la figura anterior: Izquierda: vista del grafo de criticidad de los enlaces según el índice de Shapley para el escenario de la red de referencia durante el tráfico de la hora punta: cuanto más grueso es un enlace, mayor es su importancia. Derecha: Ahorro de energía alcanzable para el escenario de referencia de la red, para diferentes clasificaciones de enlaces. Fuente: Bianzino et al. (2012)