What is a k-core of a graph?

Teorema de la amistad: En ciertas redes hay siempre un amigo de todos

Grafo de la Amistad

Wikipedia



En el campo matemático de la teoría de grafos, el grafo de amistad (o grafo de molino de viento holandés o n-fan) F_n es un grafo no dirigido planar con 2n + 1 vértices y 3n enlaces. [1]

El grafo de amistad F_n se puede construir uniendo n copias del grafo de ciclo C3 con un vértice común. [2]

Por construcción, el grafo de amistad F_n es isomorfo al grafo de molino de viento Wd(3,n). Es la unidad de distancia con circunferencia 3, diámetro 2 y radio 1. El gráfico F₂ es isomorfo al grafo de mariposa.

Teorema de la amistad

El teorema de amistad de Paul Erdős, Alfréd Rényi y Vera T. Sós (1966) [3] afirma que los grafos finitos con la propiedad de que cada dos vértices tienen exactamente un vecino en común son exactamente los grafos de amistad. De manera informal, si un grupo de personas tiene la propiedad de que cada par de personas tiene exactamente un amigo en común, entonces debe haber una persona que sea amiga de todos los demás. Sin embargo, para los grafos infinitos, puede haber muchos grafos diferentes con la misma cardinalidad que tienen esta propiedad. [4]

Mertzios y Unger dieron una prueba combinatoria del teorema de la amistad. [5] Craig Huneke dio otra prueba. [6] Alexander van der Vekens reportó una prueba formal en Metamath en octubre de 2018 en la lista de correo de Metamath. [7]

Etiquetado y coloración.

El gráfico de amistad tiene el número cromático 3 y el índice cromático 2n. Su polinomio cromático se puede deducir del polinomio cromático del gráfico de ciclo C₃ y es igual a .

El grafo de amistad F_n es elegante si y solo si n es impar. Es elegante si y solo si n ≡ 0 (mod 4) o n ≡ 1 (mod 4). [8] [9]

Cada grafo de amistad es factor-crítico.

Teoría de grafos extremos

De acuerdo con la teoría de los grafos extremos, cada grafo con suficientes enlaces (en relación con su número de vértices) debe contener un ${\displaystyle k}$-fan como subgrafo. Más específicamente, esto es cierto para un grafo de n vértices si el número de enlaces es



donde es si k es impar y si si k es par. Estos límites generalizan el teorema de Turán sobre el número de bordes en un gráfico sin triángulos, y son los mejores límites posibles para este problema, ya que para un número menor de bordes existen gráficos que no contienen k-fan.

Referencias

1. Weisstein, Eric W. "Dutch Windmill Graph". MathWorld.
2. Gallian, J. A. (January 3, 2007), "Dynamic Survey DS6: Graph Labeling" (PDF), Electronic Journal of Combinatorics, DS6, 1-58. 
3. Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235. 
4. Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976),  "There are ${\displaystyle \scriptstyle 2^{\aleph _{\alpha }}}$ friendship graphs of cardinal ${\displaystyle \scriptstyle \aleph _{\alpha }}$", Canadian Mathematical Bulletin, 19 (4): 431–433, doi:10.4153/cmb-1976-064-1.
5. Mertzios, George; Walter Unger (2008), "The friendship problem on graphs" (PDF), Relations, Orders and Graphs: Interaction with Computer Science
6. Huneke, Craig (1 January 2002), "The Friendship Theorem", The American Mathematical Monthly, 109 (2): 192–194, doi:10.2307/2695332, JSTOR 2695332 
7. Alexander van der Vekens, Friendship Theorem (#83 of "100 theorem list") (11 October 2018) https://groups.google.com/forum/#!msg/metamath/j3EjD6ibhvo/ZVlOD3noBAAJ 
8. Bermond, J.-C.; Brouwer, A. E.; Germa, A. (1978), "Systèmes de triplets et différences associées", Problèmes Combinatoires et Théorie des Graphes (Univ. Orsay, 1976), Colloq. Intern. du CNRS, 260, CNRS, Paris, pp. 35–38, MR 0539936.
9. Bermond, J.-C.; Kotzig, A.; Turgeon, J. (1978), "On a combinatorial problem of antennas in radioastronomy", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam-New York, pp. 135–149, MR 0519261. 
10. Erdős, P.; Füredi, Z.; Gould, R. J.; Gunderson, D. S. (1995), "Extremal graphs for intersecting triangles", Journal of Combinatorial Theory, Series B, 64 (1): 89–100, doi:10.1006/jctb.1995.1026, MR 1328293.

Homofilia cerebral entre los mejores amigos

Usted comparte todo con su mejor amigo. Incluso las ondas cerebrales.

Por Natalie Angier | The New York Times




Un amigo te ayudará a moverte, como dice un viejo dicho, mientras que un buen amigo te ayudará a mover un cuerpo. ¿Y por qué no? Dejando de lado los reparos morales, ese buen amigo probablemente estaría de acuerdo en que la víctima era un imbécil intolerable que tuvo que venir y, por Dios, no deberías haber hecho esto, pero ¿dónde guardas la pala?

Los investigadores saben desde hace mucho tiempo que las personas eligen amigos que se parecen mucho en una amplia gama de características: de una edad, raza, religión, nivel socioeconómico, nivel educativo, inclinación política, nivel de pulcritud e incluso fuerza de agarre similares. El impulso hacia la homofilia, hacia la unión con otros que son lo menos posible, se encuentra entre los grupos tradicionales de cazadores-recolectores y las sociedades capitalistas avanzadas por igual.

Una nueva investigación sugiere que las raíces de la amistad se extienden incluso más allá de lo que se sospechaba anteriormente. Los científicos han descubierto que los cerebros de los amigos cercanos responden de maneras notablemente similares cuando ven una serie de videos cortos: los mismos reflujos y oleadas de atención y distracción, el mismo pico de procesamiento de recompensas aquí, alertas de aburrimiento allí.

Los patrones de respuesta neuronal evocados por los videos -en temas tan diversos como los peligros del fútbol universitario, el comportamiento del agua en el espacio exterior y Liam Neeson probando su comedia de improvisación- demostraron ser tan congruentes entre amigos, en comparación con los patrones que se ven entre las personas que no eran amigos, que los investigadores podían predecir la fortaleza del vínculo social de dos personas basándose solo en sus escáneres cerebrales.

"Me sorprendió la excepcional magnitud de la similitud entre amigos", dijo Carolyn Parkinson, una científica cognitiva de la Universidad de California en Los Ángeles. Los resultados "fueron más persuasivos de lo que hubiera pensado". La Dra. Parkinson y sus colegas, Thalia Wheatley y Adam M. Kleinbaum de Dartmouth College, informaron sus resultados en Nature Communications.

"Creo que es un documento increíblemente ingenioso", dijo Nicholas Christakis, autor de "Conectado: el poder de nuestras redes sociales y cómo moldean nuestro mundo" y un biosociólogo de la Universidad de Yale. "Sugiere que los amigos se parecen entre sí no solo superficialmente, sino en las estructuras mismas de sus cerebros".

Los hallazgos ofrecen evidencia tentadora del vago sentido que tenemos de que la amistad es más que intereses compartidos o de marcar los recuadros correctos en un perfil de Facebook. Se trata de algo que llamamos buena química.

"Nuestros resultados sugieren que los amigos pueden ser similares en la forma en que prestan atención y procesan el mundo que les rodea", dijo el Dr. Parkinson. "Ese procesamiento compartido podría hacer que la gente haga clic con más facilidad y tener el tipo de interacción social perfecta que puede ser tan gratificante".

Kevin N. Ochsner, un neurocientífico cognitivo de la Universidad de Columbia que estudia las redes sociales, dijo que el nuevo informe es "genial", "provocativo" y "plantea más preguntas de las que responde". Podría estar recogiendo rastros de "un inefable compartido". realidad "entre amigos.

El Dr. Ochsner ofreció su propia historia como evidencia de la primacía de la química sobre la mera biografía. "Mi futura esposa y yo éramos neurocientíficas en el campo, estábamos saliendo con sitios web, pero nunca fuimos emparejados", dijo.

"Luego nos encontramos como colegas y en dos minutos supimos que teníamos el tipo de química que engendra una relación".

La Dra. Parkinson, que tiene 31 años, usa anteojos con montura grande y tiene el aspecto saludable de un joven Sally Field, se describió a sí misma como introvertida, pero dijo: "He sido afortunada con mis amigos".

El nuevo estudio es parte de un aumento del interés científico en la naturaleza, la estructura y la evolución de la amistad. Detrás del entusiasmo hay un Kilimanjaro virtual de evidencia demográfica que dice que la falta de amistad puede ser venenosa, y que exige un costo físico y emocional comparable al de factores de riesgo más familiares como obesidad, presión arterial alta, desempleo, falta de ejercicio, fumar cigarrillos.

Los científicos quieren saber qué es exactamente lo que hace que la amistad tan saludable y el aislamiento social sean tan dañinos, y están recopilando pistas provocativas, si no aún definitivas.

El Dr. Christakis y sus colaboradores demostraron recientemente que las personas con fuertes vínculos sociales tenían concentraciones comparativamente bajas de fibrinógeno, una proteína asociada con el tipo de inflamación crónica que se cree que es la fuente de muchas enfermedades. Por qué la sociabilidad puede ayudar a bloquear la inflamación sigue sin estar clara.

Los investigadores también se han sentido intrigados por la evidencia de amistad entre animales no humanos, y no solo en candidatos obvios como primates, delfines y elefantes.

Gerald G. Carter del Smithsonian Tropical Research Institute en Panamá y sus colegas informaron el año pasado que las murciélagos vampiros cultivan relaciones cercanas con hembras no relacionadas y compartirán comidas con sangre con esos amigos en tiempos difíciles, un acto que salva vidas para los animales que no pueden sobrevivir mucho más que un día sin comida.

A través de años de rastrear los comportamientos de una gran bandada de grandes tetas, Josh A. Firth de la Universidad de Oxford y sus colaboradores descubrieron que las aves individuales mostraban preferencias claras por algunos miembros de la banda sobre otros. Cuando el buen amigo de un pájaro murió o desapareció, el herido abandonado comenzó a hacer oberturas con otras aves para reemplazar al camarada perdido.

Sin embargo, cuando se trata de la profundidad y complejidad de los vínculos, los humanos no tienen pares. El Dr. Parkinson y sus compañeros de trabajo habían demostrado anteriormente que las personas son conscientes de cómo todos los jugadores en su esfera social encajan, y los científicos querían saber por qué algunos jugadores en una red determinada son amigos cercanos y otros meramente asintiendo. conocidos.

Inspirados en la investigación de Uri Hasson de Princeton, decidieron explorar las reacciones neuronales de los sujetos ante los estímulos naturalistas cotidianos, que en la actualidad significa mirar videos.

Los investigadores comenzaron con una red social definida: una clase completa de 279 estudiantes de posgrado en una universidad sin nombre ampliamente conocida entre los neurocientíficos por haber sido Dartmouth School of Business.

Los estudiantes, que todos se conocían entre sí y que en muchos casos vivían en dormitorios juntos, se les pidió que llenaran cuestionarios. ¿Con cuál de sus compañeros se socializaron? ¿Compartieron comidas e iban al cine con invitaciones a sus hogares? A partir de esa encuesta, los investigadores diseñaron una red social de diversos grados de conectividad: amigos, amigos de amigos, amigos de tercer grado, amigos de Kevin Bacon.

Luego se les pidió a los estudiantes que participaran en un estudio de escaneo cerebral y 42 estuvieron de acuerdo. Como un dispositivo de resonancia magnética funcional rastreó el flujo de sangre en sus cerebros, los estudiantes vieron una serie de videoclips de diferentes longitudes, una experiencia que el Dr. Parkinson comparó al canal de navegación con alguien más en control del control remoto.

Vieron al astronauta Chris Hadfield demostrar cómo el agua se comporta como un gel pegajoso en baja gravedad. Vieron una escena tranquilamente sentimental de una boda judía entre dos personas que resultaron ser homosexuales.

Vieron al autor Eric Schlosser advertir sobre los peligros de permitir que unos pocos gigantes de comida rápida controlen nuestro suministro de alimentos. Vieron lo que mi buena amiga Judy Gradwohl y yo acordamos, al revisar los videos juntos más tarde, fue uno de los peores videos musicales jamás producidos, sobre un hombre con una deformidad facial obviamente falsa que es intimidado en el trabajo y desairado por su atractiva colega pero quien eventualmente gana su corazón cuando los matones se vuelven contra ella y él, Hombre Elefante falso, interviene y los golpea.

Los estudiantes vieron clips de comedia pratfall y un falso documental australiano tan sutil que ciertos espectadores confesaron que no se dieron cuenta de que era una parodia, pero les gustó de todos modos.

Analizando los escaneos de los estudiantes, el Dr. Parkinson y sus colegas encontraron una fuerte concordancia entre los patrones de flujo sanguíneo -una medida de la actividad neuronal- y el grado de amistad entre los diversos participantes, incluso después de controlar otros factores que podrían explicar las similitudes en las respuestas neuronales , como el origen étnico, la religión o el ingreso familiar.

Los investigadores identificaron regiones particularmente reveladoras de concordancia de patrones entre amigos, especialmente en el núcleo accumbens, en el cerebro anterior inferior, que es clave para el procesamiento de recompensa, y en el lóbulo parietal superior, ubicado hacia la parte superior y posterior del cerebro, aproximadamente la posición de un hombre bollo - donde el cerebro decide cómo asignar atención al entorno externo.

Utilizando los resultados, los investigadores pudieron entrenar un algoritmo computacional para predecir, a un ritmo muy superior al azar, la distancia social entre dos personas en función de la similitud relativa de sus patrones de respuesta neuronal.

El Dr. Parkinson enfatizó que el estudio fue un "primer paso, una prueba de concepto", y que ella y sus colegas todavía no saben lo que significan los patrones de respuesta neuronal: qué actitudes, opiniones, impulsos o pulgar mental hacen girar los escaneos. puede estar detectando.

Ellos planean realizar el experimento al revés: analizar a los estudiantes que aún no se conocen y ver si aquellos con los patrones neurales más congruentes terminan convirtiéndose en buenos amigos.

Alexander Nehamas, profesor de filosofía en la Universidad de Princeton y autor de un libro meditativo, "Sobre la amistad", apreció el diseño del estudio y su uso de videoclips para descubrir la firma de la amistad.

"Las elecciones estéticas que hacemos, las cosas que nos gustan, el gusto que tenemos en el arte, las obras de teatro, la televisión, los muebles, cuando los unes son componentes absolutamente esenciales de nuestro personaje, una indicación de quiénes somos", dijo. Vivimos "inmersos en el arte".

No es un arte elevado, no es un arte de la noche en la ópera, sino arte cotidiano: edificios, vallas publicitarias, ropa, los platos en un restaurante, los ritmos de percusión del metro en las vías del tren.

"Ver videos de TV es mucho más preciso para nuestra vida cotidiana que los tiempos en que vamos a un museo", dijo, y por lo tanto, potencialmente más revelador de lo que somos y lo que esperamos encontrar en un amigo.

Así que si le pones "The Cute Show: Sloths!", Acerca de un autoproclamado "santuario de perezosos" en Costa Rica, y si tu primer pensamiento no fue ooh, qué adorables son esos pequeños perezosos sonrientes, sino más bien, perezosos no son mascotas para abrazar y no bañan las algas de su pelaje, ¿no has oído hablar del mutualismo? - Llámame.

Seremos compañeros del alma biosnob de por vida.

Percolación y crecimiento explosivo detrás de la viralidad

Las nuevas leyes de las redes explosivas

Los investigadores están descubriendo las leyes ocultas que revelan cómo crece Internet, cómo se propagan los virus y cómo estallan las burbujas financieras.

Jennifer Ouellette | Quanta Magazine

Las redes crecen a medida que los nodos individuales se conectan entre sí. Al modificar las reglas que rigen cuando los nodos se conectan, los investigadores pueden configurar las propiedades de la red.

Paolo Čerić / PATAKK

La semana pasada, United Airlines mantuvo en tierra cerca de 5.000 vuelos cuando su sistema informático se cayó. El culpable: un enrutador de red defectuoso. Más tarde, la misma mañana, otro fallo de la computadora interrumpió la negociación en la Bolsa de Nueva York durante más de tres horas.

Algunos vieron la mano siniestra de un hacker en estas interrupciones, pero son mucho más probables ser una coincidencia, una característica intrínseca del sistema algo que un insecto. Las redes bajan todo el tiempo, consecuencia de niveles de interconexión sin precedentes. Las interrupciones pueden ocurrir incluso en las redes más robustas, ya sean redes eléctricas, mercados financieros globales o su red social favorita. Como señaló el ex reportero del Atlantic, Alexis Madrigal, cuando un error informático cerró la bolsa de valores Nasdaq en 2013, "Cuando las cosas funcionan de nuevas maneras, se rompen de nuevas maneras".

Una nueva comprensión de estos sistemas - la forma en que crecen, y cómo se rompen - ha surgido de la física del café.

Los investigadores suelen pensar en la conectividad de red como sucediendo de una manera lenta y continua, similar a la forma en que el agua se mueve a través de granos de café recién molido, saturando lentamente todos los gránulos para convertirse en café en el contenedor de abajo. Sin embargo, en los últimos años, los investigadores han descubierto que en casos especiales, la conectividad podría surgir con una explosión, no un gemido, a través de un fenómeno que han denominado "percolación explosiva".

Clusters cultivados por percolación explosiva

Esta nueva comprensión de cómo surge la über-conectividad, que fue descrita a principios de este mes en la revista Nature Physics, es el primer paso hacia la identificación de señales de advertencia que pueden ocurrir cuando tales sistemas fallan -por ejemplo, cuando las redes eléctricas comienzan a fallar o cuando una enfermedad infecciosa comienza a convertirse en una pandemia mundial. La percolación explosiva puede ayudar a crear estrategias eficaces de intervención para controlar ese comportamiento y, quizás, evitar consecuencias catastróficas.

Un giro explosivo

Los modelos matemáticos tradicionales de percolación, que datan de la década de 1940, ven el proceso como una transición suave y continua. "Pensamos en la percolación como el agua que fluye por el suelo", dijo Robert Ziff, físico de la Universidad de Michigan, que ha estado estudiando transiciones de fase durante los últimos 30 años. "Es una formación de conectividad de largo alcance en el sistema".

La formación de conectividad puede entenderse como una transición de fase, el proceso por el cual el agua se congela en hielo o se separa en vapor.

Las transiciones de fase son omnipresentes por naturaleza, y también proporcionan un modelo práctico de cómo los nodos individuales en una red aleatoria se unen gradualmente, uno por uno, a través de conexiones de corto alcance a lo largo del tiempo. Cuando el número de conexiones alcanza un umbral crítico, un cambio de fase hace que el mayor clúster de nodos crezca rápidamente y resultados de über-conectividad. (Visto de esta manera, el proceso de percolación que da lugar a su taza de mañana de Joe es un ejemplo de una transición de fase.La agua caliente pasa a través de frijoles tostados y cambia a un nuevo estado - café.)

Raissa D'Souza, física de la Universidad de California, Davis, 

está explorando cómo las intervenciones a pequeña escala
pueden alterar una red grande y compleja

.

La percolación explosiva funciona un poco diferente. La noción surgió durante un taller en 2000 en el Instituto Fields para la Investigación en Ciencias Matemáticas en Toronto. Dimitris Achlioptas, científico de computación de la Universidad de California en Santa Cruz, propuso un posible medio para retrasar la transición de fase a una red densamente conectada, fusionando la noción tradicional de percolación con una estrategia de optimización conocida como el poder de dos opciones. En lugar de dejar que dos nodos aleatorios se conecten (o no), considere dos pares de nodos aleatorios y decida qué par prefiere conectar. Su elección se basa en criterios predeterminados; por ejemplo, puede seleccionar el par que tenga menos conexiones preexistentes con otros nodos.

Debido a que un sistema aleatorio normalmente favorecería a los nodos con las conexiones más preexistentes, esta elección forzada introduce un sesgo en la red, una intervención que altera su comportamiento típico. En 2009, Achlioptas, Raissa D'Souza, físico de la Universidad de California, Davis, y Joel Spencer, matemático del Instituto Courant de Ciencias Matemáticas de la Universidad de Nueva York, encontraron que modificar el modelo de percolación tradicional de esta manera cambia dramáticamente la naturaleza de la transición de fase resultante. En lugar de surgir de una marcha lenta y continua hacia una conectividad cada vez mayor, las conexiones emergen globalmente de una vez por todas en todo el sistema en una especie de explosión, de ahí el apodo de "percolación explosiva".

El concepto ha explotado por derecho propio, generando innumerables documentos en los últimos seis años. Muchos de los trabajos discuten si este nuevo modelo constituye una transición de fase verdaderamente discontinua. De hecho, en 2011 los investigadores mostraron que para el modelo particular analizado en el estudio original de 2009, las transiciones explosivas sólo ocurren si la red es finita. Mientras que las redes como Internet tienen como máximo alrededor de mil millones de nodos, las transiciones de fase se asocian más comúnmente con los materiales, que son redes intrincadas de tantas moléculas (aproximadamente 1023 o más) que los sistemas son efectivamente infinitos. Una vez extendidas a un sistema verdaderamente infinito, las percolaciones explosivas parecen perder parte de su boom.

Sin embargo, D'Souza y sus cohortes tampoco han estado ociosos. Han descubierto muchos otros modelos de percolación que producen transiciones realmente abruptas. Estos nuevos modelos comparten una característica clave, según D'Souza. En la percolación tradicional, los nodos y pares de nodos se eligen al azar para formar conexiones, pero la probabilidad de que dos grupos se fusionen es proporcional a su tamaño. Una vez que un gran grupo se ha formado, domina el sistema, absorbiendo cualquier racimo más pequeño que podría fusionarse y crecer.

Sin embargo, en los modelos explosivos, la red crece, pero el crecimiento del gran grupo se suprime. Esto permite que muchos clústeres grandes pero desconectados crezcan, hasta que el sistema alcance el umbral crítico en el que agregar sólo uno o dos enlaces adicionales desencadena un cambio instantáneo a la über-conectividad. Todos los grandes clusters se combinan a la vez en una sola fusión violenta.

Un nuevo paradigma para el control

D'Souza quiere aprender a controlar mejor las redes complejas. La conectividad es una espada de doble filo, según ella. "Para sistemas operativos normales (como Internet, las redes aéreas o la bolsa de valores), queremos que estén fuertemente conectados", dijo. "Pero cuando pensamos en la propagación de epidemias, queremos reducir el alcance de la conectividad". Incluso cuando la conectividad es deseable, a veces puede ser contraproducente, causando un colapso potencialmente catastrófico del sistema. "Nos gustaría ser capaces de intervenir en el sistema fácilmente para mejorar o retrasar su conectividad", dependiendo de la situación, dijo.

La percolación explosiva es un primer paso en el pensamiento sobre el control, según D'Souza, ya que proporciona un medio de manipular el inicio de la conectividad de largo alcance a través de interacciones a pequeña escala. Una serie de intervenciones a pequeña escala puede tener consecuencias dramáticas - para bien o para mal.

Los profesionales de las relaciones públicas a menudo se preguntan cómo el trabajo de D'Souza podría ayudar a sus productos ir viral. Ella responde típicamente señalando que sus modelos suprimen realmente comportamiento viral, por lo menos en el corto plazo. "¿Quieres ganar todas las ganancias tan rápido como puedas, o quieres suprimir el crecimiento, así que cuando sucede, más gente aprende de inmediato?", Dijo. Lo mismo ocurre con las campañas políticas, según Ziff. Siguiendo este modelo, pasarán gran parte de su tiempo a principios de la campaña en los esfuerzos locales de base, creando grupos localizados de conexiones y suprimiendo la aparición de conexiones de largo alcance hasta que la campaña esté lista para ir nacional con un gran chapoteo mediático.

En otros sistemas, como los mercados financieros o las redes de energía eléctrica, cuando ocurre un colapso, es probable que sea catastrófico, y este enfoque de mosaico podría ser utilizado para invertir el proceso, rompiendo el sistema conectado en una colección de agrupamientos disjuntos, o "islas", para evitar catastróficas fallas en cascada. Idealmente, uno esperaría encontrar un "punto dulce" para el nivel óptimo de intervención.

00:00/21:44

En las redes eléctricas, las empresas de servicios públicos pierden dinero cada vez que una línea baja, por lo que idealmente uno debe tratar de evitar cualquier tiempo de inactividad. Sin embargo, actuar para evitar cualquier interrupción en absoluto puede conducir inadvertidamente a interrupciones muy grandes que son mucho más costosas. Por lo tanto, el fomento de pequeños "fallos" en cascada puede disipar los desequilibrios energéticos que de otro modo habrían causado fracasos masivos más adelante, una estrategia potencialmente inteligente a pesar de que come en los márgenes de beneficio. "Si suelen desencadenar pequeñas cascadas, nunca se obtienen eventos realmente masivos, pero sacrifican todo ese beneficio a corto plazo", explicó D'Souza. "Si se evitan las cascadas a toda costa, se puede obtener una gran ganancia, pero eventualmente se producirá una cascada, y será tan masiva que [podría] borrar todo su beneficio".

El siguiente paso es identificar los signos que pueden indicar cuando un sistema está a punto de ser crítico. Los investigadores entienden las transiciones de fase como las que suceden cuando el agua se convierte en hielo y pueden identificar señales de un cambio inminente. Lo mismo no puede decirse de la percolación explosiva. "Una vez que tengamos una mejor comprensión, podremos ver cómo nuestras intervenciones de control están impactando el sistema", dijo D'Souza. "Vamos a tener estos datos que podemos analizar en tiempo real para ver si estamos viendo la firma de las señales de alerta temprana de muchas clases diferentes de transiciones".

Las transiciones de fase han fascinado físicos y matemáticos por décadas, así que ¿por qué se ha encontrado este comportamiento explosivo sólo ahora? D'Souza piensa que es porque el descubrimiento requirió la fusión de ideas de varios campos, sobre todo la idea de Achlioptas de mezclar algoritmos y física estadística, creando así un emocionante nuevo fenómeno de modelado. "Realmente es un nuevo paradigma de percolación", dijo Ziff.

Redes sociales de una abadesa medieval en Catalunya

Imaginando asociaciones de la abadesa Emma

Por Jonathan Jarrett - A Corner of Tenth-Century Europe

Muy viejos lectores de este blog se puede que recuerde un debate que se puso en marcha en este blog en junio de 2008, a propósito de un artículo en la revista Journal of Neurocomputing que estaba utilizando la información Carta medieval para mostrar la visualización de datos de redes sociales. [1] yo estaba inicialmente escéptico, pero hablando con dos de los autores me tiene mucho más interés y, posteriormente, hablé una de ellas en la entrega de un documento en los últimos problemas y posibilidades del comienzo de la sesión Diplomática medieval en Leeds, un documento que queríamos publicar, pero que por desgracia en al final no podría incluirse en la publicación final. 2 Eso sigue siendo una lástima, ya que había cosas buenas para pensar con allí, pero por supuesto lo que cualquier historiador se trata de datos sociales densa va a querer saber acerca de este tipo de software y técnicas es, '¿cómo va a ayudarme con mis cosas?' y puesto que responder a esta cuestión por lo general implica una gran cantidad de entrada de datos, se ha tendido a descansar allí.


También está la cuestión de hasta qué punto una "Representación de la red social medieval con algoritmo de fuerza dirigida" como esta de Boulet et al., "SOM lotes núcleo y los métodos de Laplace relacionados para análisis de redes sociales", fig. 1, se puede ver por sí mismo, por lo que, por supuesto, en ese artículo que a continuación pasan mucho tiempo y lo descomponen.

Por mi área de interés, esto se cambió a mediados de 2012 como el incansable Joan Vilaseca de la página web Cathalaunia comenzó a investigar la aplicación de estas técnicas a la base de datos que mantiene allí, que incluye un buen montón de documentos de los que yo ejercer mi oficio. Magistra et Mater, que estaba recibiendo interesados ​​en las posibilidades de estas cosas entonces también, escribió algunas ideas iniciales acerca de lo que Joan y otros estaban haciendo a ella en diciembre de 2012, y yo ya había hecho una nota talón de hablar de ello en octubre de ese año, pero, además, se ha puesto en cola desde entonces. ¡Todavía hay mucho que decir, sin embargo!

Lo que llamó especialmente mi interés era que Joan puso un post en su blog en el que se produjo una lista de las personas mejor conectadas en su base de datos, los que aparecen con los más otras personas, y una vez que los reyes que se ven cláusulas de citas y sus notarios se separaron por filtración, más o menos la parte superior de la lista era abadesa Emma de Sant Joan de Ripoll. Puesto que no es tal vez nadie en el mundo que se preocupa más por la abadesa Emma que yo, 3 esto parecía un muy buen tipo de los casos con los que responder a la pregunta: ¿este tipo de análisis nos brindan más información de la que ya tenemos? Y, extrañamente, creo que mi conclusión es que para mí es tal vez lo más valioso para acentuar lo que no hacemos.


Las relaciones de abadesa Emma en la base de datos Cathalaunia color de acuerdo al grado de conectividad

Para hablar de esto es necesario para conseguir que el lector clara sobre exactamente lo que Joan ha hecho en realidad aquí, por supuesto. Tan simplemente como puedo decirlo, lo que tenemos encima es una gráfica integrada de la siguiente manera. En la base de datos de Joan Emma aparece en los documentos 50 y 50 en aquellos documentos que se produce con una gran cantidad de personas. Buscando sólo la más significativa, Joan excluidos del recuento de todas las personas con las que Emma se presentó una sola vez, lo cual es mucho teniendo en cuenta que se organizó la audiencia Vall de Sant Joan en la que cerca de 500 personas juraron testimonio de ella y luego todavía hay 48 más documentos con ella en. Esto aún deja a 112 personas con el que se registró asociar más de una vez, de hecho, el total de las asociaciones todavía en el recuento es 1292. Muchas de estas personas también se relacionan entre sí y lo que tiene encima es una visualización asistida por ordenador de todos esos enlaces, con Emma en el centro y todos los demás se retiró a donde se pueden ver los enlaces. Pero ya se puede ver por la forma en que algunos de los enlaces se hacen con bandas gruesas de color más oscuro que algunas de estas personas dominan la muestra mucho más que otros. Entonces, ¿quién es esta gente? Pues bien, si se carga la versión SVG de este gráfico en el blog de Joan puedes hacer clic directamente a través de sus registros de base de datos, lo cual es maravilloso, pero en definitiva los cinco primeros son dos sacerdotes llamados gentiles y Guisad, y luego tres legos, a saber, Reinoard, Guimara y Tudiscle.


Archivo de la Corona d'Aragón, Cancilleria, Pergamins Seniofredo 39 (versión de menor calidad), con la firma de los gentiles inferior izquierdo y central

Todo esto suena más o menos sensible a mí: aunque creo que sólo los gentiles y Reinoard, tal vez Tudiscle, habría estado en los cinco primeros me había adivinado, puedo ver por qué están todos aquí. Gentiles era algo así como el jefe escriba de Sant Joan: él aparece en la primera aparición de Emma como un adulto, continuó apareciendo unos seis a diez años de su muerte, y en ese tiempo una gran cantidad de los documentos de la abadía lleva a su scribal firma, a pesar de que como Federico Udina señaló cuando editó estos documentos, no todos están en la misma mano. Se supone que esto significa que él tenía subordinados que firman cosas fuera para él y que su nombre era lo suficientemente importante que todavía tenía que estar allí. 4 Guisad era otro escriba frecuente para la abadía, al parecer más viejo, y también apareció en el panel de un par de las audiencias en la que Emma pursused las personas por sus derechos sobre sus tierras. 5 Reinoard era jefe de uno de los asentamientos en la Vall de Sant Joan y trabajó como ejecutor judicial para Emma vez, además de aparecer en la corte cuando ella los llamaba, era un colaborador de ella quienes he discutido en otro lugar. 6 Tudiscle y Guimara presentan un caso más interesante: estos son dos de los propietarios quienes Emma llevó a los tribunales, pero en ambos casos los episodios eran parte de una relación más larga con la abadía que había aquí desglosado. He escrito sobre estos dos, así, precisamente porque creo que en el caso de Tudiscle la audiencia fue parte de la reparación de esa relación, ya que su importancia no parece haber sufrido posteriormente, mientras que Guimara parece posteriormente no haber trabajado con la abadesa y de hecho parece haber logrado cambiar mucho de propiedad una vez donado al convento en el hermano pequeño de Emma, ​​el conde-Marquis Sunyer de Barcelona, ​​Girona y Osona, como parte de la campaña de Sunyer para recortarle las alas.7  La abadesa gobernada de forma independiente, de su hermana Pero antes que había trabajado para Emma, ​​y ​​estas personas sin duda hará que la gente buena para estudiar si se quiere entender cómo funcionaba Emma, ​​que es, por supuesto, por qué lo hice.


Las mismas relaciones muestran ahora de acuerdo a su modularidad, es decir, por el tamaño de los grupos internos a los datos

Por lo tanto, la primera respuesta a la gran pregunta acerca de si esto me dice nada se parece a "no"; Yo ya había encontrado a estas personas por métodos más antiguos. Pero no estoy aquí podría decirse que el objetivo: la cosa es que esos métodos eran muy parecido a lo que Joan de programación automatiza todos menos. Fui a través de los documentos, tomaron nota de los nombres que presentaron recidiva más, montado perfiles de sus apariencias y decidieron que eran las personas con las que podría contar la historia con. base de datos y la representación gráfica de Joan juntos significan que podría, si yo estaba empezando de nuevo, hacerlo en unos diez minutos el mismo ejercicio que me llevó semanas cuando en realidad lo hice. Que podía hacer (y puede hacerlo) lo mismo ahora con el conde-Marquis Guifré II Borrell, predecesor y hermano de Sunyer, para los que no he hecho el mismo trasfondo de análisis intensivo de datos, con muchos menos problemas de lo que estaba esperando. Así que en términos de facilitación de la investigación para otros, esto es un gran paso adelante incluso si no me ayuda. Puedo de hecho, sólo digo la cantidad de uso es precisamente porque lo había hecho ya por otros medios! (Ya sea Joan tuvo que poner un menor número de horas para hacer que suceda lo que lo hice para mi investigación es otra cuestión, por supuesto ...)

De todos modos, como he dicho anteriormente, lo que ahora me hace pensar que es la forma imperfecta nuestros datos a veces es por el tipo de preguntas que nos gustaría preguntar. Si, por los primeros principios, nos preguntamos quién era el principal contacto de una abadesa medieval temprano, probablemente suponer que los principales fueron sus monjas. Así que de hecho pueden haber estado aquí, pero como he observado en un próximo documento supuestamente-, mientras que Emma estaba a cargo de Sant Joan que saber los nombres de sólo otras dos monjas, y los que sólo se ven cuando se unen el convento, no tenemos ni idea de lo que las relaciones de Emma con ellos eran like.8 Si, pues, nos permitimos recordar que este abadesa era la hija de un conde, entonces podríamos pensar en su familia como una segunda cadena importante. Pero Emma casi no aparece con su familia, y cuando lo hace se necesita una lectura muy cuidadosa: Creo que ella sólo se produce vivo y en persona con el hermano Sunyer en la audiencia Vall de Sant Joan donde ella se encontraba en la teoría de llevarlo a los tribunales, por ejemplo, . 9 (Ella también se convierte en imagen como vecino de la tierra que estaba transfiriendo dos veces, pero por supuesto que no estaba realmente allí para eso, aunque nos da otra razón para suponer que tenían otras relaciones. 10) También en el extremo defender en ese ocasión fue su hermano probablemente anciano-Miró, conde de Cerdanya, que en su testamento llamada Emma uno de sus ejecutores y tenía su llamado "mi más querida hermana '; Creo que ocurre con él una vez de lo contrario. 11 Ella tiene Radulfo consagrar una iglesia con ella una vez, creo que eso es todo sin embargo. 12 Podemos más o menos vemos de esto que este conjunto de hermanos fueron estrechos colaboradores, aunque no siempre los muy pronto, pero la cantidad de apariciones en realidad no reflejan lo que podemos adivinar la importancia de esas relaciones habría sido.


La piedra en memoria de abadesa Emma en la iglesia de la abadía de Sant Joan de les Abadesses

La información que obtenemos de esto, por lo tanto, no está mal, pero es parcial. Emma probablemente hizo ver gentiles y hablar con él casi todos los días de su vida adulta. No es claro si Guisad también fue un sacerdote de la abadía pero si es así, él también habría sido una característica habitual de sus días. Ella colocó un montón de confianza en Reinoard, y esa relación era probablemente importante para los dos de ellos en la crianza de Reinoard encima de sus compañeros y mostrando cómo esos tipos Emma podría recompensar a sus colaboradores. Tudiscle y Guimara, al menos al principio, eran más de ese tipo de persona e incluso si las relaciones probablemente no significan tanto para Emma como con el hermano que tenía Miró, por ejemplo, están históricamente muy interesante y cualquier persona que trabaje en Emma estaría bien servido por el que se apunta hacia ellos. Pero también hay datos que faltan tranquilo y que debe de haber hecho una gran cantidad más de su vida, y que realmente no podemos reconstruir. No es de ninguna manera el fallo de esta tecnología que no puede traer eso a nuestro aviso: es obvio que no nos puede devolver información que no pusimos en Pero eso también significa que la tecnología no es más que uno de. las herramientas que tenemos para usar esa información para comprender en su contexto, algunos de los cuales contexto es simplemente lo que no está allí. 13

Referencias

1. Romain Boulet, Bertrand Jouse, Fabrice Rossi & Nathalie Villa, “Batch kernel SOM and related Laplacian methods for social network analysis” in Journal of Neurocomputing Vol. 71 (Amsterdam 2008), pp. 1579-1573.

2. What final publication, you ask? Why, Jonathan Jarrett & Allan Scott McKinley (edd.), Problems and Possibilities of Early Medieval Charters, International Medieval Research 19 (Turnhout 2013). You could buy it here if you wanted!

3. See J. Jarrett, “Power over Past and Future: Abbess Emma and the nunnery of Sant Joan de les Abadesses” in Early Medieval Europe Vol. 12 (Oxford 2003), pp. 229-258; idem, Rulers and Ruled in Frontier Catalonia 880-1010: pathways of power (Woodbridge 2010), pp. 23-72.

4. Ibid. pp. 29-30; see Federico Udina Martorell, El Archivo Condal de Barcelona en los siglos IX-X: estudio crítico de sus fondos, Textos 18/Publicaciones de le Sección de Barcelona 15 (Madrid 1951), p. 205 for the argument.

5. Jarrett, Rulers and Ruled, p. 59 n. 162.

6. Ibid. pp. 39, 41-42.

7. Ibid. pp. 52-53 (Tudiscle), 53-57 (Guimarà) & 64-65 (Sunyer’s pressure on the nunnery).

8. J. Jarrett, “Nuns, Signatures and Literacy in late-Carolingian Catalonia”, to appear in a Festschrift for Rosamond McKitterick first planned in 2010.

9. La audiencia está mejor impresa en Ramon Ordeig i Mata (ed.), Catalunya Carolíngia IV: els comtats d’Osona i Manresa, Memòries de la Secció Històrico-arqueològica LIII (Barcelona 1999), 3 vols, doc. nos 119 & 120, si bien las notas paleográficas de Udina, Archivo Condal, doc. no. 38, son todavía muy útiles.

10. Ordeig, Catalunya Carolíngia IV, doc. nos 103, 105 & 155. Hay algunos otros casos donde ella y Sunyer ambos giran como vecinos, pero no de las mismas propiedades, por lo que no creo que realmente cuenta aquí.

11. El testamento está solo impreso en Prosper de Bofarull y Mascaró, Los condes de Barcelona vindicados, y cronología y genealogía de los reyes de España considerados como soberanos independientes de su marca (Barcelona 1836, repr. 1990), 2 vols. I pp. 88-90. En Ordeig, Catalunya Carolíngia IV, doc. no. 57 Miró presidió la audiencia donde Emma fue la demandada, pero ella fue representada por un mandatario y ella no estaba presente.

12. Udina, Archivo Condal, doc. no. 73. Los dos también ocurrieron como vecinos comunes en Ordeig, Catalunya Carolíngia IV, doc. nos 155 & 419, pero de nuevo eso sólo dice que probablemente se conocieron en algún momento..

13. Cf. Jarrett, “Poor Tools to Think With: the human space in digital diplomatics” in Georg Vogeler & Antonella Ambrosiani (edd.), Digital Diplomatics 2011, Beihefte der Archiv für Diplomatik (München forthcoming), pp. 291-302.

Cuando las redes enredan

When Networks Network

Once studied solo, systems display surprising behavior when they interact

By Elizabeth Quill

Half a dozen times each night, your slumbering body performs a remarkable feat of coordination.

During the deepest throes of sleep, the body’s support systems run on their own timetables. Nerve cells hum along in your brain, their chitchat generating slow waves that signal sleep’s nether stages. Yet, like buses and trains with overlapping routes but unsynchronized schedules, this neural conversation has little to say to your heart, which pumps blood to its own rhythm through the body’s arteries and veins. Air likewise skips into the nostrils and down the windpipe in seemingly random spits and spats. And muscle fluctuations that make the legs twitch come and go as if in a vacuum. Networks of muscles, of brain cells, of airways and lungs, of heart and vessels operate largely independently.

Every couple of hours, though, in as little as 30 seconds, the barriers break down. Suddenly, there’s synchrony. All the disjointed activity of deep sleep starts to connect with its surroundings. Each network — run via the group effort of its own muscular, cellular and molecular players — joins the larger team.

This change, marking the transition from deep to light sleep, has only recently been understood in detail — thanks to a new look at when and how the body’s myriad networks link up to form an übernetwork.

“As I go from one state to another, immediately the links between the physiological systems change,” says Plamen Ivanov, a biophysicist at Boston University. “It is quite surprising.”

And it’s not just in bodies. Similar syncing happens all the time in everyday life. Systems of all sorts constantly connect. Bus stops pop up near train stations, allowing commuters to hop from one transit network to another. New friends join your social circle, linking your network of friends to theirs. Telephones, banks, power plants all come online — and connect online.

A rich area of research has long been devoted to understanding how players — whether bodily organs, people, bus stops, companies or countries — connect and interact to create webs called networks. An advance in the late 1990s led to a boom in network science, enabling sophisticated analyses of how networks function and sometimes fail. But more recently investigators have awakened to the idea that it’s not enough to know how isolated networks work; studying how networks interact with one another is just as important. Today, the frontier field is not network science, but the science of networks of networks.

“When we think about a single network in isolation, we are missing so much of the context,” says Raissa D’Souza, a physicist and engineer at the University of California, Davis. “We are going to make predictions that don’t match real systems.”

Like their single-network counterparts, networks of networks show up everywhere. By waking up in the morning, going to work and using your brain, you are connecting networks. Same when you introduce a family member to a friend or send a message on Facebook that you also broadcast via Twitter. In fact, anytime you access the Internet, which is supported by the power grid, which gets its instructions via communications networks, you are relying on interdependent systems. And if your 401(k) lost value during the recent recession, you’re feeling the effects of such systems gone awry.

Findings so far suggest that networks of networks pose risks of catastrophic danger that can exceed the risks in isolated systems. A seemingly benign disruption can generate rippling negative effects. Those effects can cost millions of dollars, or even billions, when stock markets crash, half of India loses power or an Icelandic volcano spews ash into the sky, shutting down air travel and overwhelming hotels and rental car companies. In other cases, failure within a network of networks can mean the difference between a minor disease outbreak or a pandemic, a foiled terrorist attack or one that kills thousands of people.

Understanding these life-and-death scenarios means abandoning some well-established ideas developed from single-network studies. Scientists now know that networks of networks don’t always behave the way single networks do. In the wake of this insight, a revolution is under way. Researchers from various fields are rushing to figure out how networks link up and to identify the consequences of those connections.

ENLARGE

NETWORK MILESTONESView larger image | A major breakthrough in the study of networks occurred when researchers discovered that a lot of real-world networks take a similar form. Dubbed “small-world,” these single networks are characterized by clustering and shortcuts. Another refinement in thinking is now taking place as attention turns to interacting networks.T. Dubé

Investigators including Ivanov are analyzing a deluge of data to understand how networks cooperate to make bodies function. Other researchers are probing the Earth around them to identify the links that keep the planet in balance. But it’s not all rainbows and butterflies. Much of the recent focus has been on the potential dangers that come with connection. In one landmark study, researchers at Boston University and elsewhere have developed math for explaining the way networks of networks can suddenly break down. Studying the bad along with the good may lead to a sort of “how to” for designing integrated systems that not only perform well in normal times, but also keep working when things go wrong.

Cascades of failure

A series of CNN news clips posted on YouTube highlight the vulnerability of interdependent systems. In what Wolf Blitzer repeatedly reminds the viewer is only an “exercise,” former U.S. government officials convene to respond to a simulated cyberattack. The War of the Worlds–esque report begins with a Russian computer infecting a smartphone with a virus. After jumping to other smartphones, the bug makes its way into U.S. computers. From there it crashes communication networks, which in turn take out power stations. The ensuing blackout shuts down transportation networks. Each failure leads to yet more failures as the effects of a single infection bounce back and forth between systems. Having no control over the Russian computer system and no authority to shut down smartphones, the U.S. government is powerless.

Shlomo Havlin of Bar-Ilan University in Israel sometimes shows portions of these clips during talks he gives on networks of networks. “If you have damage in one system, it can lead to damage in another system,” Havlin says. But he points out that concerns about such rippling damages are not entirely new. Several reports — such as the CNN coverage — have highlighted worries about how fragile interdependent systems might be. “What was not known was a systematic way to study this, a framework,” Havlin says.

He first became interested in the problem when a program reviewer from the U.S. Defense Threat Reduction Agency visited the Boston University physics department in 2009. The agency was funding Havlin and H. Eugene Stanley, along with Boston colleagues Gerald Paul and Sergey Buldyrev, to work on questions plaguing single networks. The reviewer mentioned a new topic that interested the agency: How resilient are interacting networks when something goes amiss? Proposals were due in a couple of weeks. Despite the short time frame, the team, later joined by Bar-Ilan colleague Roni Parshani, decided to tackle the issue.

Overnight Havlin came up with a way of thinking about it. Single networks are typically represented by dots joined by lines. The dots, called nodes, are the players in the network. The lines, called edges or links, represent connections between those players. Havlin’s insight was to connect some of the nodes in one network with nodes in another via a new type of line. His new lines, called dependency links, signal places where a node in one network relies on a node in the other to function — say, a computer that can’t get by without its sole power source. These key dependencies could allow a failure to propagate between systems.

Once Havlin outlined a way of thinking about the problem, Buldyrev worked through the math. It wasn’t simple. He had to use equations to explain each state of each network as the random removal of one node triggered the removal of other nodes. Buldyrev, whom Paul calls “a mathematical genius,” cracked it. Answering the program reviewer’s initial question took only about a week.

“One morning, I came in and Shlomo was — not quite dancing on the table — but he was very, very excited,” Paul says.

In their analysis of connected networks, the researchers found a type of mathematical behavior that couldn’t have been predicted from knowledge of single networks. When a node is removed from a single network, the failure tends to propagate gradually, the network coming apart bit by bit by bit. But removing nodes in a network of networks means the breakdown can occur abruptly. As nodes go offline, the system initially appears to be working properly. But all of a sudden, a threshold is reached. Lose one more node and — poof — the whole thing falls to pieces.

“Even if one more node fails, the network collapses completely,” Havlin says. “It makes the network a much more risky place.”

Stanley likens the single-network scenario to a drunken prisoner trying to escape with a pair of wire clippers. As the prisoner makes random cuts along a fence, a hole develops that gradually gets bigger and bigger. After a little while, maybe, the prisoner can stick an arm through, and with a few more snips, a head. Eventually enough snips may allow the prisoner’s whole body to fit through. But in the case of networks of networks, the prisoner cuts just one or two wires and then appears to hit on a magical one that makes the whole fence disintegrate. The prisoner can walk to freedom.

ENLARGE

BACK-AND-FORTH FAILURESView larger image | When networks depend on other networks, such as a communications network that relies on a power grid, failure can cascade back and forth between the two. This behavior may explain sudden breakdowns in interacting systems. Thus, the effects of an attack on a single node can reduce an übernetwork (above) that starts with 12 operating nodes to just four.Source: S.V. Buldyrev et al/Nature 2010, adapted byT. Dubé

“It’s as if someone threw a switch,” Stanley says. “But there is no switch.”

After tweaking the math and running some simulations, the researchers submitted a paper toNature. Since its publication, in 2010, more than 100 other papers have cited it.

Other teams have also found unexpected behavior in networks of networks. In 2009, D’Souza and a colleague showed that connecting a large portion of nodes in a network of networks takes fewer links than would be required for a similar single network. Other scientists have revealed that imposing travel restrictions may not reduce the spread of an epidemic as much as would be expected because of the interconnected nature of human mobility networks. And in 2008, Italian researchers reported that a power station shutdown led to a failure in the Internet communication network, causing the breakdown of more power stations and triggering an electrical blackout affecting much of Italy. In its Nature paper, the Boston group used this disaster as a real-world example to model how failures can cascade back and forth between networks.

What set the Nature paper apart from the others was that it offered a simple mathematical model to explain real-world phenomena. That finding meshed with others to give network-of-networks science a theoretical foundation.

“They have really figured out the framework of how to think about it,” says Albert-László Barabási of Northeastern University in Boston, who made seminal contributions to studies of single networks. “They came along and said, let me show how you calculate this and what are the consequences of coupling these networks.”

Since the discovery, the Boston cadre — along with a battalion of graduate students — has extended its framework to study the vulnerability of three or more interconnected systems. In another study, the researchers have found that terrorist-caused damage to an important power hub may differ from more arbitrary damage caused by, say, a rat chewing through an electrical wire.

Like a social scene in which all the popular kids hang out together, in some networks well-connected nodes are more likely to link up with other well-connected nodes. Stanley, grad student Di Zhou and colleagues have found that if one network in an interdependent system has this property, dubbed assortativity, then the whole system is more vulnerable to disturbance.

These early findings were unexpected based on studies of solo networks, leaving scientists wondering what other secrets networks of networks might hold. “There are many questions that appear immediately,” Havlin says.

It’s a small world

A similar burst of activity in network science occurred in 1998, after Cornell University’s Steven Strogatz and then-colleague Duncan Watts published a groundbreaking paper, also in Nature. Titled “Collective dynamics of ‘small-world’ networks,” it explained why the world seems so tiny.

At the time, “small-world phenomena” had already gained a degree of notoriety. In the 1960s, psychologist Stanley Milgram showed that a randomly selected person living in Nebraska could be connected via acquaintances to a target person in Massachusetts through just a few (typically six) other people. Students from Albright College in Reading, Pa., made the idea widely known in the mid-1990s when they invented a game known as Six Degrees of Kevin Bacon, based on the actor’s appearances in so many movies. With the links defined as coappearances in any single film, Bacon could supposedly be connected to any other Hollywood celebrity in no more than six steps. In the network of actors, moving from the node of Kevin Bacon to the node of, say, Hilary Swank would pass you over fewer than six films. (In fact, it’s hard to name an actor who is more than two or three degrees from Kevin Bacon. Try for yourself at www.oracleofbacon.org.)

ENLARGE

SLEEP SHIFTSView larger image | During the transition from deep to light sleep, networks in the body suddenly join up. Each small circle stands for a measurement of a bodily system, and the lines show which systems are acting in concert over a four-minute period. From an interacting networks perspective, deep sleep is quite distinct from light sleep, which more resembles waking.Source: A. Bashan et al/Nature Communications 2012, adapted by T. Dubé

Small-world, or Watts-Strogatz, networks exhibit two features: They are highly clustered, meaning the nodes clump together like cliques of middle school girls. And shortcuts connect those cliques, akin to a cheerleader who occasionally hangs out with a member of the nerdy group.

Much like the simple framework developed more recently by the Boston group, the Cornell duo’s findings had implications for how a network behaves. “Systems synchronize much faster, epidemics spread much more rapidly,” Strogatz says. “In the case of game theory — where you have people, companies, countries playing prisoner’s dilemma — we were able to show that the small-world structure would make a difference in how that game evolved.”

But what really launched the Watts-Strogatz revolution was the way features in their model matched multiple real-world networks. An electric power grid, actors connected to Kevin Bacon and the nerve cells in a worm were all in on a secret that scientists had only just uncovered.

“The legacy is the introduction of the idea of looking at the comparative anatomy of networks,” Strogatz says. “What we were able to show was there were universal principles that applied to different networks that scientifically were completely unrelated but mathematically were following the same architectural principles.”

Almost immediately, researchers from diverse disciplines abandoned existing projects and redirected their intellectual firepower to develop network math for proteins, planes, power stations and pathogens. Friends, film actors and financial players also got their fair share of attention. Over the last dozen years or so, this flood of effort has led to a better understanding of how nodes of all types come together to form networks and what happens when one gets plucked out.

But work so far has focused mostly on the comparative anatomy of single networks. Surprising behavior uncovered in networks of networks presents a new and still puzzling question: Do the übernetworks behind blackouts, stock market crashes, transportation gridlock and even sudden deteriorations in health — a particular worry of Stanley’s — conceal a deeper shared anatomy?

Stanley believes they might. When he walks down the stairs, he has a habit of holding the railing. Breaking a hip, he says, could trigger a series of disconnections in his body’s network of networks.

It’s widely known that an elderly person who fractures a hip faces a greatly increased chance of dying within the next year, even if repair surgery is successful. What’s not yet clear, though, is whether the cascading behavior outlined by the Boston team is behind this abrupt decline in health. An answer may emerge as scientists find out what networks of networks in the body, in finance and in nature have in common.

Plumbing networked networks

Of all the world’s network-of-networks problems, climate change is one of the most challenging to untangle. How much global temperatures will increase over the next century depends on patterns of behavior in the air, the ocean, the land and among all the organisms living on the planet. Natural cycles are influenced by human-driven networks — the economics governing greenhouse gas emissions, the political drive behind energy alternatives and the social recognition of global warming as a problem in need of a solution.

In a recent study, physicist Jonathan Donges of Germany’s Potsdam Institute for Climate Impact Research plotted hundreds of thousands of data points related to air pressure to study networks in just the atmosphere. By tracking how the data changed over time, he identified a series of horizontal networks that wrap around the Earth, layering on top of one another like Russian nesting dolls. The Arctic serves as the link, acting as a sort of atmospheric border patrol that controls mingling between the horizontal layers, he and colleagues reported last year in European Physical Journal B.

“The Arctic seems to be important in coupling atmospheric dynamics on the surface and in higher layers up in the atmosphere,” Donges says.

ENLARGE

SAVING NODESView larger image | In a simulation of coupled networks in Italy (circles represent a power grid, diamonds a communications network), protecting just four nodes made a system less vulnerable. At left, all communications servers are coupled to the power grid; at right, four are decoupled. Colors show the probability that a node fails after 14 servers fail.Source: C.M. Schneider et al/arxiv.org 2011; Map: Geoatlas/graphi-ogre, adapted by T. Dubé

If networks of air molecules sound complicated, consider the network of goings-on in your cells, where the nodes and their links come in different forms. Within each cell of your body there is a constant dance among DNA, RNA and proteins. DNA encodes networks of 20,000-plus genes; at any one time many are being decoded into complementary strands of messenger RNA, which form their own networks as they guide the production of proteins. Those proteins can do-si-do with other proteins, interacting within their own network in a very physical way, or can connect with other networks by pulling genes onto or off the dance floor.

“You cannot look at these networks in isolation,” says Tom Michoel of the University of Edinburgh’s Roslin Institute. “Everything there is interconnected.”

Michoel tries to understand networked networks by studying small-scale patterns that show up more often than expected in a particular system, and thus say something about its overall functioning. Consider a common workplace pattern, in which an intermediary can serve as a point of contact between a boss and an employee. Michoel found many examples of a similar pattern in yeast cells. One of two linked-up networks included interactions that regulated gene activity, in which a protein (the boss) chemically tags a gene that codes for another protein (the intermediary). The other contained more direct protein-protein interactions (between the intermediary and an employee).

By looking at how the small-scale patterns clustered and overlapped, Michoel discerned that one boss interacts with one intermediary but that each intermediary represents many employees, sort of like a union spokesperson acting on behalf of union members. Without the übernetwork analysis, there was no way to understand the distinct roles of bosses and intermediaries, Michoel says. Important large-scale interactions would have remained hidden.

Exposing unknown interactions is not the only issue. Strengths of the connections linking networks are also important. The volume of buses traveling a route, for example, may ramp up during rush hour. Or in your social networks, you may see a coworker almost every day but a high school friend just once a year.

In his investigation of sleep cycles, Ivanov showed that changing how tightly two networks are coupled can affect physiology. Links don’t have to be newly created or severed to matter.

A former student of Stanley’s, Ivanov spent more than a decade collecting data on heart rate, breathing rate, muscle tone and eye movement to find out how the body’s networks interact during the various stages of sleep. Much like Donges’ approach with the atmosphere, Ivanov inferred links and the nature of those links by analyzing how measurable markers from each system parallel each other in time. His team found out how the networks hook and unhook, but also how those hookups vary.

Ivanov believes his problem, as well as other network-of-networks puzzles that show up in the body, is a bit more challenging than the ideal scenario tackled by Stanley and Havlin’s group.

“We could have failure even if a particular link between nodes doesn’t disappear,” Ivanov says. “We could still have all links present, but with different strengths, and the system can come to arrest.”

Such considerations inject further complications into the emerging field, suggesting just how much more there is to be learned.

Physicist and computational scientist Alessandro Vespignani of Northeastern University, who studies epidemics and other spreading processes in networks, compares the current state of knowledge to what the Romans knew about Africa 2,000 years ago. The Romans had a pretty good map of the world, but they didn’t journey deep into Africa. “There are lions, that was the only information,” Vespignani says.

Right now, scientists have a map of the future of network science, and networks of networks offer an exciting new area, but people are only beginning to travel there. “We need to define new mathematical tools,” Vespignani says. “We need to gather a lot of data. We need to do the exploratory work to really chart the territory.”

Linked resilience

D’Souza of UC Davis has made early strides in mapping a landscape different from the one where the Boston team planted its flag. When she and colleagues became interested in networks of networks, they focused on success rather than failure.

“We weren’t looking in the realm of something so catastrophic that the node goes away forever,” D’Souza says. “We are more interested in a dynamical thing that will keep the network still working.”

In a recent study, her team looked at how two linked power grids might interact, say a grid that covers much of the eastern United States and another that services the West. She constructed links between the grids that are similar to the links between individual nodes within each grid: The nodes interact, but the survival of one doesn’t depend entirely on the other. She calls them connectivity links.

Each node in each network was assigned a capacity, akin to the load a power plant can handle before it becomes overwhelmed by that demand. Links represent ways for a power plant to hand off its load. If a plant can’t meet a given demand, it can pass some on to another linked power plant, which can pass it on to another and then another. As the researchers gradually add demand, like sand being added to a pile, they look for “avalanches” of load. Load will take off running across nodes the way that sand added to a pile will eventually start tumbling down the sides. Fittingly, network scientists call these avalanches “sandpile cascades.”

In analyzing the mathematics of these cascades, D’Souza and her colleagues showed that having two networks can help take some of the burden off a single network, minimizing the threat of large avalanches. “A little bit of coupling was incredibly beneficial,” D’Souza says. “The second network acted as a reservoir where the first could shed some load.”

But add too many connections between the networks and larger avalanches become possible, the team reported in March in theProceedings of the National Academy of Sciences.

Connected power grids are a good example of networks that cooperate, says D’Souza. Adding power lines to one network may boost the transmitting capabilities of the second. But such networks may also turn competitive, if, for example, an improvement in one puts the other at an energy-supplying disadvantage.

D’Souza’s efforts have highlighted other flavors that networks of networks can come in, too. In your social web, you probably have overlapping networks, in which you simultaneously belong to a friend group and a family group. Or there may be networks in which the nodes are the same, but the links differ; think of banks that borrow money from each other in one network and invest in each other in another.

Then there are systems in which one network is actually built on top of another, the way hyperlinked Web pages sit atop electric, fiber-optic and wireless communication channels. These “overlay networks” also show up in the brain. Its physical architecture, the very anatomy of the brain, provides the structural network from which function — thought, memory, reason — emerges.

“Functional activity for me is more of a fleeting, fast-changing, difficult to characterize and for that reason much more ethereal construct in some ways,” says Olaf Sporns of Indiana University. Sporns is a major player in the Human Connectome Project, which seeks to understand how all the nerve cells in the brain interact. “The structure of the brain, the anatomy is something that, if we have good enough instruments, we can measure,” he says. “It is actual wiring.”

Brain scientists agree that the functional network must somehow be rooted in the structural network. But exactly how one gives rise to the other isn’t clear. What’s more, the networks feed off each other, adding the element of evolution to an already hard-to-follow labyrinth of nodes and links. The architecture sculpts, constrains and molds the function, and the function leaves experiential traces on the structure over time.

Sporns proposes that these dynamics represent a constant balancing act between the wiring cost in the anatomical network and the desire for efficient outcomes in the functional network. “This process of negotiating, and renegotiating trade-offs,” Sporns and a colleague wrote in May in Nature Reviews Neuroscience, “continues over long (decades) and short (millisecond) timescales as brain networks evolve, grow and adapt to changing cognitive demands.”

As the brain changes in time, so does the behavior of the body — influencing all the larger networks in which a person plays a part.

That can expand the puzzles facing scientists. Questions extend to how a network of networks reacts to what’s happening within, and how people adapt to the system, says Vespignani. “If I know there is a blackout, I will do certain things. If I know there is an economic crisis, I will go to the bank and ask to get all my money back. If there is an epidemic, I will stay home.”

Some scientists speculate that currently available theoretical approaches for übernetworks may be too simplistic to be useful. One economist went so far as to warn of the dangers of applying the Boston team’s results too widely, assuming everything is a nail just because you have a hammer. Most researchers, though, offer a more measured take.

Toward better systems

While physicists and mathematicians strive for simplicity, engineers like Leonardo Dueñas-Osorio of Rice University favor a more data-driven simulation approach, enriching tools from network science with realities from physical systems.

“When you have a complex problem, abstractions of the analytical kind can help you narrow down where to focus,” Dueñas-Osorio says. “Then you need to add refinement, make things more realistic.”

Both approaches — theoretical and simulation-based — have some real-world payoff. With equations that are mathematically tractable, “you can do a lot of insightful derivations,” he says. “Those are very valuable, but sometimes you only achieve those at the expense of simplifying the systems.”

Dueñas-Osorio and others instead build network models that pin every node into its proper geographic location and give each one a different likelihood of failing, depending on factors such as its age or activity level. Many of these researchers get their data on the ground.

During a trip to Chile after a 2010 earthquake there, Dueñas-Osorio collected information about what transformers failed and what pipes broke. He talked to utility companies to track service interruptions. “This information allows us to get a sense of how strong the connections are between systems,” he says.

Such data also reveal ways in which systems are suboptimal and could be improved. Some areas hard-hit by natural disasters don’t have enough connections — with, for example, only one power plant supporting a pumping station.

Efforts by Havlin and colleagues have yielded other tips for designing better systems. Selectively choosing which nodes in one network to keep independent from the second network can prevent “poof” moments. Looking back to the blackout in Italy, the researchers found that they could defend the system by decoupling just four communications servers. “Here, we have some hope to make a system more robust,” Havlin says.

This promise is what piques the interest of governments and other agencies with money to fund deeper explorations of network-of-networks problems. It’s probably what attracted the attention of the Defense Threat Reduction Agency in the first place. Others outside the United States are also onboard. The European Union is spending millions of euros on Multiplex, putting together an all-star network science team to create a solid theoretical foundation for interacting networks. And an Italian-funded project, called Crisis Lab, will receive 9 million euros over three years to evaluate risk in real-world crises, with a focus on interdependencies among power grids, telecommunications systems and other critical infrastructures.

Eventually, Dueñas-Osorio envisions that a set of guidelines will emerge not just for how to simulate and study networks of networks, but also for how to best link networks up to begin with. The United States, along with other countries, have rules for designing independent systems, he notes. There are minimum requirements for constructing buildings and bridges. But no one says how networks of networks should come together.

Ivanov hopes to develop a similar rulebook for the human body that shows actual designs. Many doctors’ offices display diagrams of the body that outline the different systems — the circulatory system, the respiratory system, the musculoskeletal system. But no diagrams show how those systems interact with one another, and that knowledge might be just as crucial for fighting disease.

As more data come in, the goals of those working on human-built systems and natural systems may merge. More important than whether biological, social and technological systems exhibit similar mathematical properties may be whether they should. Can people design better systems by learning from the systems that exist in nature?

Sporns predicts the answer could be yes. “These systems naturally, just by virtue of being here, actually having survived, have been optimized to a certain extent,” he says. “They are existing proof that you can have complex networks that are structurally buildable and realizable and sustainable, at the same time dynamically competent, resilient against perturbations and evolvable.”

How to maximize sustainability, resilience and evolvability in networks of networks are questions that are still largely open. Geneticists seek answers in the genes, physiologists in the broader body and ecologists in the interactions that govern all living things. Connections forming among these growing webs of knowledge, as well as with engineers’ models and theorists’ frameworks, will provide much-needed fuel for a burgeoning intellectual endeavor.

If the efforts prevail, one day preventing blackouts, interrupting epidemics and handling a complicated commute may be as easy as waking up in the morning.

---

Network catastrophes

While researchers have not yet analyzed them in detail, some recent real-world incidents highlight what can happen if disaster strikes within a network of networks.

© AP, Corbis

India blackout, 2012
Power grids collapsed in India earlier this year, leaving hundreds of millions of people without power. The outage triggered transportation failures as local and long-distance trains stopped running. Some sources speculate that the grid was overloaded because a weak monsoon had farmers using more electricity to pump water to fields.

Stocktrek Images/Richard Roscoe/getty images

Eyjafjallajökull eruption, 2010
Iceland’s Eyjafjallajökull volcano erupted in 2010, spewing ash that shut down air travel throughout Europe. But travelers weren’t the only ones affected: Manufacturers, medical suppliers and crop producers couldn’t move their goods. The effects of the grounding rippled into the fuel, hotel and car rental industries.

Eneas De Troya/flickr

Swine flu pandemic, 2009
When a swine flu outbreak hit Mexico in 2009, officials responded with travel bans and other control measures. But a drop in international air traffic to and from Mexico didn’t prevent a pandemic. Viruses travel through a complex global mobility über­network that is made up of long-distance flights as well as local commutes, and interacts with social and economic networks.

Science News

Press12sciencenews Interdependentnetworks

Lire plus de publications sur Calaméo