Mostrando entradas con la etiqueta teoría económica. Mostrar todas las entradas
Mostrando entradas con la etiqueta teoría económica. Mostrar todas las entradas

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)


miércoles, 11 de octubre de 2017

Saltando sobre los agujeros estructurales: Integración social vía Tinder

Primera evidencia de que la citas en línea está cambiando la naturaleza de la sociedad

Los sitios web de citas han cambiado la forma en que las parejas se encuentran. Ahora está emergiendo evidencia de que este cambio está influyendo en los niveles de matrimonio interracial e incluso en la estabilidad del matrimonio mismo.

por Emerging Technology from the arXiv

No hace mucho tiempo, nadie conoció a un compañero en línea. Luego, en la década de 1990, llegaron los primeros sitios web de citas.

Match.com se puso en marcha en 1995. Una nueva ola de sitios web de citas, como OKCupid, surgió a principios de los años 2000. Y la llegada de 2012 de Tinder cambió aún más. Hoy en día, más de un tercio de los matrimonios comienzan en línea.

Es evidente que estos sitios han tenido un enorme impacto en el comportamiento de las citas. Pero ahora está emergiendo la primera evidencia de que su efecto es mucho más profundo.


La forma en que la gente conoce a sus parejas ha cambiado drásticamente en los últimos años

Durante más de 50 años, los investigadores han estudiado la naturaleza de las redes que unen a las personas entre sí. Estas redes sociales resultan tener una propiedad peculiar.

Un tipo obvio de la red liga cada nodo con sus vecinos más cercanos, en un patrón como tablero de ajedrez o alambre de gallinero. Otro tipo obvio de enlaces de red nodos al azar (random network). Pero las redes sociales reales no son como ninguno de estos. En su lugar, las personas están fuertemente conectadas a un grupo relativamente pequeño de vecinos y ligeramente conectados a personas mucho más distantes.

Estas conexiones sueltas resultan ser extremadamente importantes. "Esos lazos débiles sirven de puentes entre nuestro grupo de amigos cercanos y otros grupos agrupados, permitiéndonos conectarnos con la comunidad global", dicen Josue Ortega de la Universidad de Essex en U.K. y Philipp Hergovich en la Universidad de Viena en Austria.

Tradicionalmente, los lazos sueltos han desempeñado un papel clave en el encuentro con los compañeros. Aunque la mayoría de la gente era poco probable de ir a una cita con uno de sus mejores amigos, era muy probable de citar a personas que estaban vinculados con su grupo de amigos, un amigo de un amigo, por ejemplo. En el lenguaje de la teoría de la red, los socios de citas estaban embebidos en las redes de los demás.

De hecho, esto se ha reflejado durante mucho tiempo en encuestas sobre la forma en que las personas se encuentran con sus parejas: a través de amigos comunes, en bares, en el trabajo, en instituciones educativas, en la iglesia, a través de sus familias, etc.

Las citas en línea ha cambiado eso. Hoy en día, las citas en línea son la segunda forma más común de conocer a las parejas heterosexuales. Para las parejas homosexuales, es de lejos el más popular.

Eso tiene implicaciones significativas. "Las personas que se reúnen en línea tienden a ser completos extraños", dicen Ortega y Hergovich. Y cuando la gente se reúne de esta manera, establece vínculos sociales que antes eran inexistentes.

La pregunta que Ortega y Hergovich investigan es cómo esto cambia la diversidad racial de la sociedad. "Comprender la evolución del matrimonio interracial es un problema importante, ya que el matrimonio mixto es ampliamente considerado como una medida de la distancia social en nuestras sociedades", dicen.

Los investigadores comienzan simulando lo que sucede cuando se introducen enlaces adicionales en una red social. Su red se compone de hombres y mujeres de diferentes razas que se distribuyen al azar. En este modelo, todo el mundo quiere casarse con una persona del sexo opuesto, pero sólo puede casarse con alguien con quien existe una conexión. Esto conduce a una sociedad con un nivel relativamente bajo de matrimonio interracial.

Pero si los investigadores añaden vínculos aleatorios entre personas de diferentes grupos étnicos, el nivel de matrimonio interracial cambia drásticamente. "Nuestro modelo predice una integración racial casi completa sobre la aparición de las citas en línea, aunque el número de parejas que los individuos encuentren de los lazos recién formados sea pequeño", dicen Ortega y Hergovich.

Y hay otro efecto sorprendente. El equipo de medir la fuerza de los matrimonios mediante la medición de la distancia media entre los socios antes y después de la introducción de citas en línea. "Nuestro modelo también predice que los matrimonios creados en una sociedad con citas en línea tienden a ser más fuertes", dicen.

A continuación, los investigadores comparan los resultados de sus modelos con las tasas observadas de matrimonios interraciales en los Estados Unidos. Esto ha ido en aumento por algún tiempo, pero las tasas siguen siendo bajas, sobre todo porque el matrimonio interracial fue prohibido en algunas partes del país hasta 1967.

Pero la tasa de aumento cambió en el momento en que la cita en línea se popularizan. "Es intrigante que poco después de la introducción de los primeros sitios web de citas en 1995, como Match.com, el porcentaje de nuevos matrimonios creados por parejas interraciales aumentó rápidamente", dicen los investigadores.

El aumento se hizo más pronunciado en los años 2000, cuando las citas en línea se hicieron aún más populares. Entonces, en 2014, la proporción de matrimonios interraciales saltó de nuevo. "Es interesante que este aumento se produce poco después de la creación de Tinder, considerada la aplicación de citas en línea más popular", dicen.

Tinder tiene unos 50 millones de usuarios y produce más de 12 millones de encuentros al día.

Por supuesto, estos datos no demuestran que las citas en línea causaron el aumento de los matrimonios interraciales. Pero es consistente con la hipótesis de que lo hace.

Mientras tanto, la investigación sobre la fuerza del matrimonio ha encontrado alguna evidencia de que las parejas casadas que se reúnen en línea tienen menores tasas de ruptura matrimonial que las que se reúnen tradicionalmente. Eso tiene el potencial de beneficiar significativamente a la sociedad. Y es exactamente lo que predice el modelo de Ortega y Hergovich.

Por supuesto, hay otros factores que podrían contribuir al aumento del matrimonio interracial. Una es que la tendencia es el resultado de una reducción en el porcentaje de estadounidenses que son blancos. Si los matrimonios son aleatorios, esto debería aumentar el número de matrimonios interraciales, pero no por la cantidad observada. "El cambio en la composición de la población en los Estados Unidos no puede explicar el enorme aumento en el matrimonio mixto que observamos", dicen Ortega y Hergovich.

Eso deja a las citas en línea como el principal impulsor de este cambio. Y si ese es el caso, el modelo implica que este cambio está en curso.

Esa es una profunda revelación. Estos cambios están programados para continuar y beneficiar a la sociedad como resultado.


Ref: arxiv.org/abs/1709.10478 : The Strength of Absent Ties: Social Integration via Online Dating