Mostrando entradas con la etiqueta juegos cooperativos. Mostrar todas las entradas
Mostrando entradas con la etiqueta juegos cooperativos. Mostrar todas las entradas

domingo, 24 de junio de 2018

Maravilloso trabajo de campo con redes sociales de tribus de cazadores-recolectores

Cazadores-recolectores de Hadza, redes sociales y modelos de cooperación


por Artem Kaznatcheev | Theory, Evolution and Games Groups


En el corazón de la región de los Grandes Lagos de África Oriental se encuentra Tanzania, una república compuesta por 30 mikoa o provincias. Su frontera está marcada por los lagos gigantes Victoria, Tanganyika y Malawi. Pero el lago que más me interesa es uno interno: a 200 km de la frontera con Kenia en el cruce de mikao Arusha, Manyara, Simiyu y Singed está el lago Eyasi. Es un lago temperamental que se puede secar casi por completo, que se puede cruzar a pie, en algunos años y en otros, como en los años de El Niño, inunda sus riberas lo suficiente como para atraer hipopótamos del Serengeti.

Para los Hadza, es su hogar.

El número de Hadza es de alrededor de mil personas, y alrededor de 300 viven como cazadores-recolectores nómadas tradicionales (Marlow, 2002; 2010). Un estilo de vida que se cree que es un modelo útil de sociedades en nuestra propia herencia evolutiva. Un modelo empírico de particular interés para la evolución de la cooperación. Pero un modelo que requiere mucho más esfuerzo para explorar que ejecutar algunas configuraciones de parámetros en su computadora. En el verano de 2010, Coren Apicella exploró este modelo viajando entre los campos de Hadza en toda la región del lago Eyasi para obtener información sobre su red social y su comportamiento cooperativo.

Aquí hay un video resumen donde Coren describe su trabajo:




Los datos que recopiló con sus colegas (Apicella et al., 2012) proporcionan nuestro mejor proxy para la organización social de los primeros humanos. En este post, quiero hablar sobre el Hadza, el conjunto de datos de su red social, y cómo puede informar a otros modelos de cooperación. En otras palabras, quiero freeride en Apicella et al. (2012) y me permito a mí mismo y a otros teóricos explorar modelos computacionales informados por el modelo empírico Hadza sin tener que caminar por el Lago Eyasi por nosotros mismos.






Los Hadza viven en pequeños campamentos temporales de unos 30 individuos, con un promedio de 11.7 \ pm 6.0 adultos por campamento para los 17 campamentos en Apicella et al. (2012). [1] Dentro de los campamentos de cazadores-recolectores, incluido el Hadza, hay un intercambio de alimentos en todo el campamento (Marlowe, 2004; Gurven, 2004), de la responsabilidad del cuidado infantil (Henry, et al., 2005; Crittenden & Marlowe, 2008; Hill & Hurtado, 2009), y de las tareas diarias como la adquisición de alimentos, la construcción y el mantenimiento de espacios habitables, y el transporte de niños y posesiones (Hill, 2002). En un metanálisis multicultural de 32 sociedades de alimentación actuales, incluyendo Hadza - Hill et al. (2011) mostraron que sus campamentos tienen bajos niveles de parentesco cercano (generalmente menos del 10%; en el Hadza específicamente varía en promedio del 4.1% para un macho focal al 5.5% para una hembra focal) y experimentan un flujo constante de individuos entre campamentos. Como destacó Coren en el video anterior, los campos de Hadza son muy dinámicos, se reubican cada 4 a 6 semanas y algunas veces se disuelven o se fusionan con otros campamentos.

Sin embargo, este flujo de individuos entre los campamentos no es aleatorio. Los individuos tienen preferencias para compañeros de campamento y Apicella et al. (2012) midieron estas preferencias pidiendo a cada adulto que nominara a algunas otras personas que preferirían tener como compañeros de campamento para su próximo campamento. [2] En este estudio, los hombres solo nominaron a otros hombres y mujeres como mujeres, lo que resultó en dos grafos disjuntos con un total de 205 individuos (nodos) y 1263 candidaturas futuras (enlaces dirigidos) y alrededor del 46% de los enlaces entre los campamentos. Apicella et al. (2012) presentaron estos grafos en la figura 1c (y las nominaciones dentro de los campamentos en la figura S4). Dado que un paso importante para trabajar con datos es tener esos datos, preferiblemente en un formato amigable para la máquina, me enfoqué en esta figura. Aunque conocí a Coren Apicella una vez, no me sentí cómodo al enviarle un correo electrónico con sus datos en bruto, especialmente porque no tenía un propósito específico en mente, así que Marcel Montrey y yo extrajimos la matriz de adyacencia de la figura 1c mano. [3]


