Encontrando comunidades por caminos aleatorios en redes científicas

Mapas de caminos aleatorios en redes complejas revelan estructura de comunidades
Martin Rosvall *, † y Carl T. Bergstrom *, ‡


Editado por Brian Skyrms, Universidad de California, Irvine, CA, y aprobado el 10 de diciembre de 2007 (recibido por opinión 21 julio, 2007)
PNAS

Para comprender la organización multipartito de los sistemas biológicos y sociales a gran escala, se introduce un enfoque teórico de información que revela la estructura de la comunidad en las redes ponderados y dirigidas. Utilizamos el flujo probabilidad de caminos aleatorios en una red como un sustituto de los flujos de información en el sistema real y se descomponen la red en módulos mediante la compresión de una descripción del flujo de probabilidad. El resultado es un mapa que tanto simplifica y pone de relieve las regularidades en la estructura y sus relaciones. Presentamos el método al hacer un mapa de la comunicación científica como se refleja en los patrones de citación de> 6.000 revistas. Descubrimos una organización multicéntrica con campos que varían mucho de tamaño y el grado de integración en la red de la ciencia. A lo largo de la columna vertebral de la red, incluyendo la física, la química, la biología molecular y la medicina-flujos de información bidireccional, pero el mapa revela un patrón direccional de la cita de los campos aplicados a las ciencias básicas.
Palabras claves: compresión, agrupación, teoría de la información, mapeo de ciencia, bibiometría

Los sistemas biológicos y sociales se diferencian, multipartito, integrada y dinámica. Los datos acerca de estos sistemas, ahora disponibles en escalas sin precedentes, a menudo se esquematizan como redes. Tales abstracciones son de gran alcance (1, 2), pero aún así como abstracciones siguen siendo muy compleja. Por tanto, es útil para descomponer la miríada de nodos y enlaces en módulos que representan a la red (3-5). Una representación convincente retendrá la información importante acerca de la red y reflejar el hecho de que las interacciones entre los elementos de los sistemas complejos son ponderados, direccional, interdependientes y conductora. Buenas representaciones tanto simplificar y poner de relieve las estructuras subyacentes y las relaciones que representan; son mapas (6, 7).

Para crear un buen mapa, el cartógrafo debe alcanzar un delicado equilibrio entre la omisión de las estructuras importantes de simplificación y oscureciendo las relaciones significativas en un aluvión de detalles superfluos. Los mejores mapas transmiten una gran cantidad de información, sino que requieren ancho de banda mínimo: los mejores mapas son también buenas compresiones. Al adoptar un enfoque teórico de la información, podemos medir la eficiencia con un mapa representa la geografía subyacente, y podemos medir la cantidad de detalles que se pierde en el proceso de simplificación, lo que nos permite cuantificar y resolver compensación del cartógrafo.

Mapas de redes y teoría de la codificación

En este artículo, utilizamos mapas para describir la dinámica a través de los enlaces y nodos en redes dirigidas, con pesos que representan las interacciones locales entre las subunidades de un sistema. Estas interacciones locales inducen un flujo de todo el sistema de información que caracteriza el comportamiento del sistema completo (8-12). En consecuencia, si queremos entender cómo la estructura de la red se refiere al comportamiento del sistema, tenemos que entender el flujo de información en la red. Por lo tanto, identificamos los módulos que componen la red mediante la búsqueda de una descripción eficiente de grano grueso de cómo los flujos de información en la red. Un grupo de nodos entre los cuales fluye la información rápida y fácilmente se pueden agregar y se describe como un único módulo bien comunicado; los vínculos entre los módulos de captura de las vías de flujo de información entre dichos módulos.

Sucinta que describe el flujo de información es un problema de codificación o compresión. La idea clave en la teoría de la codificación es que un flujo de datos puede ser comprimido por un código que explota regularidades en el proceso que genera la corriente (13). Utilizamos un paseo aleatorio como un proxy para el flujo de información, debido a que un paseo aleatorio utiliza toda la información en la representación de la red y nada más. Por lo tanto, proporciona un mecanismo predeterminado para generar una dinámica de un diagrama de red solo (8).

Tomando este enfoque, se desarrolla un código eficiente para describir un camino aleatorio en una red. de esta manera nos muestran que la búsqueda de estructura de la comunidad en las redes es equivalente a resolver un problema de codificación (14-16). Ejemplificamos este método al hacer un mapa de la ciencia, sobre la base de cómo fluye la información entre las revistas científicas por medio de citas.

Describiendo una trayectoria en una red. Para ilustrar lo que la codificación tiene que ver con la creación de mapas, consideremos el siguiente juego de comunicación. Supongamos que usted y yo sabemos que la estructura de una red ponderada, indica. Nuestro objetivo es elegir un código que nos permitirá describir de manera eficiente caminos de la red que surgen de un proceso de paseo aleatorio en un lenguaje que refleja la estructura subyacente de la red. ¿Cómo debemos diseñar nuestro código?
Si la compresión máxima fuera el único objetivo, podríamos codificar el camino en o cerca de la velocidad de la entropía del proceso de Markov correspondiente. Shannon mostró que se puede lograr esta velocidad mediante la asignación a cada nodo un diccionario única de las transiciones salientes (17). Sin embargo, la compresión no es nuestro único objetivo; aquí, queremos que nuestro lenguaje para reflejar la estructura de la red, queremos que las palabras que utilizamos para hacer referencia a las cosas en el mundo. El enfoque de Shannon no hacer esto por nosotros, porque cada palabra de código tendría un significado diferente dependiendo de donde se utiliza. Comparación de mapas: mapas útiles asignar nombres exclusivos a las estructuras importantes. Por lo tanto, buscamos una manera de describir o que codifica el paseo aleatorio en el que las estructuras importantes de hecho conservan nombres únicos. Veamos un ejemplo concreto. Higo. 1A muestra una red ponderada con n = 25 nodos. El espesor de enlace indica la probabilidad relativa de que un paseo aleatorio atravesará cualquier enlace en particular. Sobrepuesto en la red es una realización específica de 71 pasos de un camino aleatorio que vamos a utilizar para ilustrar nuestro juego de comunicación. En la Fig. 1, se describe este paseo con niveles crecientes de compresión (B-D), que explotan más y más de las regularidades en la red.

Fig. 1.La detección de las comunidades mediante la compresión de la descripción de los flujos de información en las redes. (A) Queremos describir la trayectoria de un paseo aleatorio en la red de tal manera que las estructuras importantes tienen nombres únicos. La línea naranja muestra una trayectoria muestra. (B) Un enfoque básico es dar un nombre único a cada nodo de la red. El código de Huffman ilustrado aquí es una forma eficaz para hacerlo. Los 314 bits de la red mencionados en los apartados describen la trayectoria de la muestra en A, a partir de 1.111.100 para el primer nodo en la caminata en la esquina superior izquierda, 1100 para el segundo nodo, etc., y terminando con 00011 para el último nodo en la caminata en la esquina inferior derecha. (C) Una descripción de dos niveles del paseo aleatorio, en el que los principales grupos reciben nombres únicos, pero los nombres de los nodos dentro de los grupos se vuelven a utilizar, los rendimientos en promedio un 32% más corta descripción para esta red. Los códigos de nombres de los módulos y los códigos utilizados para indicar una salida de cada módulo se muestran a la izquierda y la derecha de las flechas bajo la red, respectivamente. El uso de este código, podemos describir el pie en A por los 243 bits de muestra debajo de la red en C. Los tres primeros bits 111 indican que el paseo se inicia en el módulo rojo, el código 0000 especifica el primer nodo en la caminata, etc. (D) de informes sólo los nombres de los módulos, y no los lugares dentro de los módulos, proporciona un granulado grueso eficiente de la red.

