Mostrando entradas con la etiqueta bicomponente. Mostrar todas las entradas
Mostrando entradas con la etiqueta bicomponente. Mostrar todas las entradas

viernes, 8 de junio de 2018

Redes, historia y complejidad

Redes e historia

Peter Bearman,
Instituto de Investigación y Política Social y Económica, Universidad de Columbia, Nueva York, NY 

James Moody, y 
Departamento de Sociología, Universidad Estatal de Ohio, Columbus, OH 
Robert Faris
Departamento de Sociología, Universidad de Carolina del Norte en Chapel Hill


Fuente

Los eventos y las estructuras de eventos componen los elementos constitutivos de la historia. Para construir relatos históricos de secuencias de eventos, los historiadores tienen que hacer casos. Este artículo propone un método para encajonar eventos históricos. Ilustramos la estrategia analítica al considerar una compleja población de eventos interrelacionados que conforman una narrativa de revolución, contrarrevolución y revolución en una pequeña aldea en China. Se discuten las implicaciones para la metodología de las ciencias sociales históricas.


En contraste con los argumentos excesivamente deterministas sobre las causas fundamentales, las narrativas imaginativas de la cate nación fortuita de los eventos contingentes como reveladores del proceso histórico son la moda actual en la ciencia social histórica. Al servicio de tales narrativas, las imágenes de red a menudo se despliegan para describir las vías contingentes aparentemente frágiles a través de las cuales ocurren resultados históricos complejos. A primera vista, las redes parecen proporcionar una metáfora apropiada para el azar y la contingencia, pero este no es el caso. En cambio, la consideración de las estructuras de red en el contexto histórico sugiere roles limitados para la contingencia en la dinámica de eventos. En consecuencia, las estructuras de eventos históricos que aparecen como casos en la historia de las ciencias sociales son mucho más sólidas de lo que se suele imaginar. Sin embargo, algunos eventos pueden jugar papeles más importantes que otros en la configuración de la historia, y el problema de la explicación histórica se basa en desarrollar una metodología para modelar estructuras complejas de eventos que revele qué eventos desempeñan papeles críticos en los resultados históricos. Tal metodología es la preocupación de este artículo en el cual proponemos que la aplicación de modelos de red a casos históricos puede proporcionar respuestas a preguntas tan fundamentales como: ¿cuándo, si alguna vez, los eventos únicos cambian la historia? ¿Qué significan las cosas en el contexto histórico y cómo definimos los casos en un contexto histórico?
El argumento que proponemos es simple. El significado de un evento depende de su posición en una secuencia de eventos interrelacionados, lo que los historiadores llaman un caso. En consecuencia, para quienes estén interesados ​​en lo que significan los eventos, las secuencias de eventos de cobertura es el problema más fundamental que enfrentan los historiadores. En la Sección 2, proponemos una solución, que explota los desarrollos en el análisis de redes sociales que son relevantes para el análisis de estructuras complejas de eventos. Nos enfocamos
sobre las similitudes entre las estructuras sociales y las estructuras de eventos que apuntan a la aplicabilidad de los métodos de red para el análisis de datos históricos. Estas similitudes también sugieren que los procesos históricos pueden ser bastante robustos a la perturbación.El encapsulamiento (casing), que está limitando el comienzo y el final de las secuencias de eventos, no es diferente de un problema en el análisis estructural: cómo especificar un límite en una red. El problema para las ciencias sociales históricas implica generar una población de eventos. Las estrategias para generar una población de eventos en contextos históricos se describen brevemente en la Sección 3. En la Sección 4, ilustramos el método con respecto a un único caso complejo; revolución, contrarrevolución y revolución en una aldea china durante el período de 1920 a 1950. Explotamos técnicas de modelado para redes narrativas [1], para transformar las narrativas en redes. Las operaciones en estas redes proporcionan la base para nuestros análisis, en los que "probamos" nuestra solución de creación de un caso es simulando el futuro. Finalmente, consideramos si los eventos se pueden organizar de manera significativa con respecto a su probabilidad de dar forma al historial y describir cómo dicha matriz podría contribuir a un nuevo método histórico. En la conclusión, indicamos cómo el enfoque propuesto aquí podría alterar nuestro pensamiento sobre la naturaleza del azar en la configuración de los resultados, el registro de casos que los historiadores consideran, y la historia en general.

1. EL PROBLEMA DEL CREACIÓN DE UN CASO

El encapsulamiento está necesariamente implicado en la simple tarea de construir una narración histórica. Del mismo modo, la carcasa es un requisito previo para el significado. Precisamente porque es tan importante, la creación de un caso se ve como una cuestión de discernimiento y el juicio que surge de tal idea. Para la mayoría de los historiadores, cómo se crea un caso de estudio es un logro esencialmente artístico. Aquí proponemos una estrategia para cubrir eventos históricos que dependen menos del arte y más del método. No es sorprendente que este no sea un problema simple. Una gran complicación surge del futuro. Debido a que el significado de un evento depende de su posición en una secuencia de eventos interrelacionados, es necesariamente imposible fijar para siempre el significado de un evento, es decir, fijar para siempre el final y el comienzo de una secuencia de eventos, porque el futuro los eventos pueden activarse, es decir, dibujar en una nueva secuencia de eventos, eventos pasados. No podemos encontrar consuelo en la idea de que solo una cierta clase de eventos futuros podría tener ese papel, porque la ocurrencia futura podría ser tan trascendental como la toma de la Bastilla o tan trivial como el descubrimiento de un diario perdido. En este último caso, un elemento del arte de los historiadores, el descubrimiento (de nuevos eventos o relaciones entre eventos) tiene la capacidad de cambiar los comienzos y los fines, y por lo tanto el significado específico de los eventos.El hecho de que sea posible cambiar el significado de los eventos no significa que los historiadores deban abandonar el intento de desarrollar una estrategia para encauzar secuencias de eventos. Primero, aunque algunos eventos pueden activarse por descubrimiento o por el futuro, la mayoría nunca es tan afortunado. Lo que sea que significa que la mayoría de los eventos se han corregido completamente dentro de una única secuencia de eventos específicos, se ha fijado en secuencias de eventos más grandes y complejas. Dicho de otra manera, ni el descubrimiento de nuevos eventos ni sucesos futuros desconocidos pueden alterar en modo alguno la secuencia de eventos en los que están incrustados los eventos "muertos" y, en consecuencia, su significado también es fijo. Sin embargo, algunos eventos ya se han incorporado, y algunos más, en nuevas secuencias de eventos luego del descubrimiento o la ocurrencia de eventos en el futuro. En consecuencia, podemos imaginar una distribución de eventos, definida con respecto a su probabilidad de activación, "fluidez de significado" o susceptibilidad a estar condicionados por el futuro. Si podemos ordenar eventos con respecto a su probabilidad de estar condicionados por el futuro, se deduce que las secuencias de eventos también se caracterizan mediante dicha distribución, y asimismo, los conglomerados de secuencias de eventos densamente interrelacionadas (lo que definimos como "casos") también están sujetos a la misma distribución, con algunos más probables de cambiar que otros. Esto tiene sentido intuitivo y lo confirma el juicio que usan los historiadores. En términos simples, algunos eventos, secuencias de eventos y casos están muertos.Algunos eventos y secuencias de eventos están sujetos a una revisión radical. Podemos hablar con confianza sobre el significado de los eventos muertos. Nuestra confianza recae en aquellos que probablemente estén vivos. El problema práctico implica saber qué eventos, secuencias de eventos y casos son calientes y cuáles no.

