miércoles, 30 de noviembre de 2016

Tecnología para atacar las fuentes de desinformación en medios sociales

Desinformación en las redes sociales: ¿Puede la tecnología salvarnos?
The conversation


Compartiendo hashtags de la elección: Los puntos son cuentas de Twitter; Las líneas muestran retweeting; Los puntos más grandes son retweeted más. Los puntos rojos son bots probables; Los azules son probablemente seres humanos. Clayton Davis, CC BY-ND

Autor Filippo Menczer
Profesor de Informática e Informática; Director del Centro de Redes Complejas y Sistemas de Investigación, Universidad de Indiana, Bloomington


Si obtienes tus noticias de las redes sociales, como la mayoría de los estadounidenses, estás expuesto a una dosis diaria de engaños, rumores, teorías conspirativas y noticias engañosas. Cuando todo está mezclado con información confiable de fuentes honestas, la verdad puede ser muy difícil de discernir.

De hecho, el análisis de mi equipo de investigación de datos y seguimiento de rumores de la Universidad de Columbia Emergent sugiere que esta desinformación es tan probable que vaya viral como información confiable.

Muchos están preguntando si este ataque de desinformación digital afectó el resultado de las elecciones estadounidenses de 2016. La verdad es que no sabemos, aunque hay razones para creer que es totalmente posible, sobre la base de análisis anteriores y los recuentos de otros países. Cada pieza de desinformación contribuye a la formación de nuestras opiniones. En general, el daño puede ser muy real: si la gente puede ser engañada para poner en peligro la vida de nuestros hijos, como lo hacen cuando se optan por inmunizaciones, ¿por qué no nuestra democracia?

Como investigador de la propagación de la desinformación a través de los medios de comunicación social, sé que limitar la capacidad de los falsificadores de noticias para vender anuncios, como anunció recientemente Google y Facebook, es un paso en la dirección correcta. Pero no limitará los abusos impulsados ​​por motivos políticos.


Explotación de medios sociales

Hace unos 10 años, mis colegas y yo realizamos un experimento en el que aprendimos que el 72 por ciento de los estudiantes universitarios confiaban en vínculos que parecían originados por amigos, incluso hasta el punto de ingresar información de inicio de sesión personal en sitios de phishing. Esta vulnerabilidad generalizada sugiere otra forma de manipulación maliciosa: La gente también podría creer que la desinformación que reciben al hacer clic en un enlace de un contacto social.

Para explorar esa idea, he creado una página web falsa con noticias aleatorias generadas por computadoras, como "Celebrity X en la cama con Celebrity Y!". Los visitantes del sitio que buscaban un nombre activarían el script para fabricar automáticamente una Historia de la persona. Incluí en el sitio un descargo de responsabilidad, diciendo que el sitio contenía texto sin sentido y "hechos" inventados. También colocé anuncios en la página. Al final del mes, recibí un cheque por correo con los ingresos de los anuncios. Esa era mi prueba: las noticias falsas podían ganar dinero contaminando Internet con falsedades.

Lamentablemente, yo no era el único con esta idea. Diez años más tarde, tenemos una industria de falsas noticias y desinformación digital. Los sitios de Clickbait fabrican bromas para ganar dinero con anuncios, mientras que los llamados sitios hiperpartidistas publican y difunden rumores y teorías de conspiración para influir en la opinión pública.

Esta industria se ve reforzada por lo fácil que es crear bots sociales, cuentas falsas controladas por software que parecen personas reales y por lo tanto pueden tener una influencia real. Investigaciones en mi laboratorio descubrieron muchos ejemplos de falsas campañas populares, también llamadas de astroturfing político.

En respuesta, desarrollamos la herramienta BotOrNot para detectar bots sociales. No es perfecto, pero lo suficientemente preciso como para descubrir campañas de persuasión en los movimientos Brexit y antivax. Usando BotOrNot, nuestros colegas encontraron que una gran parte de la charla en línea sobre las elecciones de 2016 fue generada por bots.



En esta visualización de la propagación del hashtag # SB277 sobre una ley de vacunación de California, los puntos son cuentas de Twitter publicando usando ese hashtag, y las líneas entre ellos muestran retweeting de mensajes hashtagged. Los puntos más grandes son cuentas que se retweeted más. Los puntos rojos son bots probables; Los azules son probablemente seres humanos. Onur Varol, CC BY-ND


Creación de burbujas de información

Los seres humanos somos vulnerables a la manipulación por la desinformación digital gracias a un complejo conjunto de sesgos sociales, cognitivos, económicos y algorítmicos. Algunos de estos han evolucionado por buenas razones: Confiar en las señales de nuestros círculos sociales y rechazar la información que contradice nuestra experiencia nos sirvió bien cuando nuestra especie se adaptó a evadir a los depredadores. Pero en las actuales redes en línea, una conexión de red social con un teórico de la conspiración en el otro lado del planeta no ayuda a informar mis opiniones.

Copiar a nuestros amigos y no seguir a los que tienen diferentes opiniones nos dan cámaras de eco tan polarizadas que los investigadores pueden decir con alta precisión si usted es liberal o conservador por sólo mirar a sus amigos. La estructura de la red es tan densa que cualquier desinformación se extiende casi instantáneamente dentro de un grupo, y así segregada que no llega al otro.

Dentro de nuestra burbuja, estamos expuestos selectivamente a información alineada con nuestras creencias. Ese es un escenario ideal para maximizar el compromiso, pero uno perjudicial para desarrollar un escepticismo saludable. El sesgo de confirmación nos lleva a compartir un titular sin ni siquiera leer el artículo.

Nuestro laboratorio obtuvo una lección personal en esto cuando nuestro propio proyecto de investigación se convirtió en el tema de una campaña de desinformación viciosa en el período previo a las elecciones de mitad de mandato de los Estados Unidos en 2014. Cuando investigamos lo que estaba sucediendo, encontramos falsas noticias sobre nuestra investigación que eran compartidas predominantemente por los usuarios de Twitter dentro de una cámara de eco partidista, una comunidad grande y homogénea de usuarios políticamente activos. Estas personas se apresuraron a retweet e impermeables a debunking información.




En este gráfico de cámaras de eco en la Twittersfera, puntos morados representan a las personas difundir afirmaciones falsas sobre el proyecto de investigación Truthy; Las dos cuentas que trataban de desacreditar la información falsa están en naranja en la extrema izquierda. Giovanni Luca Ciampaglia, CC BY-ND

Inevitabilidad viral 

Nuestra investigación muestra que dada la estructura de nuestras redes sociales y nuestra limitada atención, es inevitable que algunos memes se vuelvan virales, independientemente de su calidad. Incluso si los individuos tienden a compartir información de mayor calidad, la red en su conjunto no es efectiva para discriminar entre información confiable y fabricada. Esto ayuda a explicar todos los engaños virales que observamos en la naturaleza.

La economía de la atención se ocupa del resto: si prestamos atención a un tema determinado, se producirá más información sobre ese tema. Es más barato fabricar información y transmitirla como un hecho que para informar la verdad real. Y la fabricación se puede adaptar a cada grupo: los conservadores leen que el Papa endosó a Trump, los liberales leen que apoyó a Clinton. Él tampoco hizo nada.


Atención a los algoritmos

Dado que no podemos prestar atención a todos los posts de nuestros feeds, los algoritmos determinan lo que vemos y lo que no. Los algoritmos utilizados por las plataformas de medios sociales hoy en día están diseñados para priorizar puestos atractivos - los que es probable que haga clic en, reaccionar y compartir. Pero un análisis reciente encontró que las páginas engañosas intencionalmente consiguieron al menos tanto compartir y reaccionar en línea como noticias reales.

Este sesgo algorítmico hacia el compromiso sobre la verdad refuerza nuestros sesgos sociales y cognitivos. Como resultado, cuando seguimos enlaces compartidos en las redes sociales, tendemos a visitar un conjunto de fuentes más pequeñas y homogéneas que cuando realizamos una búsqueda y visitamos los resultados principales.

La investigación existente demuestra que estar en una cámara de eco puede hacer que las personas sean más crédulas acerca de aceptar rumores no verificados. Pero necesitamos saber mucho más acerca de cómo diferentes personas responden a un solo engaño: algunos lo comparten de inmediato, otros lo comprueban primero.

Estamos simulando una red social para estudiar esta competencia entre compartir y verificación de hechos. Esperamos ayudar a desentrañar evidencias contradictorias sobre cuándo la comprobación de hechos ayuda a evitar que los engaños se propaguen y cuando no. Nuestros resultados preliminares sugieren que cuanto más segregada sea la comunidad de creyentes engañadores, más larga la broma sobrevivirá. Una vez más, no se trata sólo de la estafa sino también de la red.