Grafo de la futura preferencia de compañero de campamento de Hadza, basado en datos de Apicella et al. (2012) El grafo de la izquierda es de mujeres y el grafo de la derecha es de hombres. Los nodos se dimensionan en proporción a su grado.

Pero, ¿qué vamos a hacer con estos datos? El primer paso de Apicella et al. (2012) fue comparar con otras redes o modelos de redes que a menudo discutimos. En comparación con una red aleatoria con el mismo número de enlaces y nodos, encontraron:
  • que la distribución de grados tiene colas significativamente más gordas,
  • diferencias en su grado de reciprocidad, con un Hadza siendo 37.6 a 51.4 veces más propenso a nombrar como compañero de campamento deseado a alguien que los haya nombrado como un compañero de campamento deseado,
  • asociatividad más alta de lo esperado entre el grado de ingreso y el de salida: los agentes que nombran más agentes también tienen más probabilidades de ser nombrados más ellos mismos.
  • homofilia en rasgos como edad, altura, peso, grasa corporal, fuerza de agarre y nivel de contribución en un juego de bienes públicos. [4]
Para las comparaciones empíricas, consideraron 142 redes socioeconómicas de estudiantes estadounidenses del Estudio Longitudinal Nacional de Salud del Adolescente (para el diseño, ver: Harris et al., 2009), y dos redes de tamaño similar (N = 181, N = 251) de adultos Aldeanos agricultores de subsistencia en Honduras que fueron compartidos con ellos por Derek K. Stafford (de próxima publicación, también, ver Stafford et al., 2010). Aunque estas redes de comparación usaron diferentes preguntas (más o menos: "¿quiénes son tus amigos?") Para generar sus enlaces dirigidos, los parámetros de la red Hadza cayeron dentro de los rangos observados en estas redes de comparación. Pero eso nos interesa solo si esperamos que estos parámetros sean relevantes y determinantes para el tipo de preguntas que queremos formular. No siempre es claro para mí que este sea el caso.

Para las comparaciones empíricas, consideraron 142 redes socioeconómicas de estudiantes estadounidenses del Estudio Longitudinal Nacional de Salud del Adolescente (para el diseño, ver: Harris et al., 2009), y dos redes de tamaño similar (N = 181, N = 251) de adultos Aldeanos agricultores de subsistencia en Honduras que fueron compartidos con ellos por Derek K. Stafford (de próxima publicación, también, ver Stafford et al., 2010). Aunque estas redes de comparación usaron diferentes preguntas (más o menos: "¿quiénes son tus amigos?") Para generar sus enlaces dirigidos, los parámetros de la red Hadza cayeron dentro de los rangos observados en estas redes de comparación. Pero eso nos interesa solo si esperamos que estos parámetros sean relevantes y determinantes para el tipo de preguntas que queremos formular. No siempre es claro para mí que este sea el caso.

Mi impulso de tener datos de redes sociales sobre cazadores-recolectores proviene de la aparente importancia y omnipresencia del estudio de la estructura espacial en los modelos matemáticos de la teoría de juegos evolutiva. La idea es eliminar al intermediario modelador de redes. En lugar de tratar de descubrir qué tipo de red son las familias como redes reales, y luego ejecutar juegos en esas familias, ¿por qué no ejecutar juegos directamente en redes observadas empíricamente? Lamentablemente, existe una tensión entre el tipo de redes que recolectan los antropólogos y los sociólogos, y el tipo de redes que modelan los teóricos de los juegos evolutivos. El enfoque típico de las redes en EGT es hacer que los enlaces del grafo determinen los pares de agentes que interactúan durante el juego y para la reproducción o la imitación. [5] Dado que generalmente consideramos juegos simétricos, generalmente también queremos grafos simétricos. [6] Entonces, un enfoque obvio es simétrizar la red Hadza diciendo que los agentes interactuarán simétricamente si cualquiera inicia, y que el "futuro compañero" es un sustituto de un amigo y la amistad es un sustituto de la interacción frecuente. Esto facilita la integración de la red Hadza en los modelos existentes, pero descarta nuestro conocimiento de cómo los Hadza realmente interactúan entre sí; que se encuentra principalmente en el nivel de un campamento.