Codificación de Huffman. Un método sencillo de dar nombres a los nodos es el uso de un código de Huffman (18). códigos de Huffman ahorrar espacio mediante la asignación de palabras de código cortas a eventos u objetos comunes y largas palabras de código a los raros, tanto como las palabras comunes son cortas en los idiomas hablados (19). Higo. 1B muestra una codificación Huffman sin prefijo para nuestra red de ejemplo. Cada palabra de código especifica un nodo en particular, y las longitudes de palabra de código se derivan de las frecuencias de visita nodo ergódicos de un paseo aleatorio infinitamente largo. Con el código de Huffman representada en la Fig. 1B, que son capaces de describir la específica pie 71-paso en 314 bits. Si en lugar de haber elegido un código uniforme, en la que todas las palabras de código son de igual longitud, cada palabra de código sería  25 = 5 bits de longitud y se habrían necesitado 71 · 5 = 355 bits para describir el pie.
Aunque en este ejemplo se asigna palabras de código reales a los nodos con fines ilustrativos, en general, no vamos a estar interesado en las palabras de código sí mismas, sino en el límite teórico de la forma concisa podemos especificar la ruta. Aquí, invocamos el teorema de Shannon fuente de codificación (17), lo que implica que cuando se utiliza n palabras de código para describir los n estados de una variable aleatoria X que se producen con frecuencias pi, la duración media de una palabra de código puede ser inferior a la entropía de la variable aleatoria X, y: h (x) = log -Σ1n pi (pi). Este teorema nos proporciona el aparato necesario para ver que, en nuestra ilustración Huffman, el número medio de bits necesarios para describir un solo paso en el camino aleatorio estará limitada hacia abajo por la entropía H (P), donde P es la distribución de la visita frecuencias a los nodos de la red. Definimos este límite inferior de la longitud del código para ser L. Por ejemplo, L = 4,50 bits por paso en la Fig. 1B.

Destacando funciones importantes. Adaptación de la longitud de palabras de código a las frecuencias de su uso nos da palabras de código eficientes para los nodos, pero no mapa. El mero hecho de asignar nombres de longitud apropiada a los nodos hace poco para simplificar o resaltar aspectos de la estructura subyacente. Para hacer un mapa, tenemos que separar las estructuras importantes de los detalles insignificantes. Por lo tanto, dividir la red en dos niveles de descripción. Nos reservamos nombres únicos para objetos a gran escala, los grupos o módulos que se identifican dentro de nuestra red, pero reutilizamos los nombres asociados con los detalles de grano fino, los nodos individuales dentro de cada módulo. Este es un enfoque familiar para la asignación de nombres a los objetos en los mapas: la mayoría de ciudades de Estados Unidos tienen nombres únicos, pero los nombres de calles son reutilizados de una ciudad a otra, de modo que cada ciudad tiene una calle principal y una obra de Broadway y la avenida Washington y así sucesivamente . La reutilización de los nombres de las calles rara vez causa confusión, porque la mayoría de las rutas se mantengan dentro de los límites de una sola ciudad.
Una descripción de dos niveles permite describir la ruta en menos bits que podríamos hacer con una descripción de un nivel. Nos aprovechamos de la estructura de la red y, en particular, sobre el hecho de que un caminante aleatorio es estadísticamente probable que pasen largos periodos de tiempo dentro de ciertos grupos de nodos. Fig. 1C ilustra este enfoque. Damos a cada grupo un nombre único, pero utilizamos un código de Huffman para nombrar los nodos dentro de cada grupo. Una palabra clave especial, el código de salida, se elige como parte de la codificación Huffman dentro de la agrupación e indica que el pie abandona el clúster actual. El código de salida siempre es seguido por el "nombre" o código del módulo del nuevo módulo en el que el pie se mueve [ver información de apoyo (SI) para más detalles]. Por lo tanto, asignar nombres únicos a las estructuras de grano grueso (las ciudades en la metáfora de la ciudad), sino reutilizar los nombres asociados con los detalles de grano fino (las calles de la metáfora de la ciudad). El ahorro es considerable; en la descripción de dos niveles de la Fig. 1C el límite L es de 3,05 bits por paso en comparación con 4,50 para la descripción de un nivel.

En esto radica la dualidad entre la búsqueda de la estructura de la comunidad en las redes y el problema de codificación: encontrar un código eficiente, buscamos una partición módulo M de n nodos en módulos m con el fin de reducir al mínimo la descripción duración prevista de un paseo aleatorio. Mediante el uso de la partición de módulo M, la longitud media de descripción de un solo paso está dado por

Esta ecuación se compone de dos términos: la primera es la entropía del movimiento entre los módulos, y la segunda es la entropía de los movimientos dentro de los módulos (donde en salida del módulo también se considera un movimiento). Cada uno es ponderada por la frecuencia con la que se produce en la partición particular. Aquí, q↷ es la probabilidad de que el paseo aleatorio cambia módulos en cualquier paso dado. H (𝒬) es la entropía de los nombres de los módulos, es decir, la entropía de las palabras de código subrayadas en la figura. 1D. H (𝒫i) es la entropía de los movimientos dentro del módulo, incluyendo el código de salida para el módulo i. El peso p  es la fracción de movimientos dentro del módulo que se producen en el Módulo I, más la probabilidad de módulo de E tal que Σi = 1 m = 1 + pq↷ (ver SI para más detalles) que sale.

Para todos, pero las redes más pequeñas, no es factible para comprobar todas las particiones posibles para encontrar el que minimiza la longitud de la descripción en el mapa ecuación (Ec. 1). En su lugar, se utiliza la búsqueda computacional. Primero calculamos la fracción de tiempo que cada nodo es visitado por un andador al azar utilizando el método de la potencia, y el uso de estas frecuencias de visita, se explora el espacio de posibles particiones usando un algoritmo de búsqueda codiciosa determinista (20, 21). Refinamos los resultados con un enfoque de recocido simulado (6) utilizando el algoritmo de calor al baño maría (ver SI para más detalles).

La Fig. 1D muestra el mapa de la red, con los descriptores dentro del módulo se desvanecieron; aquí los objetos significativos se han puesto de relieve y los detalles se han filtrado de distancia.

En aras de la simplicidad visual, la red ilustrativa en la Fig. 1 ha ponderado pero los enlaces no dirigidos. Nuestro método se desarrolló más en general, de manera que podamos extraer información de redes con enlaces que se dirigen, además de ser ponderados. La ecuación mapa sigue siendo el mismo; sólo el camino que nos proponemos describir debe ser ligeramente modificado para lograr ergodicidad. Se introduce una pequeña τ "probabilidad de teletransporte" en el paseo aleatorio: con τ probabilidad, el proceso salta a un nodo de azar en cualquier lugar de la red, que convierte nuestra aleatoria andador en el tipo de "persona que practica surf al azar" que impulsa el algoritmo PageRank de Google (22 ). Nuestros resultados de la agrupación son muy robustos a la elección particular de la pequeña fracción τ. Por ejemplo, siempre que τ <0,45 la partición óptima de la red en la Fig. 1 sigue siendo exactamente el mismo. En general, cuanto más significativa las regularidades, las más altas τ puede ser antes de teletransporte frecuentes inunda la estructura de la red. Elegimos τ = 0,15 que corresponde a el factor de amortiguamiento conocida d = 0,85 en el algoritmo PageRank (22).

Mapeo de flujo en comparación con maximización de la modularidad 

La forma tradicional de identificación de la estructura de la comunidad en las redes dirigidos y ponderados ha sido simplemente hacer caso omiso de las direcciones y los pesos de los enlaces. Pero tales enfoques descartan valiosa información acerca de la estructura de la red. Mediante la cartografía el flujo de todo el sistema inducida por las interacciones locales entre nodos, mantenemos la información sobre las direcciones y los pesos de los enlaces. También reconocemos su interdependencia en las redes inherentemente caracterizados por los flujos. Esta distinción hace que sea interesante comparar nuestro enfoque basado en los flujos con los enfoques topológicos recientes basados ​​en la optimización de la modularidad que también hace uso de la información sobre el peso y la dirección (23-26). En su forma más general, la modularidad para una partición dada de la red en módulos M es la suma del peso total de todos los enlaces en cada módulo, menos el peso esperado

Aquí, el wii es el peso total de enlaces que inician o terminan en el módulo I, Wiin y se wiout la in- total y el peso fuera de los enlaces en el Módulo I, y w es el peso total de todos los eslabones de la red. Para estimar la estructura de la comunidad en una red, la Ec. 2 se maximiza sobre todas las posibles asignaciones de nodos en cualquier número de módulos m. Ecs. 1 y 2 reflejan dos sentidos diferentes de lo que significa tener una red. La primera, que perseguimos aquí, se encuentra la esencia de una red en los patrones de flujo que su estructura induce. Este último sitúa efectivamente la esencia de la red en las propiedades topológicas de sus enlaces (como lo hicimos en la ref. 16).