Muchas personas están tratando de averiguar qué hacer con todo esto. Según el último anuncio de Mark Zuckerberg, los equipos de Facebook están probando opciones potenciales. Y un grupo de estudiantes universitarios ha propuesto una manera de etiquetar simplemente los enlaces compartidos como "verificados" o no.

Algunas soluciones permanecen fuera de alcance, al menos por el momento. Por ejemplo, todavía no podemos enseñar a los sistemas de inteligencia artificial cómo discernir entre la verdad y la falsedad. Pero podemos decir algoritmos de clasificación para dar mayor prioridad a fuentes más confiables.


Estudiar la difusión de noticias falsas

Podemos hacer que nuestra lucha contra las noticias falsas sea más eficiente si comprendemos mejor cómo se propaga la mala información. Si, por ejemplo, los bots son responsables de muchas de las falsedades, podemos centrar la atención en detectarlas. Si, alternativamente, el problema es con las cámaras de eco, tal vez podríamos diseñar sistemas de recomendación que no excluyan puntos de vista diferentes.

Para ello, nuestro laboratorio está construyendo una plataforma llamada Hoaxy para rastrear y visualizar la propagación de reclamos sin verificar y la verificación de hechos correspondiente en las redes sociales. Eso nos dará datos reales, con los que podemos informar a nuestras redes sociales simuladas. Entonces podemos probar posibles enfoques para combatir falsas noticias.

Hoaxy también puede mostrar a la gente lo fácil que es que sus opiniones sean manipuladas por la información en línea - e incluso la probabilidad de que algunos de nosotros compartamos falsedades en línea. Hoaxy se unirá a una serie de herramientas en nuestro Observatorio de Medios Sociales, que permite a cualquiera ver cómo se propagan los memes en Twitter. Vincular herramientas como éstas a los verificadores de hechos humanos y las plataformas de medios sociales podría facilitar la minimización de la duplicación de esfuerzos y apoyarse mutuamente.

Es imprescindible invertir recursos en el estudio de este fenómeno. Necesitamos todas las manos en la cubierta: los científicos de la computación, los científicos sociales, los economistas, los periodistas y los socios de la industria deben trabajar juntos para mantenerse firmes contra la extensión de la desinformación.

lunes, 28 de noviembre de 2016

Infografía: La vida de un influenciador en Twitter



La Vida de un Influenciador de Twitter [Infografía]

Chiara Di Rago - Social Media Today

Si bien Twitter puede no ser la plataforma de medios sociales más utilizada, sigue siendo uno de los canales más efectivos y relevantes para iniciar la conversación en línea - e incluso puede provocar un movimiento social.

En Webfluential, a menudo doy consejos a los influyentes sobre su valor social y cómo pueden mejorarlo. Mientras trabajaba con estos influenciadores me han hecho una serie de preguntas sobre Twitter, siendo la más común:

  • ¿Cómo puedo aumentar mi audiencia?
  • ¿Cuánto debo cobrar como influenciador de Twitter?
  • ¿Cuántos seguidores necesito para ser considerado influyente?

Teniendo en cuenta el concepto de contenido nutritivo, pensé que sería útil responder a algunas de estas preguntas en forma de un infográfico - compruébalo a continuación.

sábado, 26 de noviembre de 2016

ARS 101: Redes de co-ocurrencia

Redes de co-ocurrencia 
Wikipedia

Las redes de co-ocurrencia se usan generalmente para proporcionar una visualización gráfica de relaciones potenciales entre personas, organizaciones, conceptos u otras entidades representadas dentro del material escrito. La generación y visualización de redes de co-ocurrencia se ha vuelto práctico con el advenimiento del texto almacenado electrónicamente que es susceptible a la minería de texto.

A modo de definición, las redes de co-ocurrencia son la interconexión colectiva de términos basados ​​en su presencia emparejada dentro de una unidad de texto especificada. Las redes se generan conectando pares de términos usando un conjunto de criterios que definen la co-ocurrencia. Por ejemplo, se puede decir que los términos A y B "co-ocurren" si ambos aparecen en un artículo particular. Otro artículo puede contener términos B y C. Vincular A a B y B a C crea una red de co-ocurrencia de estos tres términos. Las reglas para definir la co-ocurrencia dentro de un corpus de texto se pueden establecer de acuerdo con los criterios deseados. Por ejemplo, un criterio más estricto para la co-ocurrencia puede requerir un par de términos para aparecer en la misma oración.



Una red de co-occurrencia creada con KH Coder

Métodos y desarrollo

Las redes de co-ocurrencia pueden ser creadas para cualquier lista de términos (cualquier diccionario) en relación con cualquier colección de textos (cualquier corpus de texto). Los pares co-occurrentes de términos se pueden llamar "vecinos" y éstos agrupan a menudo en "barrios" basados ​​en sus interconexiones. Los términos individuales pueden tener varios vecinos. Los barrios pueden conectarse entre sí a través de al menos un término individual o pueden permanecer desconectados.

Los términos individuales son, en el contexto de la minería de textos, representados simbólicamente como cadenas de texto. En el mundo real, la entidad identificada por un término normalmente tiene varias representaciones simbólicas. Por tanto, es útil considerar los términos como representados por un símbolo primario y hasta varios símbolos sinónimos alternativos. La ocurrencia de un término individual se establece mediante la búsqueda de cada representación simbólica conocida del término. El proceso puede ser aumentado a través de algoritmos de procesamiento de lenguaje natural (NLP) que interrogan segmentos de texto para posibles alternativas como orden de palabras, espaciado y separación de palabras. La PNL también se puede usar para identificar la estructura de oraciones y categorizar las cadenas de texto de acuerdo con la gramática (por ejemplo, categorizar una cadena de texto como un sustantivo basado en una cadena de texto anterior conocida como un artículo).

La representación gráfica de las redes de co-ocurrencia permite visualizarlas e inferencias sobre las relaciones entre entidades en el dominio representado por el diccionario de términos aplicados al corpus de texto. Una visualización significativa requiere normalmente simplificaciones de la red. Por ejemplo, las redes pueden ser dibujadas de manera que el número de vecinos que se conectan a cada término sea limitado. Los criterios para limitar los vecinos podrían basarse en el número absoluto de co-ocurrencias o criterios más sutiles como la "probabilidad" de co-ocurrencia o la presencia de un término descriptivo intermedio.

Los aspectos cuantitativos de la estructura subyacente de una red de coinoconducción también pueden ser informativos, como el número total de conexiones entre entidades, el agrupamiento de entidades que representan subdominios, la detección de sinónimos [1], etc.

Aplicaciones y uso

Algunas aplicaciones de trabajo del enfoque de co-ocurrencia están disponibles para el público a través de Internet. PubGene es un ejemplo de una aplicación que se ocupa de los intereses de la comunidad biomédica mediante la presentación de redes basadas en la co-ocurrencia de la genética relacionados con los términos que aparecen en los registros de MEDLINE [2] [3] El sitio web NameBase es un ejemplo de cómo las relaciones humanas se pueden inferir mediante el examen de redes construidas a partir de la co-ocurrencia de nombres personales en los periódicos y otros textos (como en Ozgur et al [4]).

Las redes de información también se utilizan para facilitar los esfuerzos para organizar y centrar la información disponible públicamente para fines de aplicación de la ley y de inteligencia (llamada "inteligencia de código abierto" o OSINT). Las técnicas conexas incluyen las redes de co-citación, así como el análisis del hipervínculo y la estructura del contenido en Internet (como en el análisis de sitios web relacionados con el terrorismo [5]).


Véase también

  • Takada H, Saito K, Yamada T, Kimura M: “Analysis of Growing Co-occurrence Networks” SIG-KBS (Journal Code:X0831A) 2006, VOL.73rd;NO.;PAGE.117-122 Language;Japanese
  • Liu, Chua T-S; “Building semantic perceptron net for topic spotting.” Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, 2001; 378 - 385