En cambio, podríamos estructurar modelos usando los datos de Coren en términos de campamentos, y tener interacciones invisibles dentro de cada campamento. Desafortunadamente, si se permite que los campamentos crezcan o sobrevivan en proporción al rendimiento total (o promedio) de los campamentos, independientemente de las interacciones que elija para modelar, entonces habremos creado una selección de grupos en nuestros modelos. Si, en cambio, mantenemos fijos los campamentos, con migración única (sin pago) entre los campamentos, entonces estamos en un entorno similar a la teoría de conjuntos evolutivos de Tarnita et al. (2009). Este enfoque también puede promover la cooperación, pero de una manera más sutil que la selección directa en grupos. Luego, podemos usar el grafo de las nominaciones de compañeros de campamento futuros de campo cruzado de la figura suplementaria S4 como un grafo de migración. Imagine una dinámica en la que en cada paso del tiempo, se selecciona un ego al azar [7] y se le da la oportunidad de migrar al campamento, potencialmente el mismo campamento en el que ya están, de uno de los alteros que el ego nominó como preferida compañera de campamento futura. Además, periódicamente podemos disolver y luego reformar las redes de compañeros de campamento de acuerdo con las preferencias que Coren recopiló. Una manera podría ser (1) seleccionar egos al azar, (2) crear un nuevo campamento para ellos si aún no son parte de un campamento, y (3) dejarlos invitar a quienes deseen tener como compañeros de campamento a su campamento . Esto reflejaría que, aunque la migración o las visitas son muy comunes, los campamentos completos se mueven entre 6 y 12 veces al año; el número y tamaño de los campamentos también fluctúa a lo largo de la temporada, con menos campamentos más grandes formados durante la última estación seca y la estación húmeda cuando las bayas son comunes (Marlowe, 2002; 2010). Este enfoque nos permite usar la red social de Coren no como el grafo de interacción (y / o reproducción / imitación), sino como una meta-red que informa cómo actualizamos el grafo de interacción.

Los enfoques de los últimos dos párrafos difieren en la medida en que debe alejarse del conocimiento del dominio sobre los datos empíricos que se recopilaron y cuánto tiene que ajustar las herramientas de modelado existentes. El primero se integró mejor con el trabajo teórico sobre EGT, y el segundo con el trabajo empírico en antropología. Al final, la cantidad que ajuste sus herramientas o cuán lejos se aleja de los datos es una elección similar a encontrar su combinación preferida de herramienta-problema. Puedo verme a mí mismo utilizando la red simétrica como telón de fondo para proyectos existentes como la evolución de delirios útiles (Kaznatcheev, et al., 2014) y extendiendo la teoría de conjuntos evolutiva como base para un modelo más cercano al modelo empírico de Hadza. Te mantendré actualizado sobre ambos, querido lector.


Notas y referencias

  1. Aquí parece haber una variación significativa entre años o estaciones. Los datos utilizados por Hill et al. (2011), por ejemplo, informó 17 campamentos con un total de 406 adultos, por lo que alrededor de 23.9 adultos por campamento. No estoy seguro de qué hacer, si es que hay algo que hacer.
  2. Apicella et al. (2012) también construyó una red de regalos pidiendo a las personas que elijan recipientes para un total de 3 barras de miel. Los palos no se podían guardar, pero podría elegir enviar más de uno de sus palos a la misma persona, lo que da como resultado un gráfico dirigido ponderado. Muchas de las propiedades generales que analizo más adelante para la red campmate también fueron válidas para esta, pero la red en sí misma no se presentó explícitamente en el documento (o los materiales complementarios). Como no pude trabajar con él directamente, no lo discutí más en esta publicación.
  3. La representación abarrotada en la figura 1c y los errores en la transcripción introducen cierta discrepancia entre los números informados en Apicella et al. (2012) y los gráficos que recuperamos. En particular, nuestros gráficos tienen un total de 94 hombres y 97 mujeres, y 340 y 506 bordes en los gráficos masculino y femenino, respectivamente. Se trata de 14 personas y 417 candidaturas menos que las 205 personas y 1263 nominaciones que los autores informan. Por lo tanto, no use nuestro conteo como un conjunto de datos autorizado. Para mis propios fines, le pediré a Coren los datos brutos reales si encuentro una pregunta que creo que el modelado computacional puede responder.
  4. Mientras visitaba los campamentos, Coren contrató al Hadza en un juego de bienes públicos. Aunque los investigadores le han pedido al Hadza que juegue varios juegos económicos antes, generalmente el juego del ultimátum o dictador (por ejemplo, ver Henrich et al., 2001), esta era la primera vez que jugaban en el juego de bienes públicos. Las recompensas fueron en la miel, su comida más preferida (Marlowe y Berbesque, 2009), y se midió en barritas. Cada participante fue dotado con 4 palos de miel, y todos los que donaron para el bien público se multiplicaron por un factor de 3 y, después de que todos los compañeros de campamento adultos tomaran sus decisiones de contribución en privado, se distribuyeron entre todos los adultos en el campamento. Todos los campamentos tenían más de 4 residentes adultos.
  5. Por supuesto, también podemos seguir a Ohtsuki et al. (2007) y usa diferentes gráficos de interacción y reemplazo. Es más fácil justificar la red Hadza como un reemplazo por una red de imitación, diciendo que los bordes son vínculos de amistad; y usar la interacción de inviscid a nivel de campamento como lo analizo en el próximo párrafo. Por supuesto, si se adapta el enfoque completo de meta-red del siguiente párrafo, entonces la red Hadza se usa para actualizar los campamentos, pero la interacción y las redes de imitación pueden ser establecidas por la propia estructura del campamento invisible.
  6. Alternativamente, uno puede abrazar los bordes dirigidos modificando los modelos de la teoría del juego evolutivo y concentrándose en juegos no simétricos como el ultimátum o el dictador. Esto se conectaría con una gran literatura de economía conductual y antropología (como Henrich et al., 2001) y algunos estudios de modelado (como Nowak et al., 2000).
  7. Seleccionar egos al azar independientemente de su aptitud o estrategia es una simplificación potencialmente irracional. Cuando un Hadza deja su campamento, por alguna razón es como una disputa o escasez de recursos que puede estar estrechamente vinculada a la recompensa o estrategia de uno en las interacciones cooperativas. Afortunadamente, este tipo de estrategias de migración condicional ya están siendo exploradas por investigadores como C. Athena Aktipis (2004).