¿Esta distinción conceptual hace ninguna diferencia práctica? Higo. La figura 2 ilustra dos redes simples para los que la ecuación mapa y la modularidad dan diferentes partitionings. Los ponderados, enlaces dirigidos muestran en la red de la figura. 2A inducir un patrón estructurado de flujo con tiempos largos de persistencia en el flujo, y limitada entre los cuatro grupos, como se subraya en la izquierda. La ecuación mapa recoge en estas regularidades estructurales, y por tanto la longitud de la descripción es mucho más corto para la división en la Fig. 2A Izquierda (2,67 bits por paso) que para la figura. 2A derecha (4,13 bits por paso). La modularidad es ciego a la interdependencia en las redes caracterizadas por flujos y por lo tanto no se puede recoger en este tipo de regularidad estructural. Sólo cuenta los pesos de los enlaces, en grados, y fuera de grado en los módulos, y por lo tanto prefiere dividir la red como se muestra en la Fig. 2A derecho con la relación de mucho peso dentro de los módulos.

Fig. 2.
Mapeo de flujo pone de relieve diferentes aspectos de la estructura que lo hace la optimización de la modularidad en redes dirigidos y ponderados. La coloración de los nodos ilustra particiones alternativas de dos redes de muestra. (Izquierda) Las particiones muestran la estructura modular optimizado por la ecuación mapa (mínima L). (Derecha) muestran la estructura de particiones como optimizada por la modularidad (Q máximo). En la red se muestra en A, la partición izquierda minimiza la ecuación mapa porque los tiempos de persistencia en los módulos son de largo; con el peso de los enlaces establecidos en negrilla a dos veces el peso de otros enlaces, un andador azar sin teletransporte tarda una media de tres pasos en un módulo antes de salir. La agrupación de la derecha da una descripción más larga duración debido a un caminante al azar tarda una media de sólo 12/5 pasos en un módulo antes de salir. La agrupación de la derecha maximiza la modularidad ya la modularidad cuenta los pesos de enlaces, en el grado-y el grado de salida de los módulos; la división de la derecha coloca los enlaces fuertemente ponderados en el interior de los módulos. En B, por la misma razón, la partición de la derecha de nuevo maximiza modularidad, pero no tan la ecuación mapa. Debido a que cada nodo es o bien un fregadero o una fuente en esta red, los enlaces no inducen ningún flujo de largo alcance, y los paseos de un solo paso se describen mejor como en la partición izquierda, con todos los nodos del mismo clúster.

En la Fig. 2B, por el contrario, no existe un patrón de flujo extendida en absoluto. Cada nodo es o bien una fuente o un sumidero, y ningún movimiento a lo largo de los enlaces de la red puede exceder más de un paso de longitud. Como resultado, el teletransporte aleatorio dominará (independientemente del tipo de teletransporte), y cualquier partición en múltiples módulos dará lugar a un alto flujo entre los módulos. Para una red tal como en la Fig. 2B, en donde los enlaces no inducen un patrón de flujo, la ecuación mapa siempre particionar la red en un solo módulo. Modularidad, ya que se ve en el patrón en los enlaces y grado a cabo en ejercicio y, separa la red en los grupos que se muestran a la derecha.

¿Qué método se debe utilizar un investigador? Depende de cuál de los dos sentidos de la red, que se describe más arriba, que el investigador está estudiando. Para el análisis de datos de la red donde los enlaces representan patrones de movimiento entre los nodos, los enfoques basados ​​en el flujo, tales como el mapa ecuación son propensos a identificar los aspectos más importantes de la estructura. Para el análisis de datos de la red donde los enlaces no representan flujos pero las relaciones en lugar de pares, puede ser útil para detectar la estructura incluso cuando no existe flujo. Para estos sistemas, métodos topológicos, tales como la modularidad (11) o la compresión basada en clúster (16) pueden ser preferibles.

Mapeo de Comunicación Científica

La ciencia es una actividad humana altamente organizada y paralelo a encontrar patrones en la naturaleza; el proceso de comunicar resultados de la investigación es tan esencial para el progreso como es el acto de llevar a cabo la investigación en el primer lugar. Por lo tanto, la ciencia no es más que un conjunto de ideas, sino también el flujo de estas ideas a través de un sistema social multipartito y altamente diferenciada. flujos de citas entre las revistas dejan entrever este flujo y proporcionar la traza de la comunicación entre los científicos (27-31). Para resaltar los campos importantes y sus relaciones, para descubrir las diferencias y cambios, para simplificar y hacer que el sistema comprensible: necesitamos un buen mapa de la ciencia.

Usando la información de enfoque teórico presentado anteriormente, hacemos un mapa del flujo de citas entre 6.128 revistas en las ciencias (Fig. 3) y las ciencias sociales (Fig. 4). Los 6,434,916 citas en esta red cruzada citación representan un rastro de la actividad científica durante el año 2004 (32). Nuestra correspondencia de los datos en una base diario por diario las citas de artículos publicados en 2004 a artículos publicados en los últimos 5 años. Excluimos las revistas que publican <12 artículos por año y aquellos que no se citan otras revistas dentro del conjunto de datos. También excluimos los únicos tres principales revistas que abarcan una amplia gama de disciplinas científicas: la ciencia, la naturaleza, y Actas de la Academia Nacional de Ciencias; el amplio alcance de estas revistas de otro modo crea una ilusión de las conexiones entre las disciplinas más estrictas, cuando en realidad pocos lectores de los artículos de física en la ciencia también son cercanos a los lectores de los artículos biomédicos en el mismo. Debido a que estamos interesados ​​en las relaciones entre revistas, excluimos también de revistas autocitas.

Fig. 3.Un mapa de la ciencia sobre la base de patrones de citas. Hemos dividido 6.128 revistas conectados por 6,434,916 citas en 88 módulos y 3.024 enlaces dirigidos y ponderados. Por simplicidad visual, solo mostramos los enlaces que el navegante aleatorio atraviesa> 1 / número 5.000 de su tiempo, y sólo se muestran los módulos que se visitan a través de estos enlaces (ver la IS para la lista completa). Debido a la clasificación automática de los nodos y enlaces por parte de la persona que practica surf al azar (22), estamos seguros de que muestra los enlaces y nodos más importantes. Para este nivel de detalle particular, capturamos 98% de los pesos de nodo y el 94% de todo el flujo.

Fig. 4.Un mapa de las ciencias sociales. Las revistas que aparecen en la edición de ciencias sociales 2004 del Journal Citation Reports (32) son un subconjunto de las que se ilustran en la Fig. 3, por un total de 1.431 revistas y 217,287 citas. Cuando hacemos un mapa de este subgrupo por su cuenta, se obtiene un mayor nivel de resolución. Los 10 módulos que corresponden a las ciencias sociales ahora son divididos en 54 módulos, pero por simplicidad solo mostramos enlaces que las visitas surfista azar un mínimo de 1 / número 2.000 de su tiempo junto con los módulos que se conectan (ver la IS para la lista completa ). Para este nivel de detalle particular, capturamos 97% de los pesos de nodo y el 90% de todo el flujo.

A través de la operación de nuestro algoritmo, los campos y los límites entre ellos surgen directamente de los datos de las citas más que de nuestras nociones preconcebidas de la taxonomía científica (véanse las Fig. 3 y 4). Nuestra única contribución subjetiva ha sido sugerir nombres razonables para cada grupo de revistas que el algoritmo identifica: economía, matemáticas, ciencias de la tierra, y así sucesivamente.

El tamaño físico de cada módulo o "campo" en el mapa refleja la fracción de tiempo que un surfista aleatorio pasa siguientes citas dentro de ese módulo. tamaños de los campos varían dramáticamente. La biología molecular incluye 723 revistas que abarcan las áreas de genética, biología celular, bioquímica, inmunología y biología del desarrollo; un surfista aleatorio gasta 26% de su tiempo en este campo, indicado por el tamaño del módulo. Tribología (el estudio de la fricción) incluye sólo siete revistas, en las que un surfista aleatorio gasta 0,064% de su tiempo.

Los enlaces ponderados y dirigidos entre campos representan flujo de citación, con el color y la anchura de las flechas que indican el volumen de flujo. Las pesadas flechas entre la medicina y la biología molecular indican un tráfico masivo de citas entre estas disciplinas. Las flechas apuntan en la dirección de la citación: A → B significa "Una cita B" como se muestra en la tecla. Estos enlaces dirigidos revelan la relación entre las ciencias básicas y aplicadas. Nos encontramos con que la antigua citan este último ampliamente, pero lo contrario no es cierto, como se ve, por ejemplo, con Geotecnología citando geociencias, citando la cirugía plástica, medicina general y sistemas de energía citando física general. El espesor de los bordes del módulo refleja la probabilidad de que un surfista aleatorio dentro del módulo seguirá una citación a una revista fuera del módulo. Estas salidas muestran una gran variación; por ejemplo, el flujo de salida es de 30% en medicina general, pero sólo el 12% en economía.

El mapa revela una estructura similar a un anillo en el que todas las disciplinas principales están conectados entre sí mediante cadenas de citas, pero estas conexiones no siempre son directos porque los campos en los lados opuestos del anillo están unidos sólo a través de campos intermedios. Por ejemplo, aunque rara vez se cita la psicología física general o viceversa, la psicología y la física en general están conectados a través de los estrechos vínculos con y entre la biología molecular y la química intermediarios. Una vez que tenemos en cuenta los pesos de los vínculos entre los campos, sin embargo, se hace evidente que la estructura de la ciencia se parece más a la letra U que como un anillo, con las ciencias sociales en un terminal e ingeniería en la otra, se unió principalmente por una columna vertebral de la medicina, la biología molecular, la química y la física. Debido a que nuestro mapa muestra el patrón de citas a artículos de investigación publicados en los 5 años, lo que representa de Solla Price llama la "frontera de la investigación" (27) en lugar de las interdependencias a largo plazo entre los campos. Por ejemplo, aunque las matemáticas son esenciales para todas las ciencias naturales, el campo de las matemáticas no es central en nuestro mapa porque sólo ciertos subcampos (por ejemplo, áreas de la física y las estadísticas) dependen en gran medida de los más recientes desarrollos en matemáticas puras y contribuyen a cambio de la agenda de investigación en este campo.

 Cuando un cartógrafo diseña un mapa, la escala o alcance del mapa influye en la elección de los cuales se representan objetos. Un mapa regional omite muchos de los detalles que aparecen en un mapa de la ciudad. Del mismo modo, en el enfoque que hemos desarrollado aquí, el tamaño o la resolución adecuada de los módulos depende del universo de los nodos que están incluidos en la red. Si comparamos el mapa de una red a un mapa de un subconjunto de la misma red, esperaríamos ver el mapa del subconjunto revelan divisiones más finas, con módulos compuestos por un menor número de nodos. Higo. 4 ilustra realizan particiones de un subconjunto de las revistas incluidas en el mapa de la ciencia: las 1.431 revistas en las ciencias sociales. La estructura básica de los campos y sus relaciones se mantiene sin cambios, con la psiquiatría y la psicología unido a través de la sociología y la gestión de la economía y la ciencia política, pero el mapa también revela más detalles. Las fracturas de antropología a lo largo de la línea divisoria física / cultural. La sociología se divide en grupos de comportamiento e institucionales. Comercialización separa de gestión. Psicología y psiquiatría revelan un conjunto de sub-disciplinas aplicadas.

El nivel de detalle adicional en el mapa centrado más estrictamente habría sido el desorden en el mapa completo de la ciencia. Cuando diseñamos mapas para ayudarnos a comprender el mundo, tenemos que encontrar ese equilibrio donde eliminamos detalles superfluos, pero destacamos las relaciones entre las estructuras importantes. Aquí, hemos demostrado cómo formalizar el precepto de este cartógrafo utilizando el aparato matemático de la teoría de la información.

ARS Avanzado: Complejo clique

Complejo clique
Wikipedia



El complejo clique de un grafo. Los grupos de tamaño uno se muestran como pequeños discos rojos; grupos de tamaño 2 se muestran como segmentos de líneas negras; grupos de tamaño 3 se muestran como triángulos de color azul claro; y grupos de tamaño 4 o tetraedros se muestran de color azul oscuro.


Los complejos cliques, complejos de bandera, e hipergrafos conformales son objetos matemáticos que están relacionados estrechamente con la teoría de grafos y la topología geométrica que cada uno describen camarillas (subgrafos completos) de un grafo no dirigido.

El complejo clique  X(G) de un grafo no dirigido G es un complejo simplicial abstracto (es decir, una familia de conjuntos finitos cerrados bajo la operación de toma de subconjuntos), formada por los conjuntos de vértices en las camarillas de G. Cualquier subconjunto de una camarilla es en sí misma una camarilla, por lo que esta familia de conjuntos cumple con el requisito de un complejo simplicial abstracto en el que cada subconjunto de un conjunto en la familia también debe estar en la familia. El complejo clique también puede ser visto como un espacio topológico en el que cada camarilla de k vértices está representado por un simplex de dimensión k - 1. El 1-esqueleto de X (G) (también conocido como el grafo subyacente del complejo) es un grafo no dirigido con un vértice por cada conjunto de 1 elemento en la familia y un enlace para cada conjunto de 2 elementos en la familia; es isomorfo a G. [1]

Los complejos clique son también conocidos como complejos de Whitney. Una triangulación Whitney o triangulación limpio de un colector (manifold) de dos dimensiones es una incrustación de un grafo de G en el colector de tal manera que cada cara es un triángulo y cada triángulo es una cara. Si un grafo G tiene una triangulación Whitney, debe formar un complejo de célula que es isomorfo al complejo Whitney de G. En este caso, el complejo (visto como un espacio topológico) es homeomorfo al colector subyacente. Un grafo G tiene un complejo clique de 2 colectores (manifold), y puede ser incrustado como una triangulación Whitney, si y sólo si G es localmente cíclico; esto significa que, para cada vértice v en el grafo, el subgrafo inducido formado por los vecinos de v forma un solo ciclo. [2]

Complejo de independencia

El complejo independencia I (G) de un grafo G se forma de la misma manera como el complejo camarilla de los conjuntos independientes de G. Es el complejo camarilla del grafo complemento de G.

Complejo de bandera

En un complejo simplicial abstracto, un conjunto S de vértices que no es en sí parte del complejo, pero de tal manera que cada par de vértices en S pertenece a algún simplex en el complejo, que se llama un simplex vacío. Mikhail Gromov define la condición de no-Δ ser la condición de que un complejo no tienen simplices vacías. Un complejo bandera es un complejo simplicial abstracto que no tiene simplices vacías; es decir, que es la condición no-Δ un complejo de Gromov satisfacer. Cualquier complejo bandera es el complejo de su camarilla 1-esqueleto. Por lo tanto, los complejos y los complejos bandera camarilla son esencialmente la misma cosa. Sin embargo, en muchos casos puede ser conveniente definir un complejo bandera directamente de algunos datos distintos de un grafo, en lugar de indirectamente como el complejo clique de un grafo derivado de los datos. [3]

Conforme de hipergrafo

El grafo primario G (H) de un hipergrafo es el grafo en el mismo conjunto de vértices que tiene como sus enlaces los pares de vértices que aparecen juntos en la misma hiperenlace. Un hipergrafo se dice que es conforme si cada camarilla máxima de su grafo es un hipernelace primitivo, o equivalentemente, si cada camarilla de su grafo primario está contenida en alguna hiperenlace. [4] Si se requiere el hipergrafo sea descendente cerrado (por lo que contiene todos los hiperenlaces que se contienen en algunos hiperenlaces) entonces el hipergrafo es conforme con precisión cuando se trata de un complejo de bandera. Esto se relaciona el lenguaje de hipergrafos al lenguaje del complejo simplicial.

Ejemplos y aplicaciones

La subdivisión baricéntrica de cualquier complejo C de células es un complejo de bandera que tiene un vértice por célula de C. Una colección de vértices de la subdivisión baricéntrica formar un simplex si y sólo si la colección correspondiente de células de C forman una bandera (una cadena en el inclusión de pedido de las células). [3] En particular, la subdivisión barycentric de un complejo celular en un 2-colector da lugar a una triangulación Whitney del colector.

El complejo orden de un conjunto parcialmente ordenado se compone de las cadenas (subconjuntos totalmente ordenado) del orden parcial. Si cada par de algún subconjunto es en sí mismo ordenó, entonces todo el subconjunto es una cadena, por lo que los complejos satisface la condición de la orden de no-Δ. Se puede interpretar como el complejo camarilla del grafo de la comparabilidad de la orden parcial. [3]

El complejo de empardamiento (matching complex) de un grafo consiste en los conjuntos de enlaces ninguno de cuyos pares comparten un punto final; de nuevo, esta familia de conjuntos satisface la condición de no-Δ. Puede ser visto como el complejo camarilla del grafo complemento del grafo de líneas del grafo dado. Cuando el complejo juego se denomina sin ninguna representación grafo concreta como contexto, significa el complejo juego de un grafo completo. El complejo juego de un grafo bipartito completo K_m,n es conocida como un complejo de tablero de ajedrez. Es el clique de del grafo complemento del grafo de una torre, [5] y cada uno de sus simplices representa una colocación de torres en un tablero de m × n de ajedrez de tal manera que no hay dos de las torres atacan entre sí. Cuando m = n ± 1, las formas complejas de tablero de ajedrez una pseudo-colector.

El complejo Vietoris-Rips de un conjunto de puntos en un espacio métrico es un caso especial de un complejo clique, formado a partir del grafo de disco unidad de los puntos; Sin embargo, cada complejo clique X(G) puede ser interpretada como el complejo Vietoris-Rips de la métrica camino más corto en el grafo subyacente G.

Hodkinson y Otto (2003) describen una aplicación de hipergrafos conformales en la lógica de las estructuras relacionales. En ese contexto, el grafo de Gaifman de una estructura relacional es el mismo que el grafo subyacente del hipergrafo que representa la estructura, y una estructura esté vigilado si corresponde a un hipergrafo conformal.

Gromov mostró que un complejo cúbico (es decir, una familia de hipercubos intersección cara a cara) forma un CAT (0) espacio si y sólo si el complejo está simplemente conectado y el enlace de cada vértice forma un complejo bandera. Una reunión compleja cúbica estas condiciones a veces se llama una cubicación o un espacio con paredes. [1] [6]

Referencias

1. Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J. E.; Pach, J.; Pollack, R., Surveys on Discrete and Computational Geometry: Twenty Years Later (PDF), Contemporary Mathematics, 453, Providence, RI: AMS, pp. 49–86.
2. Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets, North-Holland, ISBN 0-444-87489-5.
3. Chatterji, I.; Niblo, G. (2005), "From wall spaces to CAT(0) cube complexes", International Journal of Algebra and Computation, 15 (5–6): 875–885, arXiv:math.GT/0309036, doi:10.1142/S0218196705002669.
4. Davis, M. W. (2002), "Nonpositive curvature and reflection groups", in Daverman, R. J.; Sher, R. B., Handbook of Geometric Topology, Elsevier, pp. 373–422.
5. Dong, X.; Wachs, M. L. (2002), "Combinatorial Laplacian of the matching complex", Electronic Journal of Combinatorics, 9: R17.
6. Hartsfeld, N.; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica, 11 (2): 145–155, doi:10.1007/BF01206358.
7. Hodkinson, I.; Otto, M. (2003), "Finite conformal hypergraph covers and Gaifman cliques in finite structures", The Bulletin of Symbolic Logic, 9 (3): 387–405, doi:10.2178/bsl/1058448678.
8. Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics, 258: 123–135, doi:10.1016/S0012-365X(02)00266-2.
9. Malnič, A.; Mohar, B. (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B, 56 (2): 147–164, doi:10.1016/0095-8956(92)90015-P.

ARS 101: Centralidad Alfa

Centralidad Alfa
Wikipedia

En la teoría de grafos y análisis de redes sociales, la centralidad Alfa es una medida de centralidad de los nodos de un grafo. Es una adaptación de la centralidad de vector propio con la particularidad de que los nodos están impregnadas de importancia a partir de fuentes externas.

Definición

Dada una gráfica con la matriz de adyacencia  la centralidad alfa se define como sigue:



donde  es la importancia dada al nodo externo  y  es un parámetro. [1]

Motivación

Para entender la centralidad alfa primero hay que entender Centralidad del Vector Propio. Un proceso intuitivo para calcular vector propio carácter central es dar a cada nodo de una cantidad positiva al azar a partir de influencia. Cada nodo se divide entonces su influencia de manera uniforme y lo divide entre sus vecinos hacia el exterior, recibiendo de sus vecinos hacia el interior en especie. Este proceso se repite hasta que todo el mundo está dando hacia fuera tanto como que están tomando y el sistema ha alcanzado el estado estacionario. La cantidad de influencia que tienen en este estado estacionario es su centralidad del vector propio. Computacionalmente este proceso se llama el método de la potencia. Sabemos que este proceso ha convergido cuando el vector de influencia cambia sólo por una constante de la siguiente manera.



Donde  es la cantidad de influencia que el nodo i lleva,  es la matriz de adyacencia y  pasa a ser el valor propio director (aunque esto no es muy importante en este caso).

La centralidad Alfa mejora este proceso al permitir que los nodos que tienen fuentes de influencia. La cantidad de influencia que el nodo i recibe en cada ronda se codifica en . El proceso descrito anteriormente ahora debe detenerse cuando

,
Donde  es una constante que intercambia la importancia de la influencia externa en contra de la importancia de la conexión. Cuando  sólo importa la influencia externa. Cuando  es muy grande, entonces sólo importa la conectividad, es decir, reducimos al caso centralidad del vector propio.

En lugar de realizar la iteración descrita anteriormente se puede resolver este sistema para x, obteniendo la siguiente ecuación:

,

Aplicaciones

La centralidad Alfa se lleva a cabo en la biblioteca igraph para el análisis y visualización de red. [2]

Ejemplo

FUna epidemia representa otro tipo de flujo en una red. Una epidemia es un proceso dinámico que, a diferencia del paseo aleatorio, transiciona simultáneamente a todos los vecinos de un nodo dado (y con éxito infecta cada nodo, o sobrevive en ese nodo, con una probabilidad a). La película anterior muestra una propagación de la epidemia en el gráfico Club de Karate. Bajo ciertas condiciones, que alcanza un estado estacionario, dada por centralidad Alfa. La centralidad Alfa fue introducido por Bonacich [1987] como una generalización del índice de Katz de un nodo. Cuando la probabilidad de infección está supeditada a sobrepasar un umbral epidémico, la centralidad Alfa del Vector Propio es proporcional a la centralidad. Esta medida, introducido por Bonacich [2001] está dada por el vector propio que corresponde al valor propio más grande de la matriz de adyacencia del grafo [Ghosh y Lerman, 2011]. Por cierto, el umbral de epidemia está dado por la inversa de la mayor valor propio de la matriz de adyacencia [Wang et al., 2003].

Código de Matlab para calcularla

a=0.1; % damping factor has to be smaller than 1/lambda0, where lambda0 is largest eigenvalue of A
s=A*t;
cr=s;
for i=1:20
cr=s+a*A*cr;
end
cr

Fuente

Analizando redes de dos modos con Pajek (3/3)

El análisis de la red de 2 modos usando Pajek Parte 3
 Intan Dzikria - My Life, My Dreams

Antes de la Parte 1 y la Parte 2 de esta serie de análisis de red de 2 modos usando el software Pajek Ya te dije acerca de cómo una red simplificada y encontrar centralidad de una red. Ahora bien, en esta parte, quiero decirte acerca de cómo hacer la agrupación jerárquica en una red.

Usando el lenguaje humano simple, cluster es algo que la agrupación de varias personas que tienen mismas características. Por lo tanto, puede ser más fácil de averiguar algo en una gran red social.

En primer lugar, abrir su red simplificada



En segundo lugar, de esta instrucción:
Cluster - Create Complete Cluster
Operations - Network + Cluster - Dissimilarity* - Network based - d5 Correct Euclidian 
Llenar la ventana emergente con 0
Guarde el archivo que es archivo EPS que contiene dendograma de la agrupación
Abra el archivo dendograma utilizando Sra Palabra.

Este dendograma a explicar cómo las personas agrupadas en base a sus sueños para el futuro.



Pero también se puede ver el hierarchi través Pajek con clic en File - Hierarchy - Viet/Edit. A continuación, una pequeña ventana de jerarquía será pop-out y se puede desplegar la raíz y ver que hay dos grupos allí.



Para cerrar el árbol, puede hacer clic en Edit - Change Type en la ventana de visualización jerarquía.



Para conocer el resultado, que tiene que hacer la partición primero con hacer clic en Hierarchy - Make Partition. A continuación, se puede dibujar la red con Draw - Network + First Partition



El resultado es como la imagen de abajo. La red agrupados en dos grupos. Cada grupo presenta a la gente que tiene los mismos sueños futuros.



En realidad, una red con dos racimos se puede reducir. Reducir una red da a conocer la forma en clusters están vinculados entre sí y lo bien que la agrupación resultado es.

Usted puede hacer eso cliqueando Operations - Network + Partition - Shrink Network



Una pequeña ventana pop-up y usted tiene que llenar el número mínimo de líneas entre grupos y el número de racimos que no va a ser reducido.



Después de hacer clic en OK, se puede dibujar la Network + First Partition y el resultado es como esto



Se puede ver en los resultados de la red de contracción que los grupos Claire tienen vínculos con otros grupos. Por ejemplo Claire quiere estar orgullosos padres y ese sueño también en los sueños del grupo Niek.

De acuerdo ... eso es por ahora acerca de la red de 2 modos de analizar el uso de Pajek. Espero que pueda ser útil para usted y si usted tiene alguna pregunta puede comentar abajo. :)

Gracias por leer este artículo

Análisis de cuentas verificadas de Twitter con Gephi

El análisis de 205.718 usuarios verificados Twitter
Desde el año 2008 se crea visualizaciones de red para comprender mejor cómo funcionan las comunidades. En este artículo voy a echar un vistazo a cómo verificada usuarios de Twitter están conectados y quienes son.

Startup Grind



Lo siento por la mala calidad de la imagen. Medio les parece comprimir mucho. Puede descargar el PNG original (5 MB). Para obtener más información sobre el algoritmo, mira la sección de recogida de datos en la parte inferior.

¿Cómo están conectados las cuentas verificadas en Twitter?

Aquí están todas las cuentas de Twitter verificados en una sola imagen. Cada nodo es una cuenta y el tamaño se debe a la cantidad de personas los siguen. Tamaño ajustado con interpolación spline para hacer las cuentas con menos seguidores más visible y reducir los tamaños de los que tienen el mayor número de seguidores. De lo contrario las cuentas con millones de seguidores serían mayores que los de las propias comunidades.

Nombrando las sub-comunidades

La imagen se ve bien, pero se vuelve interesante cuando se va más profundo. En cuanto a cada uno de estos nudos de cuentas para entender de qué se trata. Si tienen algo en común. O si no son más que la gente al azar siguientes entre sí.


En primer lugar tratamos de ver de que se tratan estos grupos


Como se puede ver en la imagen grande más adelante, los grupos no son tan desconectados como se ven sin las conexiones (bordes). Sin embargo, el algoritmo todavía era capaz de encontrar comunidades muy unidas. Y si bien hay muchas comunidades transversales siguientes, la mayoría de los siguientes ocurren entre las propias comunidades.
Todo el gráfico es de US céntrica. Ese gran nodo de color marrón en el medio de todo. Eso es @twitter. Y el azul claro se superpone con, que es @youtube. La otra gran luz azul en la parte inferior derecha media son celebridades. @katyperry, @justinbieber, @theellenshow, @rihanna, @ladygaga y así sucesivamente. Hay mucho más en juego en este sector centro, pero en esta visualización es difícil de ver. Voy a echar un vistazo más de cerca más adelante en este artículo.
Mientras que es posible diferenciar entre grupos de actualidad en el centro, para el resto de las sub-communites se agrupan principalmente regional. Esto tiene que ver con el menor número de cuentas verificadas para los demás países. Si pongo cada uno de estos grupos en su propio gráfico, estoy seguro de que será posible obtener una imagen más clara de cómo están conectados en sí mismo y no sólo una gota.
Alemania, Austria y Suiza están conectados de forma natural por el lenguaje. Canadá es la extensión de Estados Unidos hacia la izquierda, Reino Unido hacia la derecha y Australia en la parte inferior derecha. Una vez más, el lenguaje como un factor para ello. No es la cercanía cultural. Pero esto existe para más grupos.
Otro grupo de lengua española es de color verde en la parte superior. Incluso después de varios intentos, no fue capaz de encontrar otra conexión entre todas las cuentas agrupadas allí. Son de diferentes países de América del Sur, así como los medios de comunicación de Estados Unidos en español y más. Cerca de México, Argentina y España. Brasil, con cierta distancia.
Turquía está lejos de todos los demás. Especialmente la UE, que está justo al lado de la ONU y un poco de política del Reino Unido. Más cerca de la UE no es Israel. Me sorprendió que aparece cerca de Portugal, Finlandia, Suecia y Dinamarca. En el otro lado Rusia. Y justo detrás de Rusia Qatar y Arabia Saudita.
Francia tiene una posición de fuera en la parte superior derecha, alguna conexión con Italia y España. Lejos de la UE y Alemania. Pero no todos Alemania. Hay otro sub-comunidad alemana. Fútbol. O mejor: Bundesliga. Or está cerca de los Países Bajos también. Y, por supuesto, con el fútbol en el Reino Unido. Hay otro grupo de sub-comunidades cercanas: eSport. Y eSport pasa por contracción de los desarrolladores de juegos que se sientan en el borde de la burbuja de los Estados Unidos.
En el borde derecho no es Asia con muchas varias comunidades más pequeñas. Todavía no sé por qué Japón tiene dos sub-comunidades que no están tan bien conectadas entre sí.


205 mil cuentas de twitter verificadas y 19 millones de conexiones entre ellas

Viaje a través de la gráfica [video, alemán]

En el video Voy a través de los grandes sub-comunidades y hablar de lo que creo que son y por qué son exhibidas como un grupo distinto.

Lugares más populares

Top 25 lugares (como las personas que escriban en su biografía)

Twitter no tiene la función de autocompletar para los datos de localización como Facebook lo hace. La gente puede poner en el campo de ubicación de lo que quieran. Como resultado no es tan grande como para trabajar con los datos. Como se puede ver en el gráfico anterior en el Top 25 lugares tienen varias ortografías diferentes. Londres no es más popular que Los Ángeles, pero más personas utilizan el mismo formulario. Y éstas son sólo las formas más populares, para cada ciudad hay muchas formas diferentes de escribir ellos. Algunos añaden el estado, algunos del país, algunos utilizan el barrio y mucho más.
Tal vez voy a tener tiempo para mirar en todas estas formas de un día o encontrar una herramienta que los normaliza. Por ahora creo que la nube de la palabra es suficiente, ya que no se preocupa por la ubicación exacta de la palabra de la cadena.

La recogida de datos

Cuando llegó a mi cuenta de Twitter verificada, he notado que @verified comenzó a seguirme. En cuanto a sus seguidores que es fácil de adivinar que sigue cada cuenta verificada en Twitter. Por lo tanto, puedo decir que hay 206 000 cuentas verificadas en Twitter en el momento. Y comprueben alrededor de 1.000 cuentas cada día. Puede haber algunas cuentas que bloquean @verified y por lo tanto no aparecen en sus seguidores pero supongo que la cantidad es tan pequeña que puedo ignorarlo. El uso de la cuenta como punto de partida que es posible recoger la red de cuentas verificadas en Twitter.
He utilizado una versión modificada del comando Python twecoll herramienta de línea por JP de Vooght para recoger una lista de todas las cuentas seguido por @verified. Luego, la herramienta fue a través de todas estas cuentas 205k y miró a los que siguen. Para un conjunto de datos que he limitado a las cuentas que siguen a menos de 10 000 cuentas y un segundo conjunto de datos de cuentas que siguen a menos de 1 000 cuentas. Hay dos razones para esto. Las personas más administraciones siguen, el menos importante se vuelve cada conexión. La segunda razón es la limitación técnica de mi equipo (4670k i5 a 4,2GHz, 16GB de RAM, 250 GB de Samsung EVO 840, GTX 760). A pesar de que funciona con el conjunto de datos más grande, no es divertido para trabajar, porque todo lleva más tiempo.
La recolección de datos funcionó en una Frambuesa Pi 2 de 7 días a partir de 22. 28/08/2016 con sólo algunas horas de pausa debido a los errores que tenía que corregir manualmente. Debido al tiempo de largo plazo hay algunas inconsistencias en los datos cuando la gente sigue o unfollowed alguien en ese período de tiempo. En esta escala no hace una diferencia. Hay algunas cuentas en el conjunto de datos que no se verifica más. Tomé un vistazo más de cerca a las 36 cuentas. Estas fueron todas las cuentas que han perdido su estado verificado en un día de cada cuentas verificadas. La mitad de ellos elimina su cuenta / suspendieron, la otra mitad fue privado y perdió su estado verificado por eso.
El conjunto de datos grande, <10 000 seguidores, dispone de 205 718 cuentas de Twitter y 45 302 877 conexiones entre ellos. El conjunto de datos más pequeña, <1 000 seguidores, tiene 205.718 cuentas, así y 19 176 260 conexiones.
Yo uso Gephi para visualizar los datos. Pié el proceso de obtención de los datos en un estado útil. OpenOrd (25, 25, 25, 10, 15; cortar 0,8; 500 iteraciones) me dio la disposición más útil. Los colores son calculados por el algoritmo de modularidad. Puedo cambiar el tamaño de los nodos de vez en cuando. Si no se ha señalado que son seguidores.

Algunas Estadísticas generales

Cargué las estadísticas de las cuentas verificadas 205K en Excel e ignore las conexiones. Estos números no ignoran todas las cuentas, no importa cuántas cuentas que siguen.
Cuando presenté mi cuenta para la verificación, me dijeron que por algunos contactos que no tienen suficientes seguidores. De hecho cuentas verificadas tienen un promedio de 117 845 seguidores. Pero hay una gran cola larga. La mediana es a los 9 370 seguidores. Hay más de 100 mil cuentas con menos de 10 000 seguidores. Y el resto no tiene que mucho más. El promedio se sesgada por las cuentas de mega como @katyperry con 92.2m seguidores. Hay 188 cuentas verificadas con más de 10 millones de seguidores y 4 330 cuentas verificadas con más de 1 millón de seguidores. Hay una cuenta verificada con sólo dos seguidores.

Verified Twitter account with fewest followers: @ghisperrier. 2 Followers.
Verified Twitter account with most followers: @katyperry 92.2m

— Luca 🔨 (@luca) 29 de agosto de 2016

Pero, ¿cuántas cuentas se atienen a las cuentas verificadas? Por término medio se siguen las cuentas de 2031. Pero de nuevo nos dieron algunos seguidores de mega. Una cuenta sigue cuentas 3.6m. La mediana se encuentra en una muy manejables 475 seguidores. Personalmente siento que todo por encima de 5 000 seguidores no se sigue de forma manual. Después de todo el mundo es una táctica frecuentemente usada para generar siguientes. Así que muchas personas hicieron que Twitter introdujo un límite que sólo se puede seguir un cierto porcentaje representa más de lo que sigue (Base Límite 5 000, límite diario 1 000). Esto dio lugar a una nueva táctica seguimiento y no seguir. Las cuentas siguen a tantas personas como sea posible y unfollow todo aquel que no siga de nuevo en x días. Estoy divagando. Hay 3 551 cuentas que siguen a nadie y 33 328 cuentas que siguen a otros a menos de 100. Una cuenta volvió a los siguientes negativos de -28. Supongo que eso es un error con la base de datos de Twitter.


Lo siento por la elección del eje.

Las cuentas verificadas han publicado una cantidad acumulada de 2 488 119 264 actualizaciones de estado. 12 095 en promedio. La mediana de 4 a 191. Sin cuenta la edad, estos números no significan nada. La mayoría de las cuentas son cuentas hablador de apoyo por parte de empresas. AmexOffers ha publicado tweets de 5,2 millones. Por supuesto que hay muchas cuentas verificadas, las cuales no han twitteado en absoluto. O eliminado todo. 131 para darle el número. 25 y 764 cuentas verificadas registraron menos de 500 tweets.



La mayoría de las cuentas de Twitter verificadas fueron creados en 2009. El gráfico anterior es bastante sorprendente si nos fijamos en la popularidad general de Twitter.



De lunes a domingo casi dos veces el número de cuentas se crearon que en el fin de semana. Necesito un conjunto de datos para compararla con antes de que yo puedo decir si esto es más probable que provenga de la pauta general de uso de Twitter o si estas cuentas son cuentas de trabajo es más probable que a menudo son creadas por las agencias.

Siete aprendizajes

• Las cuentas verificadas están conectados regionalmente primera, segunda y temáticamente
• El lenguaje es una característica importante mutua
• Las cuentas más seguidas son las celebridades más populares
• La política y la tecnología tienen más seguidores entre cuentas verificadas
• Las cuentas de redes son influyentes de todo el mundo
• La mayoría de las cuentas verificadas son muy activos, pero siguen pocas personas
• Compartir grandes gráficos es complicada

Explora usted mismo y dime lo que has encontrado

Usted puede explorar la gráfica, ya sea como una versión GigaPan, que carga de forma dinámica o ir a por todas y tratar la versión de 30 MB sigma.js, que puede bloquear el navegador y toma algunos minutos en cargar, pero tiene una función de búsqueda. O sin búsqueda, pero es mejor utilizar el zoom. Ambos tienen su versión sigma.js eje Y invertida, lo que está en la parte superior de las capturas de pantalla aquí, está en el fondo allí.

Visualización zoomable en Gigapan
Compartir sus ideas en los comentarios oa través de Twitter.

Colabore conmigo

Quiero escribir artículos acerca de cada sub-comunidades y necesitan la ayuda de personas que ya están conociendo el grupo respectivo. Si quieres colaborar conmigo en uno de estos artículos por favor envíeme un correo electrónico con el grupo está interesado en: lucahammer@gmail.com. Entonces le envía un archivo con los datos establecidos para ese grupo, una breve guía de cómo se puede trabajar con él y un enlace de Google Docs en el que podemos trabajar el artículo juntos. Puede publicar el artículo final en su propio blog / medio / publicación o que publicarla aquí.


Aquí está la guía de cómo alguien puede analizar las redes de Twitter con Gephi

Red de tronos en Games of Thrones

Las matemáticas de Juego de Tronos

La Red de Tronos

¿Jon Snow es realmente muerto? Tyrion Lannister será continuar su difícil alianza con Daenerys Targaryen y sobrevivir a su hermana la ira de Cersei? Será Sansa Stark escapar de la sádica Ramsay Bolton y tomar su lugar como reina del Norte?

Estas preguntas, en la superficie, no tienen nada que ver con las matemáticas. Sin embargo, según un estudio reciente aplicación de la teoría de redes para el Juego de Tronos, Jon, Tyrion y Sansa son demostrablemente los personajes centrales de la saga.

Para aquellos de ustedes que viven en una cueva, Juego de Tronos (GOT, para abreviar) es uno de los programas más populares de televisión, basada en las novelas muy populares por George R. R. Martin. GOT es un hilo de fantasía ambientado en las tierras de Poniente y Essos. La historia contiene la variedad usual de duelo de reyes y reinas, dragones y magia. A diferencia de señor de los anillos, sin embargo, la historia es completamente adulto de sexo y violencia a raudales. personajes principales mueren. Mucho. Hay gran elenco que emana de las principales familias reales que disputan el Trono de Hierro.


El mundo de GOT
El autor principal del breve documento de la Red de Tronos es un co-autor de la mina, Andrew Beveridge del Macalester College. Andrew es un teórico de la gráfica, con un fondo tanto en matemáticas teóricas y aplicadas.


El Dr. Andrew Beveridge

En el blog de hoy, voy a dar un recorrido por el papel, sus implicaciones, y un poco de discusión sobre por qué los asuntos de trabajo. La cita completa de este documento es:

A. Beveridge, J. Shan, Red de Tronos, Matemáticas Revista Horizontes, 23 (2016) 18-22.

Ver también la página web de la Red de Trono que contiene conjuntos de datos, artículos sobre su estudio, y más. También hay hashtag de Twitter: #NetworkOfThrones

Los datos de GOT

Podemos ver los personajes de GOT como nodos en una red, con los bordes entre ellas si comparten lazos sociales. Este es un ejemplo de una red social, aunque sea ficticia. Las redes sociales se han estudiado durante décadas, con un renovado interés en ellos últimamente debido al predominio de on-line de las redes sociales como Facebook y Twitter.

Lo que está ajustado los datos de redes sociales conseguidos? Se compone de 107 caracteres desde el tercer libro de la serie Tormenta de Espadas (elegidos ya que los personajes y sus relaciones habían madurado para entonces). Los autores utilizaron algoritmos para extraer la versión electrónica del libro, en busca de conexiones entre los personajes. Si sus nombres aparecieron dentro de las 15 palabras de uno al otro, entonces se colocan un borde entre ellos. Esta es la técnica de minería de datos común utilizando la frecuencia de palabras: cuanto más a menudo el co-aparición de dos nombres, el más pesado el borde une.

Aquí está la red descubrieron (una figura del papel):



Este relativamente pequeño ejemplo de red social. científicos de red (como yo) estudian a menudo muy grandes redes como Facebook y Twitter, con la esperanza de explotar sus propiedades globales y locales. Estas redes tienen cientos de millones de nodos. He escrito los blogs anteriores que hablan de tales en el mundo real, las redes complejas. En 2008, escribí un libro sobre una de las redes complejas primeros estudiados: el gráfico de red.

Observe que la red anterior se divide en las comunidades, se centró en los actores clave como Robb, John, Tyrion, etc. Los autores utilizaron varios algoritmos para detectar estas comunidades y enumerarlos. Ellos usan el concepto de modularidad, que compara la red para al azar, donde se espera ninguna estructura de la comunidad. La modularidad da una partición gráfica, lo que resulta en los grupos de colores que se ven más arriba en la figura.

Por cierto, la detección de la comunidad es un importante problema abierto en la ciencia de la red. Tenemos buenos heurísticos para el problema, pero no universalmente aceptada metodología o incluso la definición de lo que comprende una comunidad. La mayoría de los enfoques que saben utilizar las técnicas de la teoría de grafos espectral. A grandes rasgos, las comunidades deben ser subgraphs donde los más bordes interior y luego salir al exterior. La figura anterior recuerda el famoso gráfico de Zachary Club de Karate, que se presentó en uno de los primeros trabajos sobre la detección de la comunidad.


El grafo del club de karate de Zachary, a partir de la tesis doctoral de Wayne Zachary en 1972. Los nodos corresponden a los miembros de un club de karate real, y los bordes representan sus relaciones sociales. Los instructores del club son los nodos en negrilla 1 y 34. Después de una disputa entre ellos, los instructores formados cada uno su propio club. Podemos ver aquí la comunidad formada alrededor de cada uno de los nodos 1 y 34.

Una vez que se detectaron las comunidades, Beveridge y Shan miden la importancia de las personas en cada comunidad GOT por varios métodos. Un enfoque obvio es buscar en grados; el grado de un nodo es el número de bordes se unió a ella. Si los nodos están conectados a muchos otros, entonces es probable importante. Pero grado no siempre es la mejor medida de centralidad.

Puede ser importante al ser conectado a una persona importante. Supongamos que Barack Obama me siguió en Twitter. Eso sería sólo un nuevo seguidor (que sería subir mi título por uno), pero probablemente me habría vuelto muy populares en Twitter como Obama es un individuo tan poderoso en la red social. Otros verían esa conexión importante, y también me siga.

Un enfoque inteligente para evitar los problemas con la centralidad de grado es el uso de PageRank, que es un algoritmo desarrollado por Sergey Brin y Larry Page de Google fama. PageRank permite a Google para clasificar las páginas web y la velocidad de búsqueda en la Web.


Larry Page y Sergey Brin, fundadores de Google.

Las matemáticas subyacentes de PageRank tiene que ver con paseos aleatorios en las redes, similar a la forma aleatoria surfistas se propagan a través de una red. Precisamente, el PageRank es un ejemplo de una cadena de Markov discreta ergódico. surfistas aleatorias siguen los enlaces, pero de vez en cuando teletransportarse a los vértices aleatorios. El PageRank de un nodo es la probabilidad de que es visitado por un surfista al azar con el teletransporte. PageRank es ahora ampliamente reconocido como una forma de detectar los nodos centrales en una red, e incluso tiene aplicaciones en la biología de sistemas.

Lo que la matemática nos dice

Beveridge y Shan al descubierto algunos resultados interesantes. Usando sólo su análisis matemático, las principales conclusiones son que Tyrion, Jon, y Sansa son actores clave en la red social. Tyrion no es ninguna sorpresa para los fans de la serie o los libros, ni Jon. Pero Sansa es un personaje nuevo e interesante. Su apodo es pequeño pájaro, que hace hincapié en su papel hasta el momento como un peón en los planes de los demás. Creo que vamos a ver a Sansa emerger como un jugador de gran alcance en las próximas temporadas. Al menos, espero que ella será, si no fuera matarla, que el espectáculo le gusta hacer a menudo con sus personajes principales!

Otra interesante conclusión deriva únicamente de las matemáticas es que Daenerys Targerion es influyente, pero sólo a nivel local. Cualquier fan de GOT sabe que, pero es fascinante ver como que surge de manera objetiva en el análisis de datos. Ella no ha interactuado mucho con los otros jugadores en la red Poniente. Esto también va a cambiar, creo. Una de mis escenas favoritas de la serie es cuando conoce a Tyrion. ¡Su famosa cita de romper la rueda me dio escalofríos!



La temporada 6 de Juego de Tronos vuelve a HBO el 24 de abril.

La ficción se encuentra con grandes volúmenes de datos

El estudio de Beveridge y Shan es un buen recordatorio de las matemáticas papel tiene que desempeñar en la cultura popular. El uso de herramientas conocidas de las redes, los autores llegan a conclusiones sorprendentes sobre un programa de televisión y la obra literaria. Llamarlo el nuevo campo de los grandes volúmenes de datos de ficción.

Lo bueno es que se puede replicar el estudio con cualquier red social ficticio de su libro favorito o una serie. Los caracteres más el mejor, así que funciona como el señor de los anillos serían buenos candidatos para este tipo de análisis. He encontrado un tal documento, publicado este mes de abril por algunos físicos brasileños, el estudio de personajes del Señor de los Anillos, El Hobbit y El Silmarillion.


La estructura de la comunidad a partir de los 618 personajes y sus 19, 462 vínculos sociales en el universo de Tolkien. M. A. Ribeiro, M.L.P. Andruchiw, S. E. Pinto,  The complex social network of the Lord of the Rings, Bras. Ensino, Fis, 28 (1) (2016)

A partir de estos y otros estudios, se nos recuerda una vez más la importancia de la aritmética. Nos frecuente sitios Rotten Tomatoes y Box Office Mojo al comprobar el éxito crítico y financiero importante de películas. ciencia de las redes de datos y grandes nos pueden mostrar mucho más que los rendimientos de taquilla o promedios simples de las puntuaciones del crítico: pueden revelar patrones y los matices de la historia que no se daría cuenta de ordinario. También ofrecen alternativas de apoyo (por supuesto, no sustituir) el análisis literario tradicional.

Matemáticas a través de su uso en grandes volúmenes de datos que ya se utiliza en muchos ámbitos de toma de decisiones como las finanzas y la atención sanitaria. Tal vez la próxima aplicación de las matemáticas es el entretenimiento en forma de análisis de personajes de la literatura, la televisión y las películas.

¿No sería eso algo?

Anthony Bonato