Referencias

  1. Cohen AM, Hersh WR, Dubay C, Spackman, K: “Using co-occurrence network structure to extract synonymous gene and protein names from MEDLINE abstracts” BMC Bioinformatics 2005, 6:103
  2. Jenssen TK, Laegreid A, Komorowski J, Hovig E: "A literature network of human genes for high-throughput analysis of gene expression. " Nature Genetics, 2001 May; 28(1):21-8. PMID 11326270
  3. Grivell L: “Mining the bibliome: searching for a needle in a haystack? New computing tools are needed to effectively scan the growing amount of scientific literature for useful information.” EMBO reports 2001 Mar;3(3):200-3: doi:10.1093/embo-reports/kvf059 PMID 11882534
  4. Ozgur A, Cetin B, Bingol H: “Co-occurrence Network of Reuters News” (15 Dec 2007) http://arxiv.org/abs/0712.2491
  5. Zhou Y, Reid E, Qin J, Chen H, Lai G: "US Domestic Extremist Groups on the Web: Link and Content Analysis" http://doi.ieeecomputersociety.org/10.1109/MIS.2005.96

jueves, 24 de noviembre de 2016

Puentes: Árbitros inter escalamiento

Árbitros de escalas: nuevas herramientas teóricas para analizar la capacidad de adaptación


por Henrik Ernstson


La estructura de la red social es importante para la capacidad de adaptación. Una posición clave son los 'intermediarios de escalas' que vinculan a los actores que interactúan con los procesos de los ecosistemas a diferentes escalas ecológicas.


Junto con colegas de la Universidad de Estocolmo, acabamos de publicar un artículo en Ecology and Society llamado:
Henrik ErnstsonStephan Barthel,Erik Andersson y Sara T. Borgström,Ecology and Society 2010: 15 (4), 28.
El artículo sintetiza estudios empíricos de la gestión ecológica urbana en Estocolmo. Sin embargo, también contribuye a las discusiones teóricas sobre la gobernabilidad adaptativa de los sistemas socio-ecológicos (por ejemplo, el número especial en Global Environmental Change, Folke y otros 2005, Duit y Galaz, 2008). Como tal, el artículo es de interés para estudios en sistemas marinos, forestales y agrícolas.
Aquí les presento algunas ideas teóricas claves. (ver también el blog en Stockholm Resilience Centre.).
Marco para evaluar la capacidad de adaptación - vinculando los procesos ecológicos y la estructura de la red social
El artículo construye un marco teórico que vincula procesos ecológicos a estructuras de redes sociales para evaluar la capacidad de adaptación de la gobernanza de los ecosistemas. En efecto, el artículo empuja las teorizaciones actuales en al menos tres aspectos: 1) complejidad espacial; 2) el papel de la estructura de la red social; y 3) cómo manejar las interacciones entre escalas.
1) Complejidad espacial
Primero, construye un marco para explicar más explícitamente la complejidad espacial (y por lo tanto la complejidad del "recurso" en cuestión). Esto se hace principalmente a través de un enfoque empírico sobre los procesos ecológicos de dispersión de semillas y polinización, que son procesos importantes para la re-generación y resiliencia de los ecosistemas locales en el paisaje urbano fragmentado de Estocolmo.
2)Estructura de red social como variable intermedia
En segundo lugar, el documento "mira" más allá de los actores individuales y sus vínculos directos con otros (a menudo el caso en la literatura sobre, por ejemplo, las "organizaciones puente"). En cambio, los actores que interactúan con los procesos ecológicos se ven incorporados en los patrones de comunicación y relaciones sociales. Esto significa que el documento reconoce la "estructura de la red social" y cómo esta variable intermedia (no individual, no institución) media la agencia de actores individuales, y el desempeño de toda la red para responder al cambio.
Para captar la dinámica social, tomamos la idea de la sociología de que, al igual que los parches ecológicos forman parte de patrones de mayor escala, los actores sociales forman parte de estructuras de redes sociales emergentes que limitan y modelan la dinámica social (Wasserman y Faust, 1994). [...] los patrones de redes sociales son consecuencia de interacciones localizadas entre pares de actores, y ningún actor puede controlar completamente la estructura emergente. [Esto] permite la agencia humana, pero una agencia restringida y mediada a través de la propia estructura de red (Emirbayer y Goodwin, 1994).
3) Interacciones a escala cruzada y árbritros de escalas
En tercer lugar, el documento impulsa la comprensión de lo que significaría para un conjunto de actores identificables para manejar interacciones a escala cruzada en los sistemas socio-ecológicos. Esto se logra a través del desarrollo de un modelo de red de cómo ciertos grupos de actores se involucran en procesos ecológicos a diferentes escalas a través de su práctica social y teorizan una posición clave en la red llamada "arbitraje de cruce" (basándose en la noción de árbitros de Burt)
Por lo tanto, al explicar la estructura de las redes sociales entre los grupos de actores, y cómo se vinculan a las escalas ecológicas, nuestro modelo resultante consiste en grupos de actores que interactúan entre sí y con procesos ecosistémicos en diferentes escalas espaciales y en sitios espacialmente separados [ Figura en la parte superior].
Un último aspecto central de nuestro modelo es la posición en red del intermediario de escalas [que se define] como una posición de red social que vincula a grupos de actores sociales desconectados que, a través de sus prácticas sociales, interactúan con procesos ecosistémicos a diferentes niveles ecológicos ) Y en diferentes sitios físicos.
En relación con la discusión sobre cómo los sistemas de gobernanza pueden hacer frente a cambios lentos por un lado y cambios rápidos por otro, nuestra respuesta indica que debemos buscar esto en la estructura de redes sociales que une a diversos actores a través de escalas. En este sentido, el corredor de escalas se convierte en "un cruce de posibilidades" y podría facilitar la "conmutación" entre los procesos sociales de aprendizaje localizados (en tiempos de lento cambio) y la acción colectiva centralizada (en tiempos de cambio rápido):
Los intermediarios inter-escalas pueden ser vistos como agentes para fomentar la aparición de una estructura de redes sociales determinada y para cambiar entre un modo de acción colectiva centralizada y un modo descentralizado de aprendizaje social entre un conjunto diverso de grupos de actores autónomos locales.
Evaluando los sistemas de gobernanza
Como tal, el agente de cruce de escala se convierte en una lente analítica para utilizar al evaluar sistemas de gobierno empíricos. Las próximas investigaciones deberían, por lo tanto, apuntar a medir hasta qué punto puede encontrar intermediarios de escala en un sistema particular. Otra herramienta de evaluación de este tipo reside en nuestra conceptualización de una escala meso en la gobernanza en forma de "redes verdes a escala de la ciudad" (véase la figura siguiente).
En conclusión, y aparte de sus hallazgos empíricos no abordados en este blog, el documento puede ser visto como aportando nuevas ideas teóricas sobre cómo discutir y analizar la complejidad socio-ecológica y la capacidad de adaptación. Para más información vea el trabajo en sí mismo, el posteo del blog en la Stockholm Resilience Centre, o mi propio blog In Rhizomia.




Fig. 4. La figura demuestra cómo se podría identificar las redes verdes de polinización y dispersión de semillas en una zona particular de Estocolmo (sugerida aquí por el uso de mapas digitales y análisis de redes ecológicas) (véase Andersson y Bodin 2008). Observe cómo ciertas áreas verdes locales son compartidas entre las dos redes verdes de la escala de la ciudad, que dan lugar a la superposición de la red (áreas púrpuras con líneas verticales en negrita en la red verde 2 de la escala de la ciudad). Además, se sugiere que los gerentes de mediana escala puedan asumir la responsabilidad de las redes verdes de escala urbana. En su conjunto, la figura demuestra cómo los servicios ecosistémicos en particular pueden ser vistos como incrustados tanto en el paisaje físico como en las redes sociales de grupos de actores locales (manejo de áreas verdes locales), agentes de escala y agentes municipales a regionales.

Resilience Science

martes, 22 de noviembre de 2016

ARS 101: Grafo dividido

Grafo dividido
Wikipedia


Un grafo dividido, dividido en una agrupación y un conjunto independiente.

En la teoría de grafos, una rama de las matemáticas, un grafo dividido es un grafo en el que los vértices se pueden dividir en una agrupación y un conjunto independiente. Los grafos divididos fueron estudiados por primera vez por Földes y Hammer (1977a, 1977b), e introducidos independientemente por Tyshkevich y Chernyak (1979). [1]

Un grafo dividido puede tener más de una partición en una agrupación y un conjunto independiente; Por ejemplo, la trayectoria a-b-c es un grafo dividido, cuyos vértices se pueden dividir en tres formas diferentes:

  1. La camarilla {a, b} y el conjunto independiente {c}
  2. La camarilla {b, c} y el conjunto independiente {a}
  3. La camarilla {b} y el conjunto independiente {a, c}

Los grafos divididos se pueden caracterizar en términos de sus subgrafos inducidos prohibidos: un grafo se divide si y sólo si ningún subgrafo inducido es un ciclo en cuatro o cinco vértices, o un par de enlaces disjuntos (el complemento de un ciclo de 4). 2]