Teoría fuerte e historia delgada

Cuanto más sólida es la teoría, más delgada es la historia, una perogrullada que se revela más claramente cuando uno se propone representar la historia como una red de eventos conectados por flujos de causalidad. Las descripciones históricas de los acontecimientos, especialmente las que ofrecen los historiadores de las ciencias sociales, tienden a tener una apariencia uniforme. Comienzan con un grupo relativamente denso de eventos interrelacionados. Estos, típicamente eventos de nivel macro (por ejemplo, crisis fiscal, crisis agraria, crisis de confianza / legitimidad) fluyen hacia una estrecha corriente de eventos específicos de micro nivel. Una vía delgada (escasamente conectada con muy poca redundancia, pocos ciclos, etc.) se mueve a través del tiempo, induciendo finalmente un evento fundamental que se caracteriza por una gran diferencia, impactando múltiples secuencias de eventos y proporcionando (típicamente) el límite del "caso".
La Figura 1 es un grafo de red de una narración histórica estándar, en este caso, la historia de la revolución y la contrarrevolución en una aldea china.



En la Figura 1, los nodos son eventos específicos que tuvieron lugar, y las flechas son enlaces entre eventos (causales o lógicos) implícitos o explícitos en la narración. El tiempo se mueve, en general, de izquierda a derecha. Los eventos pivotales son aquellos en el centro del gráfico, delimitados por el principio y el final de la narrativa, que componen el caso. La narración es muy delgada como una red, solo escasamente conectada. Esto implica que la teoría que dio lugar a la historia específica es fuerte, porque la teoría implica negar datos. Los relatos narrativos finos son el producto de teorías específicas que dirigen al historiador a identificar algunos eventos como sobresalientes y a negar otros eventos como no destacados. La historia implica la selección de eventos para interconectarse en una narrativa. Tener una teoría requiere que sepamos el final de la historia para dirigir la selección de eventos. Pero esto es un problema ¿Cómo vamos a saber el principio y el final si solo nos dicen lo que significan los eventos?


En lugar de centrarse en la selección de eventos, ahora consideramos que la teoría implícita de la historia se caracteriza por líneas finas sin vías independientes que conectan causas y eventos. Una ironía es que con una sólida teoría, pronto nos vemos obligados a contemplar los efectos de la mantequilla como historia de conducción. En la narrativa de la Figura 1, hay muchos puntos críticos a través de los cuales solo fluye un camino. Los efectos de la manteca se pronunciarían si una pequeña perturbación tiene la consecuencia de eliminar (o agregar) un nodo o línea entre los eventos. Si el evento o el enlace no existieran, ¿podríamos realmente imaginar que la revolución no ocurriría? El problema no es la parsimonia de la explicación per se. Muchas cuentas parsimoniosas que atraviesan el mismo campo desde diferentes puntos finales pueden generar poblaciones de estructuras de eventos densas. El problema es que hay muy pocos conjuntos de ojos. El truco metodológico básico es integrar puntos de vista desde múltiples perspectivas.

2. REDES SOCIALES Y CIENCIAS SOCIALES HISTÓRICAS

Durante la última década, se publicaron artículos influyentes que se basan en el análisis de redes, sobre temas históricos sustantivamente importantes, desde la organización de los Medici hasta la construcción del estado otomano y más allá de la Comuna de París [2-7]. Las imágenes y los métodos de red proporcionan información sobre mecanismos y procesos específicos al enfocarse en individuos de rango medio, sobre individuos aislados, pero por debajo de formaciones sociales enteras. Estos estudios han proporcionado una nueva percepción del papel que desempeñan las relaciones sociales en la estructuración y el bloqueo de la acción y, de manera más abstracta, han proporcionado un nuevo lenguaje para describir los niveles densos, a menudo anidados y cíclicos, interrelacionados de relaciones sociales, construcciones simbólicas, y prácticas (vistas como flujos en una red) que componen estructuras sociales tangibles en contextos históricos y contemporáneos.
Estos notables logros no han llegado sin costos. La reconstrucción detallada de la estructura social, definida con respecto al patrón en múltiples relaciones, necesaria para el análisis de red a menudo ha conducido a un mayor compromiso con explicaciones muy particulares, y una renuencia a abstraer la estructura en sí misma de contextos específicos. En consecuencia, gran parte del trabajo en ciencias sociales históricas que utiliza redes parece prosopográfico: un enfoque de datos relacionales que es limitado porque no puede proporcionar un andamiaje analítico para una comparación significativa entre casos con respecto a parámetros estructurales interpretables. Por otro lado, el énfasis en el contexto ha sido un paliativo útil para contrarrestar una tendencia más inquietante en la historia de las ciencias sociales, la idea de que los modelos de elección racional pueden servir para una función explicativa, como frente a la función heurística. Es irónico que un método (análisis de red estructural) diseñado para la comparación entre contextos celebra la particularidad como la principal barrera para una teoría que niega la relevancia de todos los contextos (a pesar de la protesta en sentido contrario). [Los modeladores de opciones racionales lo negarían al señalar cómo sus modelos incorporan el contexto (como valores, bienes, costos, etc.) en los marcos de decisión de los actores. Pero el hecho de que todos los contextos son igualmente fáciles de integrar en el modelo le quita el fantasma.]