Aktipis, C.A. (2004). Know when to walk away: contingent movement and the evolution of cooperation. Journal of Theoretical Biology, 231(2): 249-260.

Apicella, C.L., Marlowe, F.W., Fowler, J.H., & Christakis, N.A. (2012). Social networks and cooperation in hunter-gatherers. Nature, 481 (7382), 497-501 PMID: 22281599

Crittenden, A. N., & Marlowe, F. W. (2008). Allomaternal care among the Hadza of Tanzania. Human Nature, 19(3): 249-262.

Gurven, M. (2004). To give and to give not: the behavioral ecology of human food transfers. Behavioral and Brain Sciences, 27(04), 543-559.

Harris, K.M., C.T. Halpern, E. Whitsel, J. Hussey, J. Tabor, P. Entzel, & Udry, J.R. (2009) The National Longitudinal Study of Adolescent to Adult Health: Research Design. [online].

Kaznatcheev, A., Montrey, M., & Shultz, T.R. (2014). Evolving useful delusions: Subjectively rational selfishness leads to objectively irrational cooperation. Proceedings of the 36th annual conference of the cognitive science society. arXiv: 1405.0041v1.

Marlowe, F. (2002). Why the Hadza are still hunter-gatherers. Ethnicity, huntergatherers, and the ‘Other’, ed. S. Kent, 247-81.

Marlowe, F.W. (2004). What explains Hadza food sharing? Research in Economic Anthropology, 23: 69-88.

Marlowe, F. W., & Berbesque, J. C. (2009). Tubers as fallback foods and their impact on Hadza hunter‐gatherers. American Journal of Physical Anthropology, 140(4): 751-758.

Marlowe, F.W. (2010). The Hadza: hunter-gatherers of Tanzania (Vol. 3). Univ. of California Press.

Nowak, M. A., Page, K. M., & Sigmund, K. (2000). Fairness versus reason in the ultimatum game. Science, 289(5485): 1773-1775.

Ohtsuki, H., Pacheco, J. M., & Nowak, M. A. (2007). Evolutionary graph theory: breaking the symmetry between interaction and replacement. Journal of Theoretical Biology, 246(4): 681-694.

Hill, K. (2002). Altruistic cooperation during foraging by the Ache, and the evolved human predisposition to cooperate. Human Nature, 13(1): 105-128.

Hill, K., & Hurtado, A. M. (2009). Cooperative breeding in South American hunter–gatherers. Proceedings of the Royal Society of London B: Biological Sciences, rspb20091061.

 

domingo, 15 de abril de 2018

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 centralidadGrafos no ponderadasGrafos ponderadosArtículo (PDF)
Semivalue-based Degree CentralityO(|V|3)O(|V|3)Szczepański et al. (2015)
Shapley value-based Degree CentralityO(|V|+|E|)O(|V|+|E|)Michalak et al. (2013)
Coalitional Semivalue-based Degree CentralityO(|V|4)O(|V|4)Szczepański et al. (2014)
Owen value-based Degree CentralityO(|V|+|E|)O(|V|+|E|)Szczepański et al. (2014)
Semivalue-based Betweenness CentralityO(|V|2|E|)O(|V|3|E| + |V|3log|V|)mimeo, University of Oxford
Shapley value-based Betweenness CentralityO(|V||E|)O(|V|2|E| + |V|2log|V|)Szczepański et al. (2012)
Semivalue-based Closeness CentralityO(|V|5)O(|V|5)Szczepański et al. (2015)
Shapley value-based Closeness CentralityO(|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)