Relación con otras familias de grafos

De la definición, los grafos divididos se clausuran claramente bajo complementación. [3] Otra caracterización de los grafos divididos implica la complementación: son grafos cordales cuyos complementos son también acordales. [4] Del mismo modo que los grafos acordales son los grafos de intersección de los subárboles de los árboles, los grafos divididos son los grafos de intersección de los distintos subestados de los grafos en estrella. Casi todos los grafos acordales son grafos divididos; Es decir, en el límite cuando n va al infinito, la fracción de los grafos acordales de n-vértices que se dividen se aproxima a uno. [6]

Debido a que los grafos acordales son perfectos, también lo son los grafos divididos. Los grafos de doble división, una familia de grafos derivados de grafos divididos, duplicando cada vértice (por lo que la camarilla viene a inducir un antimatching y el conjunto independiente viene a inducir una correspondencia), figura prominentemente como una de las cinco clases básicas de grafos perfectos de los cuales Todos los demás pueden formarse en la prueba de Chudnovsky et al. (2006) del teorema Strong Perfect Graph.

Si un grafo es a la vez un grafo dividido y un grafo de intervalo, entonces su complemento es tanto un grafo dividido como un grafo de comparabilidad, y viceversa. Los grafos divididos de comparabilidad, y por lo tanto también los grafos de intervalo divididos, se pueden caracterizar en términos de un conjunto de tres subgrafos inducidos prohibidos. [7] Los cógrafos divididos son exactamente los gráficos de umbral, y los grafos de permutación dividida son exactamente los grafos de intervalos que tienen complementos de grafos de intervalos. [8] Los grafos divididos tienen el número 2 cocromático.

Problemas Algorítmicos

Sea G un grafo dividido, dividida en un clique C y un conjunto independiente I. Entonces cada camarilla máxima en un grafo dividido es C o la vecindad de un vértice en I. Por lo tanto, es fácil identificar la máxima camarilla , Y complementariamente el conjunto independiente máximo en un grafo dividido. En cualquier grafo dividido, una de las siguientes tres posibilidades debe ser verdadera: [9]

  1. Existe un vértice x en I tal que C ∪ {x} es completo. En este caso, C ∪ {x} es una máxima e I es un conjunto máximo independiente.
  2. Existe un vértice x en C tal que I ∪ {x} es independiente. En este caso, I ∪ {x} es un conjunto máximo independiente y C es un máximo clique.
  3. C es una camarilla máxima e I es un conjunto independiente máximo. En este caso, G tiene una única partición (C, I) en una camarilla y un conjunto independiente, C es la máxima camarilla, e I es el conjunto máximo independiente.

Algunos otros problemas de optimización que son NP-completos en las familias de grafos más generales, incluyendo el grafos coloreados, son similares en los grafos de división. Encontrar un ciclo hamiltoniano sigue siendo NP-completo, incluso para los grafos divididos que son los grafos de cuerdas fuertes. [10] También es bien sabido que el problema del Conjunto Dominador Mínimo sigue siendo NP-completo para los grafos divididos. [11]

Secuencias de grados

Una característica notable de los grafos divididos es que pueden ser reconocidos únicamente a partir de sus secuencias de grados. Sea la sucesión de grados de un grafo G d1 ≥ d2 ≥ ... ≥ dn, y sea m el mayor valor de i tal que di ≥ i - 1. Entonces G es un grafo dividido si y solo si

\sum_{i=1}^m d_i = m(m-1) + \sum_{i=m+1}^n d_i.

Si este es el caso, entonces los m vértices con los grados más grandes forman una camarilla máxima en G, y los vértices restantes constituyen un conjunto independiente.

Cuenta de grafos divididos

Royle (2000) demostró que las grafos divididos de n-vértices con n están en correspondencia uno a uno con ciertas familias de Sperner. Usando este hecho, determinó una fórmula para el número de grafos (no isomórficos) divididos en n vértices. Para valores pequeños de n, a partir de n = 1, estos números son

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (secuencia A048194 en el OEIS).

Este resultado de enumeración gráfica también fue demostrado antes por Tyshkevich y Chernyak (1990).


Notas


  1. Földes & Hammer (1977a) tenían una definición más general, en la que los grafos que llamaron grafos divididos también incluían grafos bipartitos (es decir, grafos que se dividen en dos conjuntos independientes) y los complementos de los grafos bipartitos (es decir, los grafos que se pueden dividir en dos grupos) . Földes & Hammer (1977b) utilizan la definición aquí dada, que se ha seguido en la literatura subsiguiente; Por ejemplo, es Brandstädt, Le & Spinrad (1999), Definition 3.2.3, p.41.
  2. Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151.
  3. Golumbic (1980), Theorem 6.1, p. 150.
  4. Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151; Brandstädt, Le & Spinrad (1999), Theorem 3.2.3, p. 41.
  5. McMorris & Shier (1983); Voss (1985); Brandstädt, Le & Spinrad (1999), Theorem 4.4.2, p. 52.
  6. Bender, Richmond & Wormald (1985).
  7. Földes & Hammer (1977b); Golumbic (1980), Theorem 9.7, page 212.
  8. Brandstädt, Le & Spinrad (1999), Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.
  9. Hammer & Simeone (1981); Golumbic (1980), Theorem 6.2, p. 150.
  10. Müller (1996)
  11. Bertossi (1984)
  12. Hammer & Simeone (1981); Tyshkevich (1980); Tyshkevich, Melnikow & Kotov (1981); Golumbic (1980), Theorem 6.7 and Corollary 6.8, p. 154; Brandstädt, Le & Spinrad (1999), Theorem 13.3.2, p. 203. Merris (2003) further investigates the degree sequences of split graphs.



Referencias

viernes, 18 de noviembre de 2016

La cooperación da poder a los débiles

La competencia entre redes pone de manifiesto el poder de los débiles

Jaime Iranzo, Javier M. Buldú y Jacobo Aguirre
Nature Communications 7, Número del artículo: 13273 (2016)
Doi: 10.1038/ncomms13273

Resumen
Las conexiones no previsibles entre sistemas de red reales han llamado recientemente a un examen de fenómenos de percolación, difusión o sincronización en redes multicapa. Aquí utilizamos la teoría de redes y la teoría de juegos para explorar las interacciones en redes de redes y modelarlas como un juego para ganar importancia. Proponemos un punto de vista donde las redes eligen las estrategias de conexión, en contraste con los enfoques clásicos donde los nodos son los jugadores activos. Específicamente, investigamos cómo la creación de caminos entre redes conduce a diferentes equilibrios de Nash que determinan sus propiedades estructurales y dinámicas. En una amplia variedad de casos, la selección de conexiones adecuadas conduce a una solución cooperativa que permite a las redes débiles superar al oponente más fuerte. De manera contraria, cada red débil puede inducir una transición global a dicha configuración cooperativa independientemente de las acciones de la red más fuerte. Este poder de los débiles revela un dominio crítico de los marginados en el destino de las redes de redes.


Introducción

Los sistemas sociales, biológicos, físicos y tecnológicos están compuestos por una diversidad de agentes interactivos, lo que hace que la ciencia de la red, una comprensión de la física estadística de la teoría gráfica, sea una auténtica herramienta para investigar su estructura y dinámica1,2,3. En el marco de las redes sociales4, se ha demostrado que la topología de las interacciones entre individuos es crucial, por ejemplo, en la desaparición del umbral crítico en las epidemias5,6 o en la propagación eficiente y rápida de la innovación7. De manera similar, la topología de una red misma puede ser influenciada por los procesos dinámicos que ocurren en ella, dando lugar a mecanismos adaptativos que rigen la evolución de la estructura de las redes sociales8.

El surgimiento de la cooperación, defección o altruismo puede ser investigado vinculando la teoría de los juegos a la ciencia de la red9,10,11,12. De este modo, la heterogeneidad intrínseca de las redes sociales, la mayoría de las cuales muestran distribuciones de poder-ley en el número de conexiones1, se ha relacionado en muchos casos con el surgimiento de la cooperación, contrariamente a lo que se observa en poblaciones homogéneas13. Además, también se ha demostrado que los individuos altamente conectados son más propensos a colaborar que los pocos conectados14. Bajo este marco, la comprensión de los juegos evolutivos se benefició en gran medida de las herramientas metodológicas de la ciencia en red11. Aunque la atención se centró inicialmente en la interacción entre las estrategias de los nodos y la estructura de la red (única) subyacente15, más recientemente, las reglas coevolutivas también se han relacionado con la aparición de estructuras de interdependencia16 y de múltiples capas17. Sin embargo, ¿qué pasa si nos preocupan los intereses de una red en su conjunto en lugar de sus nodos? ¿Tiene sentido considerar las redes que compiten o colaboran con otras redes? La fructífera literatura reciente sobre redes de redes, o en un contexto más general sobre redes multicapa, hace que estas dos preguntas sean oportunas y de gran relevancia18,19. Una diversidad de procesos dinámicos como la percolación20, la difusión21 o la sincronización22 han sido reinterpretados recientemente suponiendo que las redes reales interactúan inevitablemente con otras redes, un contacto que puede ser beneficioso o perjudicial para cada una de las redes que pertenecen al conjunto23.

Aquí investigamos cómo m> 2 redes compiten o cooperan para lograr un aumento relativo de importancia medido como centralidad de vectores propios, que maximiza su resultado en una variedad de procesos dinámicos. En nuestra competencia, las redes pueden variar la forma en que interactúan con otras redes, evolucionando en el tiempo hasta alcanzar una situación estable en la que todas las redes se niegan a modificar su estrategia, ya que cualquier cambio conduciría a un peor resultado. Es importante destacar que una estrategia de conexión óptima a priori para una red dada puede no ser alcanzable debido a las acciones de las redes competidoras, lo que convierte el análisis del resultado final de las redes en un estudio de los equilibrios de Nash24 en una red de redes. Con este objetivo definimos una metodología para analizar la competencia entre redes de cualquier tamaño o topología, demostrando que pueden coexistir varios equilibrios de Nash, con algunos de ellos beneficiando a las redes más fuertes y otros beneficiando a los más débiles.

En particular, se informa de la existencia de un amplio régimen de los parámetros del sistema en el que cada red débil puede inducir al resto a cooperar, a escapar de un equilibrio de Nash perjudicial, asumiendo la situación final de toda la red de redes. Paradójicamente, la red fuerte no puede revertir este fenómeno. Esta asimetría contra-intuitiva que promueve la cooperación entre redes débiles es independiente de la estructura de la red o de las reglas de la competencia y podría aplicarse a un extenso número de sistemas reales.


Resultados

Definición de las reglas de la competencia

Como regla general, consideramos que los nodos pertenecientes a una red aceptarán una estrategia común, que puede justificarse en términos de un beneficio común o la existencia de una imposición dentro de una organización jerárquica (véase la Nota Suplementaria 1 para más detalles). El siguiente ejemplo, basado en redes reales, ilustra cómo diferentes estrategias pueden mejorar el resultado de una red. La interacción entre los miembros de las comunidades rurales del sur de la India se investigó recientemente mediante una serie de encuestas en el marco de un programa de microfinanzas25,26. A partir de esos conjuntos de datos (disponibles en la versión en línea de la referencia 25), construimos las redes de préstamos dentro de tres de esos pueblos (véase la figura 1a), creando un vínculo entre los individuos i y j si estaban dispuestos a prestar o pedir prestado Unos de otros una cierta cantidad de dinero. Las redes de préstamos locales construidas como se explicó anteriormente proporcionan mucha información sobre la capacidad de recuperación financiera de una región. Si las autoridades locales de una aldea promovían las conexiones con otras regiones -por ejemplo, mediante la financiación de eventos sociales- se mejoraría su red de préstamos y la aldea estaría más preparada para hacer frente a riesgos naturales o financieros inesperados (véanse las refs 27, 28 , 29, 30, 31 y Nota complementaria 1). Sin embargo, ¿qué aldea es la mejor para conectarse si existe más de una opción? Además, lo que es más importante, ¿qué aldea se beneficiaría más de la creación de nuevos canales financieros entre ellos?


Figura 1: Competencia por la centralidad de las redes de préstamos.

Las aldeas A (verde), B (azul) y C (rojo) se nombran de acuerdo con el valor propio más grande de sus redes de préstamos, de manera que λA> λB> ΛC (véase la Nota Suplementaria 1 para detalles sobre la construcción de las redes). La creación de conexiones entre aldeas conduciría a una red de redes T, cuya centralidad se distribuye entre las aldeas. En b, c, mostramos la centralidad retenida en cada aldea (red) dependiendo de las diferentes estrategias de conexión. El radio de cada círculo es proporcional a la centralidad acumulada por cada red. Las resistencias de las redes son λA = 4,27, λB = 4,05 y λC = 3,38. Cuando se permite una conexión entre aldeas (l = 1), coexisten dos Equilibrios de Nash: en b, las redes B y C se conectan a A (CA = 0,55, CB = 0,35 y CC = 0,10), pero su mejor estrategia se muestra en c , Es decir, crear enlaces entre ellos, obligando a la red A a unirse a ellos (CA = 0,32, CB = 0,49 y CC = 0,19). En resumen, el resultado final del concurso depende en gran medida de la solución alcanzada.


Para abordar estas preguntas en un marco general consideramos m redes de nodos Ni respectivamente, donde i = A, B, C, ... Las matrices de adyacencia Gi asociadas a cada red i contienen la información completa sobre las conexiones entre sus nodos Es, la topología específica de las redes). El mayor autovalor λi de Gi es un indicador de la intensidad de la red, como se explica en la referencia. 32; Por lo tanto, podemos ordenarlos de manera que λA> λB≥ ... ≥λm. Hacemos uso de la centralidad del vector propio para determinar la importancia adquirida por cada nodo, que se obtiene directamente del vector propio u1 asociado al valor propio más alto λ1 de la matriz de adyacencia (ver referencia 3, Métodos y Nota complementaria 2).

En nuestro juego, cada competidor (es decir, la red) hace uso de hasta l enlaces no dirigidos para conectarse con cualquiera de las otras redes. Los nodos conector son aquellos con la centralidad más grande (ver Métodos). La negativa a conectarse es una estrategia aceptada. Por lo tanto, hay  estrategias por competidor y (Sm,l)m  posibles combinaciones de acciones. El objetivo de cada competidor es maximizar su propia centralidad del autovector, calculada como la importancia total (o centralidad) Ci acumulada por todos sus nodos



Donde j son los nodos que pertenecen a la red i y uT es el autovector asociado con el valor propio más grande λT de la matriz de adyacencia de la red de redes T, que contiene todos los nodos NT=∑i Ni.. Es de notar que nos enfrentamos a un juego de suma cero (Σi Ci = 1) y el sistema conectado T consta de m redes interconectadas a través de un máximo de m × l enlaces conector. Además, dichos enlaces conectores influirán en Ci de cada red, pero no en su fuerza λi, que se mide cuando la red i está aislada del resto y es independiente de la competencia.

Como suponemos que las redes son capaces de modificar sus enlaces conector con el objetivo de adquirir la mayor centralidad posible Ci dentro de la red de redes T, la configuración final del sistema viene dada por un equilibrio de Nash. Un equilibrio de Nash es la solución de un juego no cooperativo en el que participan dos o más jugadores, en el que se supone que cada competidor conoce las estrategias de equilibrio de los otros jugadores y ningún competidor tiene nada que ganar cambiando únicamente su propia estrategia24,33. Desde esta perspectiva general, independientemente de las reglas particulares del concurso, el proceso de competencia termina cuando se alcanza un equilibrio de Nash, siendo Ci el pago final de cada red competidora.

La Figura 1b, c muestra la competencia por la centralidad en nuestra "historia de tres aldeas". Calculamos el autovalor más grande asociado con las redes de préstamos dentro de cada aldea y obtenemos el ranking en la fuerza: λA> λB> λC. La terminología utilizada para indicar cómo una red (es decir, una aldea) i1 decide conectarse a una red i2 es la siguiente: i1 (0) significa red i1 que se niega a conectar, i1i2 significa i1 conectando a la red i2 y i1i2  significa i1 conectando a la red i2 y i2 conectando a la red i1. La flecha → indica qué red decide crear el enlace del conector, pero todos los enlaces no están dirigidos (es decir, bidireccionales).

Al permitir que las aldeas se conecten a través de un enlace (l = 1), obtenemos dos posibles equilibrios de Nash. En uno de ellos, las aldeas débiles establecen conexiones con la aldea fuerte, {A (0), B → A, C → A}, que beneficia claramente a esta última (Fig. 1b). Sin embargo, el equilibrio alternativo {A → B, B↔C} permite a las aldeas débiles superar a su competidor más fuerte conectándose entre sí. En este escenario, la red fuerte debe conectarse a B para retener parte de la centralidad de todo el sistema (figura 1c).

Es importante destacar que la selección de estrategias de conexión adecuadas va más allá de la competencia por la centralidad. En las redes profesionales, por ejemplo, el crecimiento del conocimiento de un individuo puede ser modelado para ser proporcional al conocimiento de sus conocidos34, lo que conduce a una distribución final del conocimiento que es dada por el primer autovector uT de la matriz de adyacencia. Se ha traducido a un caso en el que grupos independientes de profesionales o investigadores pueden crear conexiones entre ellos, esto indicaría que la estrategia mostrada en la Fig. 1c mejoraría no sólo la importancia de un grupo de profesionales, sino la cantidad relativa de conocimientos adquiridos por el grupo más débil en comparación con el más fuerte (véase la nota complementaria 1 para varios ejemplos del mundo real que tratan de redes sociales, tecnológicas y biológicas). Además, una amplia variedad de sistemas se describen mediante matrices de adyacencia ponderada-matrices de transición que incluyen las especificidades del proceso dinámico subyacente-cuyo vector uT está relacionado con el estado de equilibrio del sistema32. La dinámica evolutiva de la replicación-mutación35, los procesos de difusión21 o la propagación de la enfermedad36 son sólo algunos ejemplos donde la metodología aquí presentada puede aplicarse sin pérdida de generalidad (ver Métodos).


Competencia y cooperación para superar las más fuertes

La figura 2 muestra una descripción numérica completa de la competencia entre m = 3 redes genéricas libres de escala A, B y C de los valores propios más grandes λA>λB>λC. Por razones de claridad, sólo se permite un enlace de conector por red (l = 1) y, por lo tanto, cada competidor tiene m diferentes estrategias de conexión (es decir, conectarse a cualquiera de las otras redes m-1 o negarse a conectarse). En el caso de tres redes, son posibles 27 combinaciones de estrategias para cada realización - elección de redes - entre las que sólo se toman como soluciones al concurso las que verifican las condiciones para ser equilibrios de Nash. La figura 1b, c muestra que más de una solución final puede coexistir, lo que plantea dos preguntas relevantes: (i) ¿es la coexistencia de soluciones un fenómeno general? Y si este es el caso, (ii) ¿el resultado final de cada jugador varía sustancialmente dependiendo de la solución alcanzada?

Figura 2: Competencia por la centralidad entre 3 redes.

Cada competidor utiliza tanto como l = 1 enlace para conectarse con el resto de las redes. Modificamos el tamaño y / o el grado medio de la red A (es decir, el competidor más fuerte) para incrementar su resistencia de λA = λB a λA»λB↔C, donde B↔C es la red resultante de conectar B y C A través de un enlace doble. El eje x se ha reescalado para permitir comparaciones entre diferentes realizaciones. Para cada elección de B y C, el sistema se resuelve para 20 series de A y los resultados son un promedio de más de 500 conjuntos de A, B y C. (a) Número de equilibrios de Nash coexistentes por realización. El radio de cada círculo es proporcional a la fracción de realizaciones (no se encontraron casos con más de dos soluciones coexistentes). (B) Presencia relativa de diferentes configuraciones en el conjunto de soluciones, promediada en todas las realizaciones: (i) Equilibrio X0 = {A → B, B↔C} (amarillo), (ii) equilibrio X∞ = {A (0) , B → A, C → A} (azul) y (iii) otros equilibrios (gris). En algunas realizaciones excepcionales, A → B es sustituido por A → C en X0. C) Centralidad de las redes A (círculo), B (diamante) y C (triángulo) para una elección particular de B y C (λB = 5,25 y λC = 5,2). Los resultados se muestran para las soluciones X0 y X∞ (código de color como en b). (D) Variabilidad de centralidad relativa ΔC entre diferentes equilibrios de Nash. Los puntos de datos (barras de error) corresponden a promedios (s.d.) sobre todas las realizaciones cuyo λA se encuentra en el correspondiente intervalo del eje X. Símbolos de red como en c.

La Figura 2a, b pregunta de dirección (i) y muestran los perfiles de solución a medida que aumenta la resistencia de la red A (es decir, λA). La figura 2a muestra un escenario que consideramos general: la coexistencia de equilibrios de Nash, entre los cuales dos de ellos, llamados X0 y X∞, son especialmente relevantes (véase la figura 2b):





Por otro lado, la Fig. 2c muestra la centralidad de los dos equilibrios de Nash existentes a medida que aumenta la fuerza de A para una elección particular de B y C. Para una amplia gama de valores de A, las centralidades alcanzadas por cada jugador dependen fuertemente de la solución específica del concurso , Que responde a la pregunta (ii) y subraya la importancia de elegir una estrategia de conexión adecuada.

Para comprobar la relevancia de este resultado, en la Fig. 2d se muestra la variabilidad de centralidad relativa (ΔC), una medida de cuánto mejora el resultado de un jugador al llegar a su solución óptima:



Donde los máximos y mínimos se calculan entre todos los equilibrios de Nash coexistentes. El ΔCi de cada jugador i toma valores que van desde cero (si todas las soluciones conducen a la misma centralidad) hasta el infinito (si la solución del peor caso conduce a la centralidad cero para ese jugador). Las tres redes muestran valores del orden de ΔC ~ 0,8, lo que significa que la centralidad final de cada red competidora puede variar hasta casi dos veces dependiendo de la solución alcanzada.

A la vista de todos, podemos identificar diferentes regímenes de competencia dependiendo de la fuerza relativa entre la fuerte red A y el resto de competidores. Para fuerzas muy grandes de A, es decir, cuando λA> λB↔C, el único equilibrio de Nash existente corresponde a X∞: las redes pequeñas evitan la cooperación mutua y tienden a conectarse a la más grande, que domina la contienda. Una transición crítica ocurre en λA = λB↔C por debajo de la cual X∞ y X0 coexisten de manera biestable. Curiosamente, dentro de esta región, la cooperación entre las redes débiles siempre conduce a su mejor resultado. Finalmente, una transición más suave ocurre alrededor de λA~λB↔C, siendo B↔C la red resultante de conectar B y C a través de un solo enlace: cuando la fuerza de A se aproxima a la de B, la cooperación mutua entre B y C se hace dominante y equilibrio X∞ ya no es posible. Al mismo tiempo, pueden aparecer otros equilibrios de Nash (región gris de la figura 2b). Véanse las notas complementarias 2 y 3 para un tratamiento analítico completo de este fenómeno.

Las redes débiles pueden inducir la migración entre equilibrios

Como se explicó, en un equilibrio de Nash cada competidor que puede cambiar la estrategia disminuiría su centralidad. Sin embargo, como hay equilibrios de Nash coexistentes, puede valer la pena asumir una pérdida temporal de centralidad si la situación final conduce a una mejora en el resultado. De esta manera, se estudia la migración potencial entre los equilibrios X0 y X∞ en el régimen en el que coexisten (λA <λB↔C). En la Fig. 3a muestran que la migración de X∞ a X0 puede ser provocada por la red más débil C individualmente, mientras que la Fig. 3b muestra que la red fuerte no puede activar el sistema para migrar de X0 a X∞. Como consecuencia, cuando múltiples redes compiten por la centralidad, una red débil por sí misma puede escapar de un equilibrio perjudicial y empujar a todo el sistema hacia un sistema mucho más beneficioso con el costo de un transitorio de un paso durante el cual se disminuye su centralidad. Por el contrario, esta estrategia de migración no es accesible a la red fuerte, dando lugar a una asimetría natural en el contexto de las redes de redes que beneficia el resultado final de las redes débiles y les proporciona una flexibilidad no permitida a los competidores más fuertes .


Figura 3: Migración entre equilibrios de Nash.

En este ejemplo, las redes se generan con el modelo de Barabási-Albert (λA = 4.07, λB = 3.95 y λC = 3.63, dando λA <λB↔C = 4.21). Para seguir cómo las estrategias de conexión influyen en la distribución de la centralidad, el radio de cada círculo es proporcional a la centralidad acumulada por cada red. El equilibrio X∞ conduce a CA = 0,65, CB = 0,21 y CC = 0,14, mientras que X0 conduce a CA = 0,28, CB = 0,45 y CC = 0,27. (A) La red más débil C provoca la migración de X∞ a X0, para mejorar drásticamente su centralidad (el mismo razonamiento podría aplicarse a B). Paso 1: la red C se desconecta de la red fuerte A y se conecta a la red débil B. Paso 2: A no cambia sus conexiones porque cualquier variación sería perjudicial, pero B mejora su centralidad separándose de A y conectándose a C. Paso 3 : A se hace aislado y CA = 0 (porque λA <λB↔C). Está obligado a conectarse a B y el sistema alcanza el equilibrio de Nash X0. (B) La red fuerte A no puede provocar la migración del equilibrio X0 a X∞ y está obligada a permanecer en un estado final desventajoso. Si A se niega a conectarse a cualquier red débil (Paso b.1) o se conecta a C en su lugar (Paso b.2), B y C perderían centralidad si rompieran su conexión mutua y consecuentemente se negaran a cambiar sus conexiones. A se ve obligado a conectarse de nuevo a B retornando a la estrategia X0.


Consecuencias generales en la red de redes

El trabajo numérico extensivo produce que la fuerza λT de la red de redes T siguiente al equilibrio X0 es siempre mayor que la de la solución X∞ (es decir, λT (X0)> λT (X∞), véase la Nota Suplementaria 4) . Es importante destacar que un aumento de λT está relacionado con un crecimiento mejorado en el equilibrio para una amplia gama de procesos dinámicos35, una reducción de la fuerza crítica de acoplamiento para la aparición de sincronización (como ~1 / λT) 37 o la aparición de un componente gigante en Fenómenos de percolación38. Por lo tanto, la tendencia natural hacia la cooperación entre redes débiles presentada en este trabajo también mejora la eficiencia y el crecimiento de todo el sistema. Volviendo al ejemplo de las tres aldeas, el análisis de los equilibrios de Nash revela que el equilibrio X0 (Fig. 1c) conduce a un λT mayor que X∞ (Fig. 1b, es decir, λT(X0)=4.78>λT(X)=4.57, para l = 1). Al final, esta es una buena noticia para todos los pueblos, ya que un λT más alto realza la fuerza de todo el conjunto39. Cabe señalar que estos resultados pueden utilizarse no sólo para la descripción, sino más importante para la prescripción de cómo las redes pueden maximizar sus resultados al interactuar con otras redes y cómo la aparición de nuevas interacciones entre redes aisladas influye en las propiedades estructurales y dinámicas del real Sistemas.

Por último, la migración entre los equilibrios descritos anteriormente podría tener una contraparte sugestiva en una amplia variedad de situaciones en las que una relación basada en la subyugación a un poderoso líder naturalmente emigró hacia un modelo nuevo y más productivo basado en la cooperación (véanse las referencias 40, 41 y Nota Complementaria 4 para un ejemplo histórico ilustrativo).

Discusión

En resumen, proponemos combinar la ciencia de redes y la teoría de juegos para analizar la elección de estrategias de interconexión en un juego de suma cero donde los jugadores no son agentes únicos sino redes. La creación de caminos entre las redes que interactúan conduce a diferentes equilibrios de Nash, algunos de los cuales benefician al competidor fuerte y algunos de ellos refuerzan a los menos favorecidos. Contrarrestantemente, mostramos que las transiciones entre los equilibrios de Nash coexistentes se restringen a los competidores más débiles, que en la práctica gobiernan el concurso, mientras que la red más fuerte es incapaz de cambiar el status quo en su propio interés.

Es importante destacar que la mayoría de los supuestos de nuestro modelo pueden modificarse para describir escenarios más realistas sin causar cambios cualitativos (véase la Nota Complementaria 5 para más detalles). Cuando se permite a cada jugador conectarse al resto de redes a través de más de un enlace (es decir, l> 1), el número de combinaciones de estrategias crece como lm(m−1) para m fijo. Sin embargo, el número de soluciones coexistentes y la fenomenología observada son totalmente equivalentes a los obtenidos para l = 1. Lo mismo ocurre con las topologías de red aleatorias (Erdös-Rényi), las redes de cualquier tamaño y las redes con diferentes capacidades, es decir, cuando ciertas redes pueden conectarse a través de un mayor número de enlaces de conector (o incluso más enlaces ponderados) que los demás competidores.

Además, extender el análisis a equilibrios mixtos de Nash, donde se permite cualquier distribución no entera de los enlaces de conector, no altera los resultados y proporciona una naturaleza probabilística al juego que amplía su aplicabilidad. Cuando se consideran más de 3 redes en el concurso, surgen nuevos tipos de equilibrios de Nash, pero de nuevo observamos la existencia de regiones amplias del espacio de parámetros donde redes débiles gobiernan toda la red de redes. Además, se han analizado diferentes definiciones de las rentabilidades basadas en la centralidad -como la centralidad de la interconexidad o cercanía- y sólo aquellas estrechamente relacionadas con la centralidad de los vectores propios llevan a una fenomenología rica en el número de equilibrios de Nash y el efecto de tales equilibrios en la Ganancias de los competidores.

Por último, en algunas redes sociales y económicas, las estrategias de conexión pueden verse influidas por las motivaciones individuales de los nodos conector, lo que da lugar a un posible conflicto con los intereses colectivos. Como primer paso para entender estos complejos escenarios, introdujimos una recompensa después de la referencia. 42, que incluye contribuciones individuales y colectivas (véase la nota complementaria 6): concluimos que la cooperación entre las redes débiles y su control del juego es un resultado frecuente que puede aparecer a niveles relativamente pequeños (o incluso cero) de incentivos colectivos, Aunque los detalles cuantitativos dependen significativamente de la topología de las redes.

La robustez de la fenomenología aquí presentada, sumada a su potencial aplicabilidad a casos reales, hace que este "poder de los débiles" sea un hecho valioso a considerar en el futuro modelado de procesos tecnológicos, biológicos o sociológicos en redes.


Métodos

Medir la importancia de los nodos y las redes

Utilizamos la centralidad de vectores propios xk para cuantificar la importancia de un nodo k en una red, que se puede obtener como un proceso iterativo que suma las centralidades de todos los vecinos de k:



Donde λ es una constante, xk es la centralidad de vectores propios del nodo k y Gkj son los componentes de la matriz de adyacencia, que podría ser tanto binaria como ponderada43. En la ecuación matricial (5) se lee λx=Gx para que x pueda expresarse como una combinación lineal de los vectores propios uk de la matriz de adyacencia G, siendo λk el conjunto de los valores propios correspondientes. La ecuación (5) puede considerarse como un proceso iterativo que comienza en t = 0 con un conjunto de condiciones iniciales x0. Independientemente de los valores de x0, el valor de x (t) en t → ∞ será proporcional al vector propio u1 asociado con el autovalor λ1 más grande. Por lo tanto, la centralidad de vectores propios se obtiene directamente del vector propio u1 de la matriz de adyacencia G, que también se mantiene para matrices de adyacencia ponderada. Como se explica en el texto principal, la centralidad acumulada por cada red se obtiene como la fracción de centralidad acumulada por sus nodos. Por último, utilizamos λ1 como medida de la intensidad de la red, ya que está relacionada con una serie de propiedades dinámicas de las redes y, a su vez, aumenta con el número de nodos, enlaces y el grado medio de la red44.


Selección de los nodos de conectores específicos

Como se explica en la ref. 32, la centralidad de los nodos conectores que enlazan redes independientes puede ser crucial en la distribución final de la centralidad. Los nodos centrales (C) de una red son los nodos con mayor centralidad de vectores propios, mientras que los nodos periféricos (P) son los nodos con una centralidad muy baja (ver Nota Complementaria 2 para más detalles). Cuando se conectan dos redes, los nodos del conector permiten distinguir entre conexiones central-central (CC) o conexiones periféricas-periféricas (PP). Es importante destacar que cuando una red de redes se divide en componentes desconectados, el cluster con el autovalor más grande adquiere toda la centralidad, mientras que el resto de los componentes (débiles) acumulan centralidad cero. Las conexiones PP conducen a un escenario cercano al caso desconectado, empujando casi la totalidad de la centralidad hacia la red fuerte. En consecuencia, cualquier estrategia de conexión basada en enlaces PP es prácticamente equivalente a negarse a conectarse con cualquier otra red. Por esta razón, hemos restringido las estrategias de las redes a las conexiones CC o sin conexiones (negarse a conectarse).

Por último, cabe señalar que las reglas de la competencia permiten a las redes conectarse a través de más de un enlace (por ejemplo, en A↔B). Por simplicidad, a lo largo de los ejemplos estudiados en este trabajo, representamos w enlaces conectores entre redes como un enlace de peso w. Sin embargo, en ciertos sistemas, los enlaces con un peso mayor que uno no podrían tener ningún significado real. En esos casos, el segundo (tercero, etc.) vínculo entre dos redes debe ser construido entre su segundo (tercero, etc) nodos más centrales, manteniendo la fenomenología cualitativamente sin cambios.

La matriz de adyacencia y los procesos dinámicos
Una variedad de procesos dinámicos que ocurren en una red puede ser descrita matemáticamente como n (t + 1) = Mn (t), donde n (t) es un vector cuyos componentes son el estado de cada nodo en el tiempo t (por ejemplo, el Población de individuos en cada nodo), y M, con Mij≥0, es una matriz que contiene las peculiaridades del proceso dinámico. Como M es una matriz primitiva, su valor propio más grande es positivo, verifica que λ1> | λi |, ∀ i> 1 y su vector propio asociado también es positivo. Por lo tanto, la dinámica de todo el sistema está dada por



De la ecuación (6) se obtiene que el sistema evoluciona hacia un estado asintótico independiente de la condición inicial y proporcional al primer vector propio u1:



Mientras que su valor propio asociado λ1 produce la tasa de crecimiento en el equilibrio asintótico. Si n (t) se normaliza de tal manera que | n (t) | = 1 después de cada iteración, n (t) → u1 cuando t → ∞ y existe una correspondencia entre la centralidad de vectores propios y el estado asintótico del sistema en equilibrio: Tanto la centralidad del vector propio como el estado asintótico del sistema son proporcionales al vector propio asociado con el autovalor más grande de la matriz de transición M.

Con respecto a la fenomenología presentada en este trabajo, en el caso de que estuviéramos preocupados por un proceso dinámico específico, reemplazaríamos la matriz de adyacencia G por la matriz de transición M, obteniendo la centralidad de vectores propios retenida por cada red sin pérdida de generalidad.



Referencias


1. Newman, M. E. J. The structure and function of complex networks. SIAM Rev. 45, 167–256 (2003). ISI Article
2. Boccaletti, S., Latora, V., Moreno, Y., Chavez, M. & Hwang, D. U.Complex networks: structure and dynamics. Phys. Rep 424, 175–308 (2006). ISI Article
3. Newman, M. E. J. Networks: an introduction Oxford Univ. Press (2010).
4. Castellano, C., Fortunato, S. & Loreto, V. Statistical physics of social dynamics. Rev. Mod. Phys. 81, 591–646 (2009). ISI Article
5. Pastor-Satorras, R. & Vespignani, A. Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86, 3200–3203 (2001). ISI CAS PubMed Article
6. Castellano, C. & Pastor-Satorras, R. Thresholds for epidemic spreading in networks. Phys. Rev. Lett. 105, 218701 (2010). CAS PubMed  Article 
7. Centola, D. The spread of behavior in an online social network experiment. Science 329, 1194–1197 (2010). ISI CAS PubMed Article
8. Gross, T. & Blasius, B. Adaptive coevolutionary networks: a review. J. R. Soc. Interface 5, 259–271 (2008). ISI PubMed Article
9. Apicella, C. L., Marlowe, F. W., Fowler, J. H. & Christakis, N. A.Social networks and cooperation in hunter-gatherers. Nature 481, 497–501 (2012). ISI CAS PubMed Article
10. Michor, F. & Nowak, M. A. The good, the bad and the lonely. Nature 419, 677–679 (2002). ISI
CAS PubMed Article
11. Szabo, G. & Fath, G. Evolutionary games on graphs. Phys. Rep. 446, 97–216 (2007). Article
12. Dreber, A., Rand, D. G., Fudenberg, D. & Nowak, M. A. Winners don’t punish. Nature 452, 348–350 (2008). ISI CAS PubMed Article
13. Santos, F. C., Santos, M. D. & Pacheco, J. M. Social diversity promotes the emergence of cooperative behavior. Nature 454, 213–216 (2008).  ISI CAS PubMed Article
14. Dall’Asta, L., Marsili, M. & Pin, P. Collaboration in social networks. Proc. Natl Acad. Sci. USA 109, 4395–4400 (2012). Article 
15. Perc, M. & Szolnoki, A. Coevolutionary games - a mini review. BioSystems 99, 109–125 (2010).  ISI PubMed Article
16. Wang, Z., Szolnoki, A. & Perc, M. Self-organization towards optimally interdependent networks by means of coevolution. New J. Phys. 16, 033041 (2014). Article
17. Wang, Z., Wang, L., Szolnoki, A. & Perc, M. Evolutionary games on multilayer networks: a colloquium. Eur. Phys. J. B 88, 124 (2015). CAS Article
18. Kivelä, M. et al. Multilayer networks. J. Complex Netw. 2, 203–271 (2014). Article
19. Boccaletti, S. et al. The structure and dynamics of multilayer networks. Phys. Rep. 544, 1–122 (2014). Article
20. Buldyrev, S. V., Parshani, R., Paul, G., Stanley, H. E. & Havlin, S.Catastrophic cascade of failures in interdependent networks. Nature 464, 1025–1028 (2010). ISI CAS PubMed Article
21. Radichi, F. & Arenas, A. Abrupt transition in the structural formation of interconnected networks. Nat. Phys. 9, 717–720 (2013). ISI CAS Article 
22. Aguirre, J., Sevilla-Escoboza, R., Gutiérrez, R., Papo, D. & Buldú, J. M. Synchronization of interconnected networks: the role of connector nodes. Phys. Rev. Lett. 112, 248701 (2014). CAS
PubMed Article
23. Quill, E. When networks network. ScienceNews 22 September 182, 18 (2012).
24. Nash, J. Equilibrium points in n-person games. Proc. Natl Acad. Sci. USA 36, 48–49 (1950).
CAS PubMed Article
25. Jackson, M. O., Rodriguez-Barraquer, T. & Tan, X. Social capital and social quilts: network patterns of favor exchange. Am. Econ. Rev. 102, 1857–1897 (2012). Article
26. Banerjee, A., Chandrasekhar, A. G., Duflo, E. & Jackson, M. O. The diffusion of microfinance. Science 341, 1236498 (2013). CAS PubMed Article
27. Hasanov, T., Ozeki, M. & Oka, N. in Proceedings of the 15th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing 53–57IEEE Computing Society (2014). 
28. Battiston, S. et al. Complexity theory and financial regulation. Science 351, 818–819 (2016).
CAS PubMed Article
29. Anand, K., Gai, P., Kapadia, S., Brennan, S. & Willison, M. A.Network model of financial system resilience. J. Econ. Behav. Org.85, 219–235 (2013). Article
30. Minoiu, C. & Reyes, J. A. A network analysis of global banking: 1978-2010. J. Financial Stability 9, 168–184 (2013). Article
31. Acemoglu, D., Ozdaglar, A. & Tahbaz-Salehi, A. Systemic risk and stability in financial networks. Am. Econ. Rev. 105, 564–608 (2015). Article
32. Aguirre, J., Papo, D. & Buldú, J. M. Successful strategies for competing networks. Nat. Phys. 9, 230–234 (2013). CAS Article 
33. Osborne, M. J. & Rubinstein, A. A Course in Game Theory MIT Press (1994).
34. König, M. D., Battiston, S., Napoletano, M. & Schweitzer, F. On algebraic graph theory and the dynamics of innovation networks. Networks Heterogeneous Media 3, 201–219 (2008). Article
35. Aguirre, J., Buldú, J. M. & Manrubia, S. C. Evolutionary dynamics on networks of selectively neutral genotypes: effects of topology and sequence stability. Phys. Rev. E 80, 066112 (2009). CAS
Article
36. Klemm, K., Serrano, M. A., Eguíluz, V. M. & San Miguel, M. A measure of individual role in collective dynamics. Sci. Rep. 2, 292 (2012).  CAS PubMed Article
37. Arenas, A., Daz-Guilera, A., Kurths, J., Moreno, Y. & Zhou, C.Synchronization in complex networks. Phys. Rep. 469, 93–153 (2008). Article
38. Bollobás, B., Borgs, C., Chayes, J. & Riordan, O. Percolation on dense graph sequences. Ann. Probab. 38, 150–183 (2010). Article
39. Komatsu, T. & Namatame, A. Dynamic diffusion in evolutionary optimised networks. Int. J. Bio-Inspired Comput. 3, 384–392 (2011). Article
40. Duby, G. Le temps des cathédrales. L'art et la société (980–1420)Gallimard (1976).
41. de Seta C., le Goff J. (eds) La città e le mura Edizioni Laterza, Roma-Bari (1989).
42. Grauwin, S., Bertin, E., Lemoy, R. & Jensen, P. Competition between collective and individual dynamics. Proc. Natl Acad. Sci. USA 106, 20622–20626 (2009). Article
43. Newman, M. E. J. Analysis of weighted networks. Phys. Rev. E 70, 056131 (2004). CAS Article
44. Restrepo, J. G., Ott, E. & Hunt, B. R. Characterizing the dynamical importance of network nodes and links. Phys. Rev. Lett. 97, 094102 (2006).