Igualmente irónico es el extraño matrimonio entre teóricos relacionales y de contingencia. Al igual que con las redes, la contingencia ha sido un "descubrimiento" importante para los científicos sociales históricos y actualmente sirve como el principal desafío para los modelos más antiguos en las ciencias sociales históricas que se centran en los determinantes a nivel macro del cambio social sin suficiente atención (social, relacional, mecanismos simbólicos, etc.) Las principales metáforas se basan en el hecho de que las observaciones de redes sociales, como las observaciones históricas, están ligadas e interdependientes. En las redes sociales y en la historia, existe la sensación de que el hecho de la interdependencia significa que el cambio sutil puede concatenarse violentamente a través de un sistema y acumularse en cambios históricos y / o estructurales imprevistos [8]. La idea es atractiva, pero incorrecta.

Las estructuras sociales tangibles se basan y dependen de la fluidez local y la interrupción de la estabilidad [9,10]. (Solo podemos observar estructuras sociales que son robustas. Las estructuras sociales no sólidas no duran lo suficiente para observar. Un idioma popular explica lo que fortalece las estructuras. El amor, como un árbol, puede resistir mejor las tormentas si se dobla).
Las estructuras robustas absorben la fluidez en el micronivel en virtud de características estructurales específicas que "explotan" la interdependencia. Los datos de red en una población son localmente densos, pero globalmente escasos, a menudo cíclicos, anudados y caracterizados por una redundancia de vínculos. (Hay muchas más similitudes. Una similitud, que explotamos posteriormente, es que las características de las redes sociales globales pueden determinarse de manera significativa mediante el muestreo de redes locales, un argumento que a menudo está implícito en las narrativas históricas). Las estructuras sociales comparten estas características con estructuras. Además de los revisionistas radicales, la mayoría de los historiadores también estarían de acuerdo en que los datos históricos muestran una redundancia vinculada, por ejemplo, la idea de que existen múltiples vías independientes a través de las cuales fluyen los efectos causales. Los ciclos en los datos históricos aparecen cuando eventos futuros condicionan eventos pasados, sacando de las relaciones nuevas pasadas a otros eventos. En las redes sociales, la densidad local, el nudo, la redundancia y la ciclicidad dan lugar a las complejas estructuras sociales que organizan el mundo relacional.
Aunque analíticamente separables, se relacionan entre sí. La ciclicidad da lugar a la redundancia, la redundancia da lugar a la densidad local y la densidad da lugar a nudos, generando propiedades de cohesión a nivel macro a partir de una serie de microprocesos independientes. Nuestro interés aquí es mostrar que es lo mismo con las estructuras de eventos. Demostramos que las estructuras de eventos reales que surgen de los datos históricos tienen una estructura similar, donde el orden aparece en el nivel agregado, un producto de la fluidez a nivel micro. En consecuencia, las representaciones de estructuras de eventos como narraciones delgadas y, en consecuencia, sujetas a los "efectos de la mantequilla" se equivocan en gran medida.


3. GENERAR UNA POBLACIÓN DE EVENTOS DE NARRATIVAS INTERCALANTES

En los relatos históricos convencionales, el fin determina el comienzo y, por lo tanto, los elementos que deben ordenarse en la narración. Para el caso de un evento, que puede estar en múltiples subsecuencias interrelacionadas, necesitamos una población de eventos alrededor de la cual podamos dibujar un principio y un final. Dos estrategias distintas para construir una población de eventos son posibles, muestras de bola de nieve de corto alcance y narrativas intercalares. La idea del muestreo de bolas de nieve de corto recorrido es comenzar con una gran muestra de eventos y utilizar técnicas de muestreo de bola de nieve para generar una población de eventos. Se puede implementar una variedad de estrategias de muestreo para redes [ver 11,12 para primeros pasos], para construir poblaciones de eventos históricos. Aquí, ilustramos la segunda estrategia, narraciones intercalares, para demostrar nuestro método para la creación de un caso. Los datos que usamos son historias de vida. Al igual que los relatos históricos, las historias de vida presuponen un final (un punto de vista). Contar historias implica organizar elementos seleccionados de un rico e inagotable plato de bienes culturales -personas, lugares, cosas, eventos, ideas, etc.- en secuencias narrativas que están orientadas hacia un fin particular, de tal manera que sea una trama . El final le permite al autor seleccionar de un mar interminable de eventos solo aquellos eventos que él o ella ve como importantes (sobre la base de una teoría) para que la historia sea revelada. En contraste con las historias formales, las historias de vida tienen características que las hacen ideales para nuestro objetivo, la más importante de las cuales es una estructura teórica débil.
Para ilustrar utilizamos 14 historias de vida de pobladores chinos cuyas experiencias abarcaron la revuelta agraria en el campo, la contrarrevolución, una revolución y luego la codificación de un régimen revolucionario en un marco institucional. El contexto es un pequeño pueblo en el norte de China. Las historias están tomadas de Report from a Chinese Village [13]. El libro contiene una colección de historias de vida de los aldeanos de la aldea de Liu Ling, en el norte de China, cerca de Yenan. Myrdal realizó entrevistas allí en 1961. La Figura 2 proporciona una representación gráfica de dos de las historias de vida que usamos.
Al tratar los eventos como nodos y las relaciones entre los eventos como arcos, las secuencias narrativas de los elementos se transforman en redes. Al representar las secuencias de eventos complejos como redes, podemos observar y medir las características estructurales de las narraciones que de otra manera serían difíciles de ver.
En estos gráficos, los elementos de la historia de la vida narrativa se tratan como nodos que están conectados por cláusulas narrativas, representadas por arcos. Una cláusula narrativa es una cláusula que está ordenada temporalmente de tal forma que moverla implica cambiar el significado de la subsecuencia en la que está incrustada. Las cláusulas libres, por el contrario, se pueden mover sin cambiar el significado de una subsecuencia o la narración como un todo [1,14,15]. Codificamos solo cláusulas narrativas como arcos, vinculando un evento (o elemento) a otro a lo largo del tiempo. Los elementos (nodos) de las narrativas son heterogéneos en alcance y rango, desde el saludo a las tropas conquistadoras con té, hasta una batalla escenificada entre el KMT y los comunistas. El evento anterior ató a los hijos de los terratenientes al KMT; este último resultó en una derrota imaginaria de los comunistas. La idea detrás de este espejismo era engañar al liderazgo del KMT para que pensara que los comunistas habían sido aplastados por las fuerzas locales del KMT para que ambas fuerzas pudieran resistir a los japoneses.



En la Figura 2, el tiempo narrativo se mueve de la parte superior a la parte inferior de la página. El eje izquierda-derecha no es substancialmente interpretable. La profundidad narrativa está representada por la cantidad de arcos que conectan eventos. En esta instancia, por ejemplo, los dos eventos en la parte inferior de la Figura 2B tienen una profundidad narrativa de 17, es decir, hay 17 pasos desde la parte inferior hasta un evento inicial en la parte superior del gráfico. Una característica de estas historias es que son estructuralmente muy diferentes de las historias de los historiadores profesionales.
Tienen muchos elementos desconectados. Los eventos se mencionan, pero no necesariamente están vinculados. A través de subsecuencias, es imposible caminar desde los eventos tempranos a eventos posteriores sin interrupción. No es sorprendente que las historias de vida sean más densas y más complejas que las narrativas históricas convencionales. Tienden a tener un flujo narrativo profundo. Son más complejos porque la gente común no está entrenada como teórica. Por lo tanto, tienen problemas para negar los datos. Las historias de vida con las que trabajamos muestran heterogeneidad. Algunas cuentas son delgadas (Figura 2A), mientras que otras son intrincadas (Figura 2B). Cada una de estas historias tiene un punto final diferente. Los narradores están parados en diferentes lugares. El final de las historias implica diferentes resultados.
El hecho de que se encuentren en diferentes lugares dirige la selección de los elementos que eligen representar para su fin. Por analogía, uno podría considerar un conjunto de cuentas profesionales de la misma secuencia de eventos, cada uno de pie en una posición diferente. Todas las historias cubren los mismos eventos de aldea y aldea en el mismo tiempo, y, en consecuencia, el campo que atraviesan y los eventos a los que se refieren, se superponen considerablemente. Explotamos esta superposición intercalando historias para generar una población de eventos interrelacionados, lo que proporciona una nueva estructura de datos y, en consecuencia, señala nuevas estrategias para el análisis. Estas nuevas instrucciones se recogen a continuación en la Sección 4.


4. HACER Y PROBAR UN CASO

Entre 1920 y 1950, China se transformó. La reforma, la revolución y la guerra sacudieron el campo. Nuestros datos surgen de una de las miles de aldeas en el norte de China. Son sobre los eventos en este pueblo y su conexión con eventos lejanos que ocurren en otros pueblos y ciudades y países, cuyo carácter y contexto probablemente era inimaginable para los aldeanos que vivían en Liu Ling. Nuestro problema es desarrollar un método para el caso de secuencias de eventos interrelacionados. Para presentar un caso, primero necesitamos una población de eventos y necesitamos información sobre su relación. El segundo paso es dibujar un límite en los nodos en el gráfico. El problema (y la solución) se conoce como el problema de especificación de límites [16]. Basándonos en una vieja tradición en la literatura de las redes sociales, podemos aislar los casos al definir una partición en la población de eventos.Sin embargo, las técnicas de agrupamiento estándar no son apropiadas para nuestro problema, ya que los arcos que conectan regiones densas de un gráfico (nodos puente) podrían desempeñar un papel importante en la secuencia narrativa que estamos tratando de capturar. En cambio, adoptamos una nueva estrategia, que es identificar todos los bicomponentes en la población [17]. Un componente de un gráfico es un subgrafo conectado máximo. Un subgráfo máximo es uno que no puede hacerse más grande y aún conserva la propiedad de que hay una ruta entre todos los pares de nodos en el subgráfico y que no hay una ruta entre un nodo en el componente y un nodo que no está en el componente. Un bicomponente es un componente que tiene la propiedad de que todos los nodos están conectados por al menos dos caminos independientes diferentes y que la adición de un nodo requiere que esté conectado a dos nodos en el subgráfico. La idea central es que un caso, visto como un conjunto de eventos interconectados producidos por múltiples narraciones intercaladas debe tener la propiedad de al menos un bicomponente. Un bicomponente no es necesariamente un caso. Es un candidato para un caso. Definimos los casos como bicomponentes que son robustos para el descubrimiento o la activación futura. La figura 3 informa todos los eventos mencionados en las 14 historias de los aldeanos chinos con los que trabajamos, intercalados para formar un solo gráfico. Se mencionan casi 2000 eventos únicos, cada evento está representado por un círculo. Los eventos que están en más de una narrativa están sombreados. El tiempo narrativo se mueve desde la parte superior a la parte inferior de la página. En algunas regiones del gráfico, donde los eventos y sus relaciones son especialmente densos, los arcos son invisibles. Los eventos que están vinculados entre sí por arcos en estas regiones densas parecen superponerse en el gráfico. Los eventos al lado izquierdo de la figura están incrustados en secuencias de eventos que no están vinculadas a eventos en el lado derecho de la figura.



Esta es nuestra población de eventos. Por supuesto, hay millones de eventos no presentes. Podrían pertenecer a alguna otra historia pero no a esta historia. Pero algunos de los eventos que están presentes parecen que tampoco pertenecen a esta historia; por ejemplo, ninguna ruta los conecta a otros eventos.
Los happenings sin relaciones son solo acontecimientos. Las relaciones que tienen con otros eventos que no están en nuestra población pueden hacerlos parte de la historia, pero no la historia del caso en el que estamos trabajando. La figura 4 identifica y representa el componente principal. Tenga en cuenta que hemos pasado de los eventos de 1995, muchos de los cuales no estaban relacionados con ningún otro evento, a un conjunto más pequeño de aproximadamente 1476 eventos, todos agrupados en el lado derecho de la Figura 4.




Como antes, el tiempo narrativo se mueve desde la parte superior a la parte inferior de la página, los eventos superpuestos están conectados por arcos invisibles, y los eventos compartidos a través de múltiples narrativas están sombreados. Uno podría considerar un componente como un caso. El problema sustantivo es que es demasiado frágil. La eliminación de cualquier número de arcos o nodos individuales (relaciones causales o eventos) daría como resultado una partición del componente en múltiples subgrafos discretos. Nuestra estrategia es definir un caso candidato como un componente bicomponente, insistiendo en que todos los eventos estén conectados por al menos dos vías independientes y para probar su robustez para el futuro. El bicomponente más grande contiene 493 eventos. La figura 5 representa la estructura de este bicomponente, siguiendo la plantilla utilizada en las figuras anteriores. La Figura 5 destaca eventos compartidos en múltiples narrativas.
Este es el caso candidato.



5. CASOS DE PRUEBA

Para saber qué significa un evento, uno debe incrustarlo en una secuencia de eventos interrelacionados, que a su vez están integrados en secuencias más grandes que componen un caso. Algunos casos son más sólidos que otros. Los casos robustos se componen de elementos que, incluso si se activan en el futuro (o por descubrimiento) no cambian el caso. Es posible evaluar la robustez del caso simulando el efecto del futuro. Los subproductos son una evaluación de la solidez de los casos y un inventario de los eventos ordenados con respecto a la probabilidad de que sean causables. La Figura 6 informa la solidez de nuestro caso candidato, su resistencia a las perturbaciones menores y mayores. El criterio que usamos es la estadística RAND, que informa la extensión del acuerdo de clasificación cuando un par de elementos seleccionados al azar (aquí, eventos) se clasifican de la misma manera (perteneciendo al mismo grupo o perteneciendo a diferentes grupos) a través de dos particiones de una matriz. La estadística ajustada corrige la superposición casual [18, Eq. 9] e informa el acuerdo entre dos subgrafos más allá de la expectativa de azar.
El lado izquierdo de la Figura 6 informa el grado de acuerdo entre los eventos iniciales que componen el bicomponente inicial (n=479) y los eventos que componen un segundo bicomponente potencialmente alterado por la adición aleatoria de 1 a 10 nuevos enlaces a uno o más de los eventos de 1995 que componen el universo de eventos de Liu Ling. En otras palabras, agregamos un número de líneas aleatorias para conectar eventos previamente desconectados en Liu Ling. Agregar enlaces cambia la estructura del grafo original (al igual que el descubrimiento de un nuevo "hecho" podría conectar dos eventos que anteriormente se consideraban desconectados). Luego, reducimos el nuevo gráfico a su bicomponente más grande y comparamos el bicomponente del gráfico original con el nuevo bicomponente. Para cada caso, ejecutamos la misma simulación 500 veces, evaluando el efecto de agregar 1, 2, 3, ... 10 enlaces. La línea horizontal oscura informa el efecto mediano; el sombreado sombreado informa el rango intercuartílico. Al alejarse de las áreas sombreadas hay puntos que informan los efectos extremos de agregar enlaces.
Debería ser obvio que el caso es robusto al impacto de agregar un enlace. En la instancia promedio, no hay cambio. En el peor de los casos, agregar una sola línea resulta en un acuerdo entre los dos casos candidatos, que es un 93% mayor de lo esperado por casualidad. Los efectos de la mantequilla son posibles, pero extremadamente raros. Se observa un patrón similar para la adición de dos o tres relaciones nuevas. La estructura se rompe un poco con alteraciones más y más radicales del gráfico original. En el momento en que se agregan 10 nuevas líneas, la superposición entre los dos casos candidatos cae un 90% más de lo esperado por casualidad. El alcance del cambio es significativo, al igual que el descubrimiento de un nuevo archivo, múltiples adiciones conducirían a (re) conectar elementos de la estructura de datos subyacente, por lo tanto,

El alcance del cambio es significativo, al igual que el descubrimiento de un nuevo archivo, las adiciones múltiples conducirían a (re) conectar elementos de la estructura de datos subyacente, lo que podría cambiar su significado cambiando el caso en el que están integrados. La alteración simultánea de múltiples relaciones causales puede tener un profundo efecto multiplicador. La inestabilidad del caso resulta de combinaciones específicas (conjunciones) de cambios múltiples y simultáneos en los datos subyacentes.El efecto de eliminar relaciones es mucho menos pronunciado. Incluso en casos extremos, eliminando 10 enlaces, y por lo tanto potencialmente hasta 20 nodos, los dos casos candidatos siguen siendo notablemente similares. Aquí, el contraste entre nuestro caso y las narrativas históricas tradicionales (o incluso el componente que identificamos anteriormente) está marcado. Estos hallazgos no son artefactos, y proporcionan una idea de la estructura de un caso. Si se eliminase una ventaja de un bicomponente mínimamente conectado, el resultado sería una partición del componente en subgrafos y, por lo tanto, un acuerdo de clasificación significativamente inferior al que observamos. La solidez del caso para la eliminación implica que el bicomponente está compuesto de múltiples clústeres densos y que los eventos que componen cada grupo están vinculados por más de dos vías independientes. Esta estructura está más cerca de la estructura social escrita en grande. La densidad local de las estructuras de eventos reales protege los casos de colapso de las perturbaciones que tienen el efecto de eliminar las relaciones causales entre los eventos históricos.

Rompedores de casos

Para los casos que colapsan bajo una presión sutil (al agregar o eliminar una o unas pocas líneas), uno podría tener poca confianza en los significados atribuidos a un evento. Con casos robustos para el futuro, el significado de los eventos que componen el caso es fijo. Se sigue que si otros siguieran la misma estrategia de investigación, revelarían el mismo caso. En consecuencia, estarían de acuerdo con el significado del evento. Como útil es un inventario de eventos dispuestos con respecto a su probabilidad de romper el caso. Esta matriz permitiría que los científicos sociales históricos aprendan acerca de las características estructurales de los eventos que tienen el potencial de tocar los efectos de ruptura de casos. De las colas en ambos paneles de la Figura 6, está claro que en algunos casos, agregar o quitar un borde puede romper la caja. Estos son eventos fundamentales. Los eventos pivotales pueden inducirse de maneras que ya no están implícitas en la cohesión proximal de los grupos de eventos iniciales.



Un mecanismo (diferenciación) es que un clúster de evento temprano conecta múltiples clústeres de sucesos posteriores, en cada caso a través de múltiples rutas independientes. Un segundo mecanismo (convergencia) es que los clústeres de eventos iniciales separados se conectan a los mismos conglomerados de eventos subsiguientes, en cada caso a través de múltiples rutas independientes. Varias combinaciones de diferenciación también pueden ser visibles. En el primer caso (diferenciación), lo que parece un clúster de eventos unitarios se divide en múltiples clusters de eventos. En el segundo caso (convergencia) observamos el tipo inverso de estructura.
Una estrategia simple para identificar bordes / nodos de alto impacto es recorrer cada borde (o par de nodos) de a uno por vez, eliminarlo o agregarlo, y calcular una estadística RAND ajustada para los bicomponentes resultantes. Esto genera un puntaje de impacto potencial sistemático para cada borde, bajo la suposición de que podría ser eliminado (o agregado entre nodos) por algún evento futuro. En los límites de nuestro caso se encuentran grupos de eventos más pequeños y relativamente densos. Si los eventos que se encuentran en el límite de los casos son o no fundamentales depende de la estructura de los grupos de eventos más pequeños que, como las lunas, están suspendidos en la periferia del caso focal. En este caso, los eventos pivotales se ubican exclusivamente dentro de las regiones semi-densas del bicomponente.

6. DISCUSIÓN

Este artículo explota los métodos de red para hacer historia. Al centrarse en las redes como útiles para el método de la ciencia social histórica, han aparecido nuevas soluciones a viejos problemas. El problema más profundo es qué significan los eventos. La idea central de este artículo es que el significado de los eventos depende de su posición en una secuencia de eventos y, por lo tanto, el problema central de las ciencias sociales históricas son las secuencias de sucesos de cobertura, con el fin de inducir principios y fines. Las soluciones antiguas para la circunscripción de un caso están por todas partes. Descansan en conocer el final, teniendo una teoría para guiar la selección de eventos hacia un comienzo. La estructura de la historia aparece como un reloj de arena. Toda la energía causal tangible está encerrada en corrientes de comportamiento delgadas que parecen estar sujetas a todo tipo de contingencia. Se necesita poca visión para ver que, al igual que las muñecas rusas anidadas, el interior de una historia proporciona la madeja exterior para otra. En cada eliminación, lo que parece globalmente escaso se revela como denso a nivel local, y viceversa. 

Los métodos de red proporcionan una forma de explotar esta característica fractal de las estructuras de eventos, si podemos revelarlas. Ilustramos una estrategia simple para generar y revelar estructuras de eventos densos, como una nueva unidad de análisis. La estrategia que ilustramos es para intercalar historias múltiples. Las estructuras de eventos históricos que produce nuestro método se caracterizan por su ciclicidad, redundancia y densidad local.

Debido a que son estructuras, tienen parámetros significativos. Se ajustan a nuestra comprensión intuitiva de un caso, como algo que envuelve eventos dentro de un límite, ya sea en virtud de principios estructurales similares que organizan las relaciones entre los elementos, o una estructuración profunda a través de la memoria o la codificación cultural. También se ajustan a nuestra comprensión intuitiva de cómo se desarrolla la historia como resultado de múltiples fuentes que operan a través de múltiples vías en múltiples niveles de observación.
Si la historia tiene esta estructura, se deduce que la contingencia, mientras sea posible, está limitada por estructuras de eventos fractales profundamente complejas que absorben los eventos del presente y del futuro. Difícilmente podría ser de otra manera. ¿Cómo puede ser entonces que la contingencia y el azar desempeñen papeles tan grandes en la comprensión histórica? Una respuesta conservadora se sugiere arriba. Algunos eventos rompen casos. Debido a que este es el caso, una contribución central de la metodología que proponemos es producir una serie consistente de eventos con respecto a su probabilidad de servir como casos quebrantadores. Tal arreglo ayudará, como mínimo, a los historiadores a demostrar empíricamente qué eventos son críticos para su caso. A largo plazo, una mejor comprensión de los casos que interrumpen los casos, dentro de los casos, debería proporcionar una base para la abstracción en todos los casos, el objetivo principal de la sociología histórica.
Hay más posibilidades radicales. Uno podría, por supuesto, con algo de ironía, simplemente afirmar que el énfasis en el azar y la contingencia es el resultado de las presiones disciplinarias. Hay algo de verdad en esta afirmación, aunque tal vez no en el aspecto que uno pueda tener. La verdad radica en el compromiso que la (s) disciplina (s) tiene con los casos antiguos. Si el nuevo trabajo debe permanecer dentro de los límites de los casos aceptados, los nuevos argumentos más convenientes gravitarán hacia la contingencia como explicación. Sin embargo, podría ser de otra manera. Si el juicio ha producido los casos reales a considerar, el método propuesto en este artículo inducirá esos casos, y solo esos casos.
Al mismo tiempo, el método que describimos permite la inducción de casos: estructuras de eventos densas y robustas a una leve permutación, para las cuales no tenemos palabras. Y aquí, quizás, yace la avenida para una nueva percepción del pasado. Nuestra conjetura es que el compromiso de los historiadores con la estructura de casos conocidos ha limitado significativamente nuestra comprensión de los eventos, secuencias de eventos y la naturaleza del pasado, de la misma manera que el compromiso de los sociólogos con la realidad de las descripciones categóricas de la presente comprensión limitada de las estructuras sociales dentro de las cuales se organiza, expresa y representa el material de la vida. Para estar seguros, por supuesto, uno tiene que esperar las aplicaciones posteriores de los métodos de red -más sofisticados que los utilizados aquí- a la historia. 



REFERENCIAS

1. Bearman, P.; Stovel, K. Becoming a Nazi: A model for narrative networks. Poetics, Forthcoming, 1999.
2. Barkey, K.; Van Rossen, R. Networks of contention: Villages and regional structure in the seventeenth century Ottoman empire. Am J Sociol 1997, 102(5), 1345–1382.
3. Bearman, P. Relations into Rhetorics; Rose Monograph Series; ASA: New Brunswick, NJ, 1993.
4. Brudner, L.; White, D. Class, property and structural endogamy: Visualizing networked histories. Theory and Society 1997, 25, 161–208.
5. Gould, R.V. Insurgent Identities: Class, Community, and Protest in Paris from 1848 to the Commune; University of Chicago Press: Chicago, IL, 1995.
6. Gould, R.V. Patron-client ties, state centralization, and the whiskey rebellion. Am J Sociol 1996, 102(5), 400 – 429.
7. Padgett, J.; Ansell, C. Robust action and the rise of the Medici, 1400 –1434. Am J Sociol 1993, 98, 1259 –1319.
8. Emirbayer, M.; Goodwin, J. Network analysis, culture, and the problem of agency. Am J Sociol 1994, 99, 1411–1454.
9. Tilly, C. Durable Inequality; University of California Press: Berkeley, 1999.
10. White, H. Identity and Control; Princeton University Press: Princeton, NJ, 1992.
11. Frank, O. Sampling and estimation in large social networks. Social Networks 1978, 1, 91–101.
12. Granovetter, M. Network sampling: Some first steps. Am J Sociol 1977, 81(6), 1287–1303.
13. Myrdal, J. Report From a Chinese Village; Pantheon Books: New York, NY, 1965.
14. Labov, W. Language in the Inner City; University of Pennsylvania Press: Philadelphia, 1972.
15. Franzosi, R. From Words to Numbers. Unpublished Manuscript. Oxford University, England, 1999.
16. Wasserman, S.; Faust, K. Social Network Analysis. Methods and Applications; Cambridge University Press: Cambridge, MA, 1994.
17. White, D.; Schnegg, M.; Brudner, L.; Nutini, H. Status Groups and Structural Endogamy: Compadrazgo in Rural Tlaxcala, Mexico. Unpublished manuscript, 1999.
18. Morey, R.; Agresti, A. The measurement of classification agreement:An adjustment to the RAND statistic for chance agreement. Educational Psychological Measurement 1984, 44, 33–37.

lunes, 3 de octubre de 2016

ARS 101: Bi-componentes conectados o vértices de corte

Bicomponentes conectados o vértice de corte
Wikipedia


Un grafo de ejemplo con el vértice de corte marcado. Cada color corresponde a un vértice de corte. vértices multicolores se cortan vértices, y por lo tanto pertenecen a varios vértice de corte.

En la teoría de grafos, un vértice de corte (también conocido como un bloque o componente 2-conectado) es un subgrafo máximo biconexas. Cualquier grafo conexo se descompone en un árbol del vértice de corte llamado el árbol de corte de bloque del grafo. Los bloques están unidos entre sí en los vértices compartidos llamados vértices de corte o puntos de articulación. Específicamente, un vértice de corte es cualquier vértice cuya eliminación aumenta el número de componentes conectados.


Algoritmos

El tiempo lineal profundidad primera búsqueda

El algoritmo secuencial clásica para el cálculo de vértice de corte en un grafo no dirigido conectada se debe a John Hopcroft y Robert Tarjan (1973). [1] Se ejecuta en tiempo lineal, y se basa en la búsqueda en profundidad. Este algoritmo también se perfila como un Problem 22-2 de su Introduction to Algorithms (tanto 2ª y 3ª ediciones).

La idea es ejecutar una búsqueda en profundidad mientras se mantiene la siguiente información:
  • la profundidad de cada vértice en el árbol de profundidad-primero-búsqueda (una vez que se visitó), y
  • para cada vértice v, la profundidad más baja de los vecinos de todos los descendientes de v en el árbol de profundidad primera búsqueda, llamado el punto más bajo.

La profundidad es estándar para mantener durante una búsqueda en profundidad. El punto más bajo de v puede calcularse después de visitar todos los descendientes de v (es decir, justo antes de v se apareció de la pila profundidad-primero-búsqueda) como el mínimo de la profundidad de v, la profundidad de todos los vecinos de v (aparte de la padre de v en el árbol de la profundidad de primera búsqueda) y el punto más bajo de todos los hijos de v en el árbol de la profundidad de primera búsqueda.

La clave es que un vértice no raíz v es un vértice de corte (o punto de articulación) que separa dos vértice de corte si y sólo si hay un niño y de v tal que si profundidad  ≥ punto más bajo (y) (v). Esta propiedad puede ser probado una vez que la búsqueda en profundidad regresó de cada hijo de v (es decir, justo antes de v se hizo estallar de la pila de profundidad primera búsqueda), y si es verdad, v separa el grafo en diferentes vértice de corte. Esto se puede representar mediante el cálculo de un vértice de corte de cada uno de estos y (un componente que contiene y contendrá el subárbol de y, además v) y, a continuación, borrar el subárbol de y del árbol.

El vértice de la raíz debe ser manejado por separado: es un vértice de corte si y sólo si tiene al menos dos hijos. Por lo tanto, basta con simplemente construir un componente de cada subárbol hijo de la raíz (incluyendo la raíz).

Pseudocódigo

GetArticulationPoints(i, d)
    visited[i] = true
    depth[i] = d
    low[i] = d
    childCount = 0
    isArticulation = false
    for each ni in adj[i]
        if not visited[ni]
            parent[ni] = i
            GetArticulationPoints(ni, d + 1)
            childCount = childCount + 1
            if low[ni] >= depth[i]
                isArticulation = true
            low[i] = Min(low[i], low[ni])
        else if ni <> parent[i]
            low[i] = Min(low[i], depth[ni])
    if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
        Output i as articulation point

Otros algoritmos

Una alternativa simple al algoritmo anterior utiliza descomposiciones de la cadena, que son descomposiciones especiales para los oídos en función de árboles DFS. [2] Las descomposiciones de cadena se pueden calcular en tiempo lineal por esta regla de desplazamiento. Sea C una descomposición de la cadena de G. Entonces se conecta-2-vértice G si y sólo si G tiene grado mínimo 2 y C1 es el único ciclo en C. Esto da inmediatamente una prueba de 2-conectividad en tiempo lineal y se puede ampliar listar todos los vértices de corte de G en el tiempo lineal utilizando la siguiente instrucción: un vértice v en un grafo conexo G (con grado mínimo 2) es un vértice de corte si y sólo si v es incidente a un puente o v es el primer vértice de un ciclo en C - C1. La lista de los vértices de corte se puede utilizar para crear el árbol de bloque de corte de G en el tiempo lineal.

En la versión en línea del problema, se añaden vértices y aristas (pero no eliminado) de forma dinámica, y una estructura de datos deben mantener las vértice de corte. Jeffery Westbrook y Robert Tarjan (1992) [3] desarrollaron una estructura de datos eficiente para este problema sobre la base de estructuras de datos disjuntos-set. En concreto, se procesa n vértices adiciones y adiciones m de borde en O (m α (m, n)) tiempo total, donde α es la función inversa Ackermann. Esta vez unida se demostró ser óptima.

Uzi Vishkin y Robert Tarjan (1985) [4] diseñaron un algoritmo paralelo en CRCW PRAM que se ejecuta en O (log n) tiempo con n + m procesadores. Guojing Cong y David A. Bader (2005) [5] desarrollaron un algoritmo que logra una aceleración de 5 con 12 procesadores en SMP. Aceleraciones superiores a 30 basado en el algoritmo original Tarjan-Vishkin fueron reportados por James A. Edwards y Uzi Vishkin (2012). [6]

Estructuras relacionadas

Relación de equivalencia

Uno puede definir una relación binaria en los bordes de un grafo no dirigido arbitraria, según la cual dos bordes E y F están relacionadas si y sólo si, ya sea e = f o el grafo contiene un ciclo simple tanto a través de e y f. Cada borde está relacionada a sí mismo, y un borde e está relacionado con otro borde f si y sólo si f está relacionado de la misma manera a E, menos evidente, esta es una relación transitiva: si existe un ciclo simple que contiene bordes e y f, y otro ciclo simple que contiene bordes F y g, entonces se pueden combinar estos dos ciclos de encontrar un ciclo simple a través de e y g. Por lo tanto, esta es una relación de equivalencia, y que puede ser utilizado para dividir los bordes en clases de equivalencia, los subconjuntos de los bordes con la propiedad de que dos bordes están relacionados entre sí, si y sólo si pertenecen a la misma clase de equivalencia. Los subgraphs formados por los bordes de cada clase de equivalencia son los vértice de corte de la grafo dada. Por lo tanto, los vértice de corte partición de los bordes de la grafo; sin embargo, pueden compartir vértices entre sí. [7]

Grafo de bloque 

El grafo de bloques de un grafo dado G es el grafo intersección de sus bloques. Por lo tanto, tiene un vértice para cada bloque de G, y un borde entre dos vértices siempre que las correspondientes dos bloques comparten un vértice. Un grafo H es el grafo de bloques de otro grafo G exactamente cuando todos los bloques de H son subgrafos completos. Los grafo H con esta propiedad son conocidos como los grafos de bloque. [8]

Árbol de bloque de corte

Un punto de un grafo de G punto de corte, el vértice de corte, o la articulación es un vértice que es compartida por dos o más bloques. La estructura de los bloques y los puntos de corte de un grafo conectado puede ser descrita por un árbol llamado el árbol de bloque de corte o árbol de BC. Este árbol tiene un vértice para cada bloque y para cada punto del grafo dada la articulación. Hay una ventaja en el árbol de bloque de corte para cada par de un bloque y un punto de articulación que pertenece a ese bloque. [9]


Notas

  1. Hopcroft, J.; Tarjan, R. (1973). "Algorithm 447: efficient algorithms for graph manipulation". Communications of the ACM. 16 (6): 372–378. doi:10.1145/362248.362272.
  2. Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters, 113 (7): 241–244, doi:10.1016/j.ipl.2013.01.016.
  3. Westbrook, J.; Tarjan, R. E. (1992). "Maintaining bridge-connected and biconnected components on-line". Algorithmica. 7: 433–464. doi:10.1007/BF01758773.
  4. Tarjan, R.; Vishkin, U. (1985). "An Efficient Parallel Biconnectivity Algorithm". SIAM J. Comput. 14 (4): 862–874. doi:10.1137/0214061.
  5. Guojing Cong and David A. Bader, (2005). "An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs)". Proceedings of the 19th IEEE International Conference on Parallel and Distributed Processing Symposium. pp. 45b. doi:10.1109/IPDPS.2005.100.
  6. Edwards, J. A.; Vishkin, U. (2012). "Better speedups using simpler parallel programming for graph connectivity and biconnectivity". Proceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and Manycores - PMAM '12. p. 103. doi:10.1145/2141702.2141714. ISBN 9781450312110.
  7. Tarjan & Vishkin (1985) credit the definition of this equivalence relation to Harary (1969); however, Harary does not appear to describe it in explicit terms.
  8. Harary, Frank (1969), Graph Theory, Addison-Wesley, p. 29.
  9. Harary (1969), p. 36.