jueves, 31 de mayo de 2018

Ridiculogramas, bolas de pelo y complejidad: Reflexiones para rederos

Ridículogramas: un diálogo ridículo

Petter Holme


Si eres un científico de redes, o andas juntado con uno, probablemente hayas escuchado acerca de los ridículogramas. Es una palabra despectiva irónica para tramas de redes enormes destinadas a impresionar por su complejidad. Tengo un vago recuerdo de alguien que acreditó a Marc Vidal por haberlo acuñado. En esta publicación de blog, exploraremos si realmente son tan ridículos en un diálogo entre mi gemelo Vidalesque y yo desde la tierra de las sombras.Las visualizaciones de grafos realmente dan una buena sensación para el tamaño y la complejidad de un sistema en red. A menudo también se puede entender la estructura a gran escala, gracias al ingenio de los algoritmos de visualización. Es posible que solo deba dejar su programa funcionando durante la noche. Anexo 1: Una red de 8507 nodos de flujos de pacientes entre unidades de un sistema regional de atención médica. Diferentes regiones geográficas salen como clusters en la red.



 

En serio hombre ¿Qué pasa si la trama es simplemente una bola de pelo sin estructura? Si lo ejecuta de la noche a la mañana y no ve ninguna estructura, ¿cómo puede estar seguro de que no lo hay? ¿Tendría que ejecutar el programa en una computadora cuántica de un millón de núcleos para verlo?

Si se trata simplemente de una bola de pelo sin estructura, ¿no es eso también interesante? Para una red lo suficientemente grande, los tipos de estructuras que son visibles en un ridículo son solo de todos modos mesoscópicos: estructura de la comunidad, estructura núcleo-periferia, otras fluctuaciones de densidad sin nombre,.

Puede haber todo tipo de otras estructuras, que debe medir con sus habilidades netsci ninja. Pero sí, es un fastidio que la mayoría del software disponible no te diga cuán bien convergente es el argumento. Uso para marcar algunos nodos, tomar capturas de pantalla y comprobar cuánto difieren a medida que pasan las horas.
Amigo, ahora entiendo por qué se llama ridiculograma! Eso es como revisar fotos del cielo para el Planeta X. . Además, si ejecuta el programa nuevamente, no verá lo mismo.
Si ejecutas esos programas de (algoritmo de energía de) relajación de resortes dos veces, no dan exactamente las mismas parcelas, sino parcelas que dan la misma impresión. 
Eso no suena muy exacto, ¿verdad? 
Por supuesto, son complementarios al resto de los análisis. Eres ese tipo de persona que piensa que cada trama en un documento debe corresponderse con un punto que hagas en el texto. ¡Las figuras podrían ser mucho más que eso! Si escribes un artículo sobre una especie animal peluda de cinco patas que descubriste, supongo que no pondrás una foto, porque podría describirse en el texto. .

 [aquí el diálogo se sale de control y se convierte en blasfemias y violencia]

martes, 29 de mayo de 2018

Redes de contratación de docentes limita la difusión de ideas

El prestigio impulsa la desigualdad epistémica en la difusión de las ideas científicas

Allison C. Morgan, Dimitrios Economou, Samuel F. Way, Aaron Clauset
PDF










    
La difusión de ideas en la comunidad científica a menudo se ve como una competencia, en la cual las buenas ideas se extienden aún más debido a una mayor aptitud intrínseca. Como resultado, comúnmente se cree que el lugar de publicación y los recuentos de citas se correlacionan con la importancia y el impacto. Sin embargo, se sabe relativamente poco sobre cómo los factores estructurales influyen en la difusión de las ideas, y específicamente cómo se origina una idea puede influir en cómo se propaga. Aquí, investigamos el papel de las redes de contratación de docentes, que encarnan el conjunto de transiciones de los investigadores de doctorado a las instituciones docentes, en la conformación de la difusión de ideas en ciencias de la computación, y la importancia de en qué parte de la red se origina una idea. Consideramos datos completos sobre los eventos de contratación de 5.032 docentes en los 205 departamentos de ciencias de la computación que otorgan doctorado en los Estados Unidos y Canadá, y sobre los tiempos y los títulos de 200.476 publicaciones asociadas. Analizando tres temas de investigación populares, demostramos empíricamente que la contratación de docentes juega un papel importante en impulsar la difusión de ideas en toda la comunidad. Luego utilizamos modelos de epidemia para simular la propagación genérica de ideas de investigación y cuantificar las consecuencias de dónde se origina una idea en su difusión a largo plazo a través de la red. Encontramos que la investigación de instituciones de prestigio se extiende más rápida y completamente que un trabajo de calidad similar originado en instituciones menos prestigiosas. Nuestros análisis establecen las compensaciones teóricas entre el prestigio de la universidad y la calidad de las ideas necesarias para una circulación eficiente. Estos resultados sugieren un límite inferior para la desigualdad epistémica, identifican un mecanismo para la ventaja epistémica persistente observada para las instituciones de élite y resaltan las limitaciones para los ideales meritocráticos.



sábado, 26 de mayo de 2018

Jerarquía y superposición de comunidades en redes complejas

Detectar la estructura sobrepuesta y jerárquica de comunidades en complejas redes

Andrea Lancichinetti, Santo Fortunato y János Kertész
Publicado el 10 de marzo de 2009 • IOP Publishing and Deutsche Physikalische Gesellschaft
New Journal of Physics


Resumen
Muchas redes en la naturaleza, la sociedad y la tecnología se caracterizan por un nivel de organización mesoscópico, con grupos de nodos que forman unidades estrechamente conectadas, llamadas comunidades o módulos, que están débilmente vinculadas entre sí. Descubrir esta estructura de comunidad es uno de los problemas más importantes en el campo de las redes complejas. Las redes a menudo muestran una organización jerárquica, con comunidades integradas en otras comunidades; además, los nodos se pueden compartir entre diferentes comunidades. Aquí, presentamos el primer algoritmo que encuentra comunidades superpuestas y la estructura jerárquica. El método se basa en la optimización local de una función de aptitud. La estructura de la comunidad se revela por los picos en el histograma de la aptitud física. La resolución puede ajustarse mediante un parámetro que permita investigar los diferentes niveles jerárquicos de la organización. Las pruebas en redes reales y artificiales dan excelentes resultados.

1. Introducción

El estudio de las redes como el 'andamio de la complejidad' ha demostrado ser muy exitoso para comprender tanto la estructura como la función de muchos sistemas naturales y artificiales [1] - [5]. Una característica común de las redes complejas es la estructura de la comunidad [6] - [9], es decir, la existencia de grupos de nodos tales que los nodos dentro de un grupo están mucho más conectados entre sí que con el resto de la red. Los módulos o las comunidades reflejan las relaciones topológicas entre los elementos del sistema subyacente y representan las entidades funcionales. Por ejemplo, las comunidades pueden ser grupos de personas relacionadas en las redes sociales [6, 10, 11], conjuntos de páginas web que tratan el mismo tema [12], categorías taxonómicas en redes tróficas [13, 14], rutas bioquímicas en redes metabólicas [15] - [17], etc. Por lo tanto, la identificación de las comunidades es de importancia central, pero sigue siendo una tarea formidable.
La solución se ve obstaculizada por el hecho de que la organización de redes en el nivel modular "mesoscópico" generalmente es altamente no trivial, por al menos dos razones. En primer lugar, a menudo existe toda una jerarquía de módulos, porque las comunidades están anidadas: las comunidades pequeñas construyen las más grandes, que a su vez se agrupan para formar otras aún más grandes, etc. Un ejemplo podría ser la organización de una empresa grande, y ha sido argumentó que la complejidad de la vida también se puede asignar a una jerarquía de redes [18]. La forma jerárquica de organización puede ser muy eficiente, y los módulos se encargan de las funciones específicas del sistema [19]. En presencia de una jerarquía, el concepto de estructura de la comunidad se vuelve más rico y exige un método que sea capaz de detectar todos los niveles modulares, no solo uno. La agrupación jerárquica es una técnica bien conocida en el análisis de redes sociales [20, 21], la biología [22] y las finanzas [23]. A partir de una partición en la que cada nodo es su propia comunidad, o todos los nodos están en la misma comunidad, se fusionan o dividen los clústeres según una medida topológica de similitud entre los nodos. De esta manera, uno construye un árbol jerárquico de particiones, llamado dendrograma. Aunque este método produce naturalmente una jerarquía de particiones, nada se conoce a priori sobre sus cualidades. La modularidad de Newman y Girvan [24] es una medida de la calidad de una partición, pero puede identificar una única partición, es decir, la que corresponde al valor más grande de la medida. Recientemente, los académicos comenzaron a enfocarse en el problema de identificar jerarquías significativas [19, 25].
Una segunda dificultad es causada por el hecho de que los nodos a menudo pertenecen a más de un módulo, lo que resulta en la superposición de comunidades [17], [26] - [29]. Por ejemplo, las personas pertenecen a diferentes comunidades sociales, dependiendo de sus familias, amigos, profesiones, pasatiempos, etc. Los nodos que pertenecen a más de una comunidad son un problema para los métodos estándar y reducen la calidad de los módulos detectados. Además, esto oculta información importante, y a menudo conduce a clasificaciones erróneas. El problema de la superposición de las comunidades se expuso en [17], donde también se ofreció una solución. El método propuesto se basa en la percolación de la camarilla: una k-clique (un subgrafo completo de k nodos) se extiende a través de la red a través de otras camarillas con k-1 nodos comunes. De esta forma, se puede llegar a un conjunto de nodos, que se identifica como una comunidad. Un nodo puede participar en más de una de esas unidades, por lo tanto, las superposiciones ocurren naturalmente. El método, sin embargo, no es adecuado para la detección de la estructura jerárquica, ya que una vez que se especifica el tamaño k de la camarilla, en su mayoría se puede recuperar una sola estructura modular. En la figura 1, mostramos distintas redes con estructura jerárquica y comunidades superpuestas, aunque debe enfatizarse que estas características a menudo ocurren simultáneamente.




Figura 1. Parte superior: una red con una estructura jerárquica. Cada uno de los cuatro grupos grandes está formado por 128 nodos y tiene una subdivisión interna en cuatro clústeres con 32 nodos. Abajo: comunidades superpuestas. Los nodos verdes están relacionados topológicamente con más grupos.

Con el fin de proporcionar la información más exhaustiva sobre la estructura modular de un grafo, un buen algoritmo debería ser capaz de detectar tanto comunidades superpuestas como jerarquías entre ellas. En este documento, presentamos un marco que cumple estas dos demandas. El método realiza una exploración local de la red, buscando la comunidad natural de cada nodo. Durante el procedimiento, los nodos se pueden visitar muchas veces, sin importar si se han asignado a una comunidad o no. De esta manera, las comunidades superpuestas se recuperan naturalmente. La variación de un parámetro de resolución, que determina el tamaño promedio de las comunidades, permite explorar todos los niveles jerárquicos de la red.

2. El método

La suposición básica detrás de nuestro algoritmo es que las comunidades son esencialmente estructuras locales, que involucran los nodos que pertenecen a los módulos mismos y como mucho un vecindario extendido de ellos. Esto es ciertamente plausible para redes grandes, donde cada nodo no depende de la mayoría de sus pares. En el grafo de enlace de la WWW, por ejemplo, uno ni siquiera tiene una percepción de qué tan grande es la red, y las comunidades temáticas se forman basándose solo en información parcial sobre el grafo. Del mismo modo, las comunidades sociales son estructuras locales sin ninguna referencia a la humanidad como un todo.
Aquí, una comunidad es un subgrafo identificado por la maximización de una propiedad o aptitud de sus nodos. Hemos probado varias opciones para la forma de la condición física y obtuvimos los mejores resultados con la expresión simple



dónde  y  son los grados totales internos y externos de los nodos del módulo , y α es un parámetro positivo de valor real, que controla el tamaño de las comunidades. El grado interno de un módulo equivale al doble del número de enlaces internos del módulo. El grado externo es el número de enlaces que unen a cada miembro del módulo con el resto del grafo. El objetivo de este documento es determinar un subgrafo que comience en el nodo A de manera que la inclusión de un nuevo nodo o la eliminación de un nodo del subgrafo disminuya. Llamamos a este subgrafo la comunidad natural del nodo A. Esto equivale a determinar los máximos locales para la función de aptitud para un α determinado. El máximo verdadero para cada nodo corresponde trivialmente a toda la red, porque en este caso y el valor de es el más grande que la medida puede alcanzar para un α determinado. La idea de detectar comunidades mediante una optimización local de alguna métrica ya se aplicó anteriormente [26, 27, 30, 31].

Es útil introducir el concepto de aptitud del nodo. Dada una función de aptitud, la aptitud de un nodo A con respecto a un subgrafo , se define como la variación de la aptitud del subgrafo  con y sin el nodo A, es decir.

Equation (2)

En la ecuación (2), el símbolo () indica el subgrafo obtenido del módulo  con el nodo A dentro (afuera).

La comunidad natural del nodo A se identifica con el siguiente procedimiento. Supongamos que hemos cubierto un subgrafo  que incluye el nodo A. Inicialmente,  se identifica con el nodo A (). Cada iteración del algoritmo consta de los siguientes pasos:

La comunidad natural del nodo A se identifica con el siguiente procedimiento. Supongamos que hemos cubierto un subgrafo que incluye el nodo A. Inicialmente, se identifica con el nodo A (). Cada iteración del algoritmo consta de los siguientes pasos:

1. un bucle se realiza sobre todos los nodos vecinos de  no incluidos en ;
2. se agrega el vecino con la aptitud más grande a , produciendo un subgrafo  más grande;
3. la aptitud de cada nodo de  es recalculada;
4. si un nodo tiene una aptitud física negativa, se elimina de este , produciendo un nuevo subgrafo ;
5. si ocurre 4, repita desde 3, de lo contrario repita desde 1 para el subgrafo .

El proceso se detiene cuando los nodos examinados en el paso 1 tienen una aptitud física negativa (figura 2). Este procedimiento corresponde a una especie de optimización codiciosa de la función de aptitud, ya que en cada movimiento se busca el mayor aumento posible. Otras recetas pueden ser adoptadas también. Por ejemplo, uno podría retroceder los nodos con una aptitud física negativa solo cuando el clúster deja de crecer y / o incluir en el clúster el primer nodo vecino que produce un aumento de la aptitud. Dichas recetas pueden conducir a clústeres de acondicionamiento físico más altos en un tiempo más corto, y merecen investigaciones en profundidad, que dejamos para el trabajo futuro.

Figura 2. Ejemplo esquemático de comunidad natural para un nodo (punto azul celeste en la figura) según nuestra definición. Los nodos azules son los otros miembros del grupo y tienen una aptitud física positiva dentro del grupo, mientras que los nodos rojos tienen una aptitud física negativa con respecto al grupo.

Definimos una cubierta del grafo como un conjunto de clústeres de modo que cada nodo se asigna a al menos un clúster. Esta es una extensión del concepto tradicional de partición de grafos (en la cual cada nodo pertenece a un solo grupo), para tener en cuenta posibles comunidades superpuestas. En nuestro caso, detectar una cobertura equivale a descubrir la comunidad natural de cada nodo del grafo que se estudia. La forma directa de lograr esto es repetir el procedimiento anterior para cada nodo individual. Esto es, sin embargo, computacionalmente costoso. Las comunidades naturales de muchos nodos a menudo coinciden, por lo que la mayor parte del tiempo de la computadora se utiliza para redescubrir los mismos módulos una y otra vez. Una salida económica se puede resumir de la siguiente manera:

1. elige un nodo A al azar;
2. detectar la comunidad natural del nodo A;
3. elegir al azar un nodo B aún no asignado a ningún grupo;
4. detectar la comunidad natural del nodo B, explorando todos los nodos independientemente de su posible pertenencia a otros grupos;
5. repetir desde 3.

El algoritmo se detiene cuando todos los nodos han sido asignados a al menos un grupo. Nuestra receta está justificada por el siguiente argumento. Los nodos de cada comunidad se superponen con otras comunidades o no. La comunidad fue explorada alrededor de un nodo específico; si uno elige cualquiera de los otros nodos, uno recuperaría la misma comunidad o una de las posibles comunidades superpuestas. Pero este último también se puede encontrar si uno parte de nodos que se encuentran fuera de la comunidad y no se superponen con él. De esta forma, uno debería recuperar todos los módulos sin necesidad de comenzar desde cada nodo. Al mismo tiempo, se cubrirán nodos superpuestos durante la construcción de cada comunidad a la que pertenecen, ya que es posible incluir nodos ya asignados a otros módulos. Extensas pruebas numéricas muestran que la pérdida de precisión es mínima si se procede como sugerimos en lugar de encontrar la comunidad natural de todos los nodos. Observamos que el procedimiento tiene cierto grado de estocasticidad, debido a la elección aleatoria de las semillas de nodo de las cuales las comunidades están cerradas. Este problema se analiza en el apéndice A.

El parámetro α sintoniza la resolución del método. La fijación de α significa establecer la escala a la que estamos mirando la red. Los valores grandes de α producen comunidades muy pequeñas, los valores pequeños en cambio proporcionan módulos grandes. Si α es lo suficientemente pequeño, todos los nodos terminan en el mismo clúster, la red misma. Hemos encontrado que, en la mayoría de los casos, para α <0.5, solo hay una comunidad; para α> 2, uno recupera las comunidades más pequeñas. Una elección natural es α = 1, ya que es la relación entre el grado externo y el grado total de la comunidad. Esto corresponde a la llamada definición débil de comunidad introducida por Radicchi et al [32]. Encontramos que, en la mayoría de los casos, la cobertura encontrada para α = 1 es relevante, por lo que brinda información útil sobre la estructura de la comunidad real del grafo en cuestión. Mantener un valor específico de α significa restringir la resolución del método, al igual que sucede al optimizar la modularidad de Newman-Girvan [33, 34]. Sin embargo, no se puede saber a priori qué tan grandes son las comunidades, ya que esta es una de las incógnitas del problema, por lo que es necesario comparar las coberturas obtenidas a diferentes escalas.

Al variar el parámetro de resolución uno explora toda la jerarquía de las cubiertas del grafo, desde toda la red hasta los nodos individuales, lo que lleva a la información más completa sobre la estructura de la comunidad de la red. Sin embargo, el método también proporciona una forma natural de clasificar las coberturas según su relevancia. Es razonable pensar que una buena cobertura de la red es estable, es decir, que solo se puede destruir cambiando sensiblemente el valor de α para el que se recuperó. Cada portada se entrega para α que se encuentra dentro de cierto rango. Una cobertura estable estaría indicada por un amplio rango de α. Lo que necesitamos es un índice cuantitativo para etiquetar una cobertura . Adoptaremos el valor promedio  de la aptitud de sus comunidades, es decir

Equation (3)

donde nc es el número de módulos. La aptitud debe calcularse para un valor fijo de α (elegimos α = 1 por simplicidad), de modo que se puedan reconocer cubiertas idénticas (diferentes) por valores iguales (diferentes). Obtendremos el histograma de los valores  de las cubiertas obtenidas para diferentes valores α: las cubiertas estables se revelan mediante picos pronunciados en el histograma de aptitud física resultante. Cuanto más alto es el pico, más estable es la cobertura. De esta manera, las cubiertas se pueden clasificar según su frecuencia. Un concepto similar de estabilidad ha sido adoptado en un estudio reciente, donde se introdujo un parámetro de resolución en la modularidad de Newman-Girvan [35].

Una pregunta natural es cómo combinar comunidades jerárquicas con comunidades superpuestas, ya que el significado habitual de la jerarquía parece incompatible con la existencia de nodos compartidos entre las comunidades. Sin embargo, esto es solo aparente y la misma definición de particiones jerárquicas puede extenderse al caso de comunidades superpuestas. Decimos que hay dos coberturas  y  están ordenados jerárquicamente, con un número  superior a , si todos los nodos de cada comunidad de  participan (total o parcialmente) en una sola comunidad de cobertura .

Es difícil estimar la complejidad computacional del algoritmo, ya que depende del tamaño de las comunidades y del alcance de sus superposiciones, que a su vez depende en gran medida de la red específica que se estudia junto con el valor del parámetro α. El tiempo para construir una comunidad con nodos s se escala aproximadamente como O(s2), debido a los pasos de retroceso. Por lo tanto, una estimación aproximada de la complejidad para un valor α fijo es O(nclangs2rang), donde nc es el número de módulos de la cubierta entregada y langs2rang el segundo momento del tamaño de la comunidad. El cuadrado proviene del ciclo de todos los nodos de una comunidad para verificar su estado físico después de cada movimiento. La complejidad del caso más desfavorable es O(n2), donde n es la cantidad de nodos de la red cuando las comunidades son de un tamaño comparable con n. En general, este no es el caso, por lo que en la mayoría de las aplicaciones el algoritmo se ejecuta mucho más rápido y casi linealmente cuando las comunidades son pequeñas. La situación se muestra en la figura 3, donde trazamos el tiempo para ejecutar el algoritmo hasta su finalización para dos valores α diferentes como una función del número de nodos para los grafos Erdös-Rényi con un grado promedio de 10: la complejidad va desde la cuadrática a lineal. La complejidad total del algoritmo para realizar el análisis completo de una red también depende del número de valores α necesarios para resolver su estructura jerárquica. Cuanto mejor se muestre la jerarquía de cubiertas, mayor será el número de valores α utilizados para ejecutar el algoritmo. Si la red tiene una estructura jerárquica, como sucede a menudo en sistemas reales, el número de cubiertas crece como log n. En este caso, el número de diferentes valores α necesarios para resolver la jerarquía también es del orden de log n y el análisis completo puede llevarse a cabo muy rápidamente. Notamos que cada iteración del algoritmo para un α dado es independiente de los otros. Entonces, el cálculo se puede paralelizar trivialmente ejecutando diferentes valores α en cada computadora. Si no se dispone de grandes recursos informáticos, una manera económica de proceder podría ser comenzar desde un gran valor α, para el cual el algoritmo se ejecuta hasta su finalización en un tiempo muy corto, y usar la cubierta final como configuración inicial para una ejecución en un valor α ligeramente menor. Dado que la cubierta correspondiente es similar a la inicial, la segunda carrera también se completará en un tiempo corto y uno puede repetir el procedimiento hasta la izquierda del rango de α.


Figura 3. Complejidad computacional del algoritmo. Las dos curvas muestran cómo el tiempo para ejecutar el algoritmo se escala con el tamaño del grafo para redes Erdös-Rényi con un grado promedio de 10 para α = 0.9 y 1.6, respectivamente. La complejidad varía desde cuadrático para α = 0.9, para el cual las comunidades son considerables, hasta lineal para α = 1.6, para el cual las comunidades son pequeñas.

Concluimos que para las redes jerárquicas nuestro procedimiento tiene una complejidad computacional del peor caso de O(n2log n). Observamos que, si bien es cierto que actualmente varios algoritmos tienen una complejidad menor, ninguno de ellos es capaz de llevar a cabo un análisis completo de la estructura jerárquica de la comunidad, ya que generalmente ofrecen una única partición. Por lo tanto, una comparación justa no es posible. Además, otras recetas para la optimización local de nuestra u otras funciones de acondicionamiento físico pueden reducir considerablemente la complejidad computacional del algoritmo, lo que parece una prometedora dirección de investigación para el futuro.

3. Resultados

Probamos ampliamente nuestro método en redes artificiales con una estructura de comunidad jerárquica incorporada. Adoptamos una referencia similar a la propuesta recientemente por Arenas et al [36, 37], que es una simple extensión de la referencia clásica propuesta por Girvan y Newman [6]. Hay 512 nodos, organizados en 16 grupos de 32 nodos cada uno. Los 16 grupos están ordenados en cuatro supergrupos. Cada nodo tiene un promedio de enlaces k1 con los 31 socios de su grupo y enlaces k2 con los 96 nodos de otros tres grupos dentro del mismo supergrupo. Además, cada nodo tiene un número k3 de enlaces con el resto de la red. De esta forma, surgen dos niveles jerárquicos: uno que consta de los 16 grupos pequeños y uno de los supergrupos con 128 nodos cada uno (la figura 1 (arriba) es un ejemplo). El grado de mezcla de los cuatro supergrupos se expresa mediante el parámetro k3 que sintonizamos libremente. En principio, también podríamos sintonizar la mezcla de las pequeñas comunidades, variando la relación k1 / k2, pero preferimos establecer k1 = k2 = 16, de modo que las microcomunidades sean "borrosas", es decir, bien mezcladas entre sí. , y plantear una dura prueba para nuestro método.

Tenemos que verificar si la jerarquía incorporada se recupera a través del algoritmo. Esto, en general, depende del parámetro k3. Por lo tanto, consideramos diferentes valores de k3: para cada valor, construimos 100 realizaciones de la red. Para comparar la estructura modular incorporada con la proporcionada por el algoritmo, adoptamos la información mutua normalizada, una medida de similitud tomada de la teoría de la información, que ha demostrado ser confiable [38]. La extensión de la medida a la superposición de comunidades no es trivial y existen varias alternativas. Nuestra extensión se analiza en el apéndice B. En la figura 4, trazamos el valor promedio de la información mutua normalizada como una función de k3 para los dos niveles jerárquicos. Vemos que en ambos casos los resultados son muy buenos. La cobertura en los cuatro supergrupos o macrocomunidades está identificada correctamente para k3 <24, con muy pocas excepciones, y el algoritmo comienza a fallar solo cuando k3 ~ 32, es decir, cuando cada nodo tiene 32 enlaces dentro y 32 fuera de su macro- comunidad, que luego se mezcla bien con los demás. El rendimiento también es muy bueno para el nivel jerárquico inferior: los módulos siempre están bien mezclados entre sí, ya que k1 = k2 = 16 para cualquier valor de k3, por lo que es notable que la estructura modular resultante encontrada por el algoritmo esté todavía tan cerca de la estructura modular incorporada, hasta k3 ~ 32. El principal problema con este tipo de pruebas es que no se cuenta con información independiente sobre las cubiertas, por lo tanto, solo se puede juzgar si son razonables o no. Afortunadamente, para algunas redes, las cubiertas se identificaron con información especial sobre el sistema y / o su historial. En la figura 5, mostramos los histogramas de fitness correspondientes a algunas de estas redes, a menudo utilizados para probar algoritmos: el club de karate Zachary [39] (panel superior izquierdo), la red de delfines de Lusseau [40] (panel superior derecho) y el red de equipos de fútbol americano universitario [6] (panel inferior izquierdo). La red social de miembros del club de karate estudiada por el sociólogo Wayne Zachary se ha convertido en un punto de referencia para todos los métodos de detección comunitaria. La red consta de 34 nodos, que se separaron en dos grupos distintos debido a un contraste entre uno de los instructores y el administrador del club. La pregunta es si uno es capaz de detectar la fisión social de la red. La segunda red representa las interacciones sociales de los delfines mulares que viven en Doubtful Sound, Nueva Zelanda. La red fue estudiada por el biólogo David Lusseau, quien dividió los delfines en dos grupos según su edad. El tercer ejemplo es la red de equipos de fútbol americano universitario. Aquí, hay 115 nodos, que representan a los equipos, y dos nodos están conectados si sus equipos juegan uno contra el otro. Los equipos están divididos en 12 conferencias. Los juegos entre equipos en la misma conferencia son más frecuentes que los juegos entre equipos de diferentes conferencias, por lo que uno tiene una cobertura natural donde las comunidades corresponden a las conferencias.


Figura 4. Prueba de la precisión de nuestro método en un punto de referencia jerárquico. La información mutua normalizada se usa para comparar la cobertura encontrada por el algoritmo con la cobertura natural de la red en cada nivel. En el nivel superior (círculos), las comunidades son cuatro clusters, cada uno de los cuales incluye 32 nodos, para un total de 128 nodos por clúster. Nuestro método encuentra los grupos correctos siempre que no estén bien mezclados entre sí. En el nivel inferior (cuadrados), las comunidades son 16 grupos de 32 nodos cada uno. El método funciona muy bien, teniendo en cuenta que cada nodo tiene tantos enlaces dentro como fuera de cada microcomunidad, para cualquier valor de k3. La línea vertical punteada marca las configuraciones de grafo para las cuales el número de enlaces de cada nodo dentro de su macrocomunidad es igual a la cantidad de enlaces que conectan el nodo con las otras tres macrocomunidades.


Figura 5. Análisis de redes reales. Los histogramas de aptitud corresponden al club de karate de Zachary (panel superior izquierdo), la red de delfines de Lusseau (panel superior derecho) y la red de equipos de fútbol americano universitario (panel inferior izquierdo). Los picos más altos indican las mejores coberturas, que coinciden con las coberturas naturales de los grafos, a excepción del club de karate de Zachary, donde corresponde a la misma división en cuatro clústers encontrados a través de la optimización de la modularidad. Sin embargo, la cobertura social en dos de las redes es la tercera tapa más relevante. En el panel inferior derecho, mostramos el histograma de fitness para un grafo aleatorio Erdös-Rényi con 100 nodos y el mismo grado promedio que la red de equipos de fútbol americano universitario: no hay una estructura visible, como se esperaba.

Los picos pronunciados en los histogramas de la figura 5 muestran que estas redes sí tienen estructura de comunidad. Para la red de Zachary, encontramos que la cubierta más estable consiste en cuatro clusters. Incluso si esto no es lo que a uno le gustaría recuperar, hacemos hincapié en que esta cobertura a menudo se encuentra por otros métodos, como la optimización de la modularidad, que indica que es topológicamente significativo. Pero nuestro método puede funcionar mejor: la división social en dos grupos (figura 6 (a)) resulta ser un nivel jerárquico más alto, dado por una fusión por pares de las cuatro comunidades de la cobertura principal. Curiosamente, encontramos que los dos grupos se superponen y comparten algunos nodos. Para la red de delfines, el pico más alto corresponde a la subdivisión de Lusseau de la población de animales en dos comunidades, con cierta superposición entre los dos grupos (figura 6 (b)). De manera similar, el pico más alto en la figura 5 (panel inferior izquierdo) corresponde a la partición natural de los equipos en conferencias.


Figura 6. (a) club de karate de Zachary. Mostramos los niveles jerárquicos correspondientes a la cobertura en dos grupos (0,76 <α <0,84). Los nodos 3, 9, 10, 14 y 31 se comparten entre los dos grupos: dichos nodos a menudo se clasifican erróneamente mediante algoritmos tradicionales. Los nodos superpuestos reflejan la fisión social observada por Zachary, ilustrada por los cuadrados y los círculos en la figura. (b) La red de delfines mulares de Lusseau. La mejor cobertura en dos conglomerados que encontramos (0,77 <α <0,82) concuerda con la separación observada por Lusseau (cuadrados y círculos en la figura). Los nodos 8, 20, 29, 31 y 40 se comparten entre los dos grupos.

Para verificar qué tan bueno es nuestro algoritmo en comparación con otros métodos, hemos analizado el karate, los delfines y las redes de fútbol americano universitario con el método de filtración de camarilla (CPM) de Palla et al [17]. Los valores de la información mutua normalizada de las coberturas encontradas por el algoritmo con respecto a las coberturas reales son 0.690 (nuestro método) y 0.170 (CPM) para el club de karate, 0.781 (nuestro método) y 0.254 (CPM) para los delfines. red, y 0.754 (nuestro método) y 0.697 (CPM) para la red de fútbol americano universitario. Por lo tanto, nuestro método es superior al CPM en estos casos. Por otro lado, el CPM funciona mejor para redes con muchas camarillas. Un ejemplo está representado por la palabra asociación de red construida en la Asociación de Normas Libres de la Universidad del Sur de la Florida [41], analizada en [17]. El CPM encuentra grupos de palabras que corresponden a categorías bien definidas, mientras que con nuestro método las categorías son más mixtas. Una razón importante de esta discrepancia es que nuestro método recupera nodos superpuestos que generalmente se encuentran en el límite entre comunidades, mientras que en la red de asociación de palabras a menudo son nodos centrales de una comunidad. Por ejemplo, la palabra "color" es el eje central de la comunidad de colores, pero también pertenece a otras categorías como "astronomía" y "luz".

Realizamos pruebas en muchos otros sistemas reales, incluidas redes de interacción de proteínas, redes de colaboración científica y otras redes sociales. En todos los casos, encontramos portadas razonables. Por otro lado, encontramos que los grafos aleatorios no tienen una estructura de comunidad natural, ya que las cubiertas son inestables (figura 5 (panel inferior derecho)). Esto es notable, ya que se sabe que otros enfoques también pueden encontrar cubiertas en grafos aleatorios [42], un problema que desencadenó un debate en curso sobre cuándo una portada es de hecho relevante [43].

En la figura 7, mostramos cómo el grado de superposición entre las comunidades depende del parámetro de resolución α, para tres redes reales. A partir de la figura, no es posible inferir ninguna dependencia sistemática de la superposición en α, el patrón depende en gran medida de la topología de grafo específica.


Figura 7. Fracción de nodos superpuestos como una función de α para las tres redes reales discutidas en la figura 5: el club de karate de Zachary y las redes de delfines y equipos de fútbol americano. No existe un patrón único, la extensión de la superposición no muestra una variación sistemática con α.

Concluimos la sección con un análisis de las propiedades estadísticas de la estructura de la comunidad en grafos. La Figura 8 muestra la distribución de tamaños de comunidad para una muestra del grafo de enlace WWW, correspondiente al subconjunto de páginas web dentro del dominio .gov. Analizamos el componente conectado más grande del grafo, que consta de 774 908 nodos y 4 711 340 enlaces. La figura hace referencia a la cubierta encontrada para α = 1, que se identificó en menos de 40 h de tiempo de CPU en una PC pequeña. La distribución del tamaño de la comunidad está sesgada, con una cola que sigue una ley de poder con el exponente 2.2 (1). El resultado es consistente con los análisis previos de distribuciones de tamaño de la comunidad en grafos grandes [8, 17, 44, 45], aunque este es el primer resultado relacionado con la WWW. Hacemos hincapié en que no hemos realizado un análisis completo de esta red, ya que requeriría una gran cantidad de procesadores para llevar a cabo el alto número de ejecuciones en diferentes valores α que son necesarios para un análisis confiable. Por lo tanto, la distribución en la figura 8 no corresponde necesariamente a la cobertura más significativa. Sin embargo, los valores α de las cubiertas más representativas de todas las redes que hemos considerado resultaron cercanas a 1, por lo que es probable que la gráfica de la figura 8 sea una aproximación aproximada de la distribución real.


Figura 8. Distribución de tamaños de comunidad para el grafo de enlace correspondiente al dominio .gov de la WWW. El parámetro de resolución α = 1. La distribución es claramente sesgada, de acuerdo con hallazgos previos en grafos grandes. La cola puede ajustarse bien mediante una ley de potencia con el exponente 2.2 (1) (línea discontinua en la figura).

4. Conclusiones

En este documento, presentamos el primer método que descubre simultáneamente tanto la estructura jerárquica como la estructura de comunidad superpuesta de redes complejas. El método consiste en encontrar los máximos locales de una función de aptitud mediante búsqueda iterativa local. El procedimiento permite que cada nodo se incluya en más de un módulo, lo que lleva a una descripción natural de comunidades superpuestas. Finalmente, ajustando el parámetro de resolución α se puede sondear la red a diferentes escalas, explorando la posible jerarquía de la estructura de la comunidad. La aplicación de nuestro método a varias redes construidas y empíricas ha dado excelentes resultados.

Nos gustaría hacer hincapié en que nuestro método proporciona un marco general que produce una gran clase de algoritmos. Por ejemplo, uno podría elegir una expresión diferente para la función de aptitud, otro criterio para definir la cubierta más significativa, o un procedimiento de optimización diferente de la aptitud para un solo grupo. La configuración que hemos probado demuestra ser muy confiable, pero no podemos excluir que las diferentes opciones rindan incluso mejores resultados. De hecho, el marco es tan flexible que se puede adaptar fácilmente al problema en cuestión: si uno tiene pistas sobre la topología de las comunidades que se encuentran para un sistema específico, esta información puede usarse para diseñar una función de acondicionamiento físico particular, teniendo en cuenta las características requeridas de los módulos.

Dado que el análisis completo de la estructura de la comunidad de una red se puede llevar a cabo simultáneamente en muchas computadoras, el límite de tamaño superior de los grafos tratables puede aumentar considerablemente. Nuestro método brinda la oportunidad de estudiar sistemáticamente la distribución de tamaños de comunidades de redes grandes hasta millones de nodos, un aspecto crucial de la organización interna de un grafo, que los estudiosos recién han empezado a examinar. Un subproducto interesante de nuestra técnica es la posibilidad de cuantificar la participación de nodos superpuestos en sus comunidades por los valores de su aptitud (nodo) con respecto a cada grupo al que pertenecen.

Finalmente, nos gustaría mencionar que el método puede extenderse naturalmente a redes ponderadas, es decir, redes donde los enlaces tienen un peso. No es necesario utilizar ningún tipo de umbralización [46], ya que la generalización de la fórmula de aptitud es sencilla: en la ecuación (1), tenemos que reemplazar el grado k con la fuerza correspondiente s (expresando la suma sobre los enlaces ' pesos). Las aplicaciones a las redes dirigidas también se pueden diseñar fácilmente con opciones adecuadas de la función de aptitud. Nuestra propia función (1) podría extenderse al caso dirigido, ya que considera el grado de los nodos de un subgrafo: es plausible suponer que el grado total de los nodos del subgrafo debido a enlaces internos al subgrafo excede el grado total de grado entrante producido por enlaces provenientes de nodos externos, si el subgrafo es una comunidad.

jueves, 24 de mayo de 2018

Protocolos de difusión afectan las cascadas de Facebook

¿Los protocolos de difusión gobiernan el crecimiento en cascada en Facebook?

Justin Cheng, Jon Kleinberg, Jure Leskovec, David Liben-Nowell, Bogdan State, Karthik Subbian, Lada Adamic

Figura 1: El árbol de difusión de una cascada con un protocolo de difusión voluntaria, donde los individuos publicaron música de un artista cuyo nombre coincidía con la letra que les asignó un amigo. Los enlaces se colorean de rojo (temprano) a azul (tarde).

Las grandes cascadas pueden desarrollarse en las redes sociales en línea a medida que las personas comparten información entre sí. Aunque las cascadas de compartición simples se han estudiado ampliamente, el alcance completo de comportamientos en cascada en las redes sociales es mucho más diverso. Aquí estudiamos cómo los protocolos de difusión, o los intercambios sociales que permiten la transmisión de información, afectan el crecimiento en cascada, de forma análoga a la forma en que los protocolos de comunicación definen cómo se transmite la información de un punto a otro. Estudiando 98 de las cascadas de información más grandes en Facebook, encontramos una amplia gama de protocolos de difusión, desde la distribución en cascada de imágenes, que usan un protocolo simple de tocar un solo botón para la propagación, hasta ALS Ice Bucket Challenge, cuyo protocolo de difusión involucraba individuos crear y publicar un video, y luego nominar a otros para que hagan lo mismo. Encontramos clases recurrentes de protocolos de difusión e identificamos dos factores clave de contrapeso en la construcción de estos protocolos, con implicaciones para el crecimiento de una cascada: el esfuerzo requerido para participar en la cascada y el costo social de permanecer al margen. Los protocolos que requieren un mayor esfuerzo individual ralentizan la propagación de una cascada, mientras que los que imponen un mayor costo social de no participar aumentan la probabilidad de adopción de la cascada. La previsibilidad de la transmisión también varía con el protocolo. Pero independientemente del mecanismo, todas las cascadas de nuestro análisis tienen un número de reproducción similar (≈ 1,8), lo que significa que las menores tasas de exposición se pueden compensar con mayores tasas de adopción por exposición. Por último, mostramos cómo la estructura de una cascada no solo puede diferenciar estos protocolos, sino también modelarse a través de procesos de ramificación. Juntos, estos hallazgos proporcionan un marco para comprender cómo una amplia variedad de cascadas de información puede lograr una adopción sustancial a través de una red.






ARXiv

martes, 22 de mayo de 2018

Introducción: Visualización en Gephi


Usando Gephi para visualización de datos


Autor: Maristella Feustle | Digital Humanities


Muchos de nosotros hemos estado haciendo visualizaciones básicas de datos cuantitativos desde la escuela primaria, convirtiendo la información numérica en cuadros y gráficos. En algún lugar a lo largo de la línea, la mayoría de nosotros también hemos encontrado diagramas de Venn para visualizar relaciones conceptuales y atributos que se tienen en común entre las entidades. Pero cuando pensamos en la visualización, las visualizaciones cuantitativas como las producidas por Excel son más accesibles.

Por supuesto, no todos los datos son cuantitativos. No todos los puntos de datos son números, y no todas las relaciones entre ellos son numéricas, y sin embargo, intuimos que el contexto puede ser tan complejo como importante. Ahí es donde entra Gephi. Si puedes articular una relación, puedes mapearla.

Gephi depende de la relación "triple" que también subyace a RDF, el modelo de metadatos del Marco de Descripción de Recursos, de claro interés para la biblioteca y la ciencia de la información. En el triple, Algo tiene una conexión con otra cosa. O bien, la Persona 1 está de alguna manera conectada a la Persona 2. El atributo 1 está conectado de alguna manera con el Atributo 2.

Los atributos son nodos, y la conexión, sea lo que sea, es un borde. Dos nodos más un borde son tres cosas, o un triple. Las conexiones pueden ser recíprocas, o solo una dirección.

Los ejemplos potenciales son virtualmente ilimitados: digamos, por ejemplo, que Jeremiah era una rana toro. Es decir, Jeremiah tiene el atributo de ser una rana toro. Jeremías y la rana toro (para acuñar un término) son nodos. Tener el atributo es una ventaja. Jeremiah también fue un buen amigo mío. Es decir, Jeremiah era miembro del grupo de buenos amigos míos.

Esas son solo algunas conexiones. ¿Qué pasa cuando tus conexiones tienen conexiones? Necesitamos una forma más sofisticada de hacer un seguimiento de ellos.

Esta demostración utiliza datos de listas de óperas y artistas intérpretes o ejecutantes en el apéndice de La Scala West de Ronald Davis: La Scala West: The Dallas Opera under Kelly and Rescigno, siguiendo aproximadamente los primeros diez años de producciones de la Ópera de Dallas.

Utilizando un valor separado por coma (archivo CSV), hemos articulado las personas y los roles que desempeñaron respectivamente como las dos columnas requeridas para que Gephi importe como una tabla de borde: Origen y Destino.

Aquí, vale la pena señalar que Gephi puede ser muy exigente con la forma en que se forman sus datos. Para evitar la creación de conexiones y nodos espurios, es importante asegurarse de que sus datos estén libres de espacios y caracteres adicionales que podrían, por ejemplo, hacer que Gephi decida que María [espacio] Callas y María [espacio espacial] Callas son dos personas diferentes Cuando tienes cientos o miles de nodos y conexiones, las distinciones innecesarias como esas realmente pueden arrojar tu visualización. Para la preparación de datos, OpenRefine es un compañero muy útil para Gephi.

Incluso con un conjunto de datos bien construido, la salida de visualización inicial de Gephi parece lanzar espaguetis y albóndigas en la pared, solo que más angulares:



La diferencia importante que debemos mencionar aquí es que Gephi hace los cálculos por usted, pero no toma decisiones por usted. Por lo tanto, depende de usted la elección de cómo aplicar los colores para diferenciar los tipos de nodos y aristas, o los grados de conectividad, y qué algoritmos representan mejor el significado que desea que su visualización muestre, qué etiquetar, etc. Estas características están fuertemente empaquetadas en la interfaz de usuario de Gephi, y experimentar con ellas es parte de la diversión del programa. Otras opciones residen en los complementos que vienen incluidos con el programa.

En este caso, el resultado final nos permitió mostrar en una sola imagen las complejidades de las conexiones entre los artistas intérpretes o ejecutantes en la Ópera de Dallas, así como los artistas principales, artistas frecuentes y producciones frecuentes en los primeros años de la Ópera de Dallas - en en resumen, un mapa de las relaciones entre los artistas intérpretes o ejecutantes, las obras y entre sí.




Para comenzar con Gephi, visite los enlaces a continuación:

https://gephi.org/tutorials/gephi-tutorial-quick_start.pdf (Refiere a una vieja versión, pero todavía útil)
http://www.martingrandjean.ch/gephi-introduction/
https://seinecle.github.io/gephi-tutorials/

sábado, 19 de mayo de 2018

Software: SocNetV trabaja muy bien

Revisión del software para ARS

Social Network Visualizer SocNetV-2.3



Fuente



Lo primero que uno encuentra en el SocNetV es sencillez. Pero no se engañen, es muy poderoso y versátil también. Se instala rápidamente y, para un usuario extendido de diversos paquetes de software, uno posa la mirada rápidamente en una opción de "Web Crawler" que intriga porque uno supone que promete extraer redes de sitios webs y sus hiperenlaces. Uno sospecha bien pero no todo es color de rosa. Volveremos a esto después.






Instalación

La última versión de SocNetV se puede descargar desde la página de descargas del proyecto.

Se distribuye tanto en código fuente como en paquetes binarios para distribuciones de Linux, instalador para Windows e imagen de disco para MacOS.

Instrucciones detalladas a continuación.


Windows

Para instalar y ejecutar SocNetV en Windows, simplemente descargue el último instalador de SocNetV para Windows desde la página de Descargas.

Haga doble clic en el ejecutable SocNetV-2.x-installer.exe. El programa se instalará automáticamente y creará un acceso directo en el menú Inicio.





Introducción a la interfaz de usuario

SocNetV tiene una interfaz gráfica de usuario (GUI) simple compuesta de:

  • El menú
  • La barra de herramientas
  • Los paneles
  • El lienzo
  • La barra de estado con mensajes útiles durante el tiempo de ejecución.

Ejemplo de ventana principal de SocNetV


El menú

En la parte superior de la ventana, está la barra de menú, llena de comandos y opciones, organizada en 6 menús:

  • Network: opciones para cargar y guardar una red, exportarla, crear redes aleatorias, etc
  • Edit: opciones para agregar / eliminar nodos y bordes, cambiar colores, filtrar bordes / aislar nodos, etc.
  • Analysis: le da herramientas para analizar la red activa (densidad, diámetro, centralidades, matriz de distancia, etc.).
  • Layout: opciones para aplicar métodos de diseño, es decir, reubicar todos los nodos según su centralidad.
  • Options: le permite mostrar / ocultar bordes, flechas de borde, activar / desactivar el antialiasing, etc.
  • Help


La barra de herramientas

Debajo del menú, la barra de herramientas te permite llevar a cabo una serie de acciones con un solo clic. Puede crear una red nueva, cargar un archivo de red, guardar la red actual e imprimir. También puede cambiar entre relaciones, agregar nuevas relaciones y mostrar mensajes de ayuda para las opciones del menú. En la barra de herramientas, hay botones para editar los nodos (agregar / eliminar / buscar / propiedades), los enlaces (agregar / eliminar / filtrar) y abrir la Configuración de la aplicación.

La parte principal de la ventana de la aplicación está ocupada por los paneles de la barra lateral (izquierda-derecha) y un "lienzo" virtual (lado derecho) donde aparecen los nodos y bordes de la red.

Los paneles

El panel a la izquierda de la ventana es el Panel de control. El panel de la derecha es el Panel de estadísticas.


Panel de control

El Panel de control se compone de 3 grupos de opciones:

  • Edit
  • Analyze
  • Visualize

En el grupo Edit, puede crear subgrafos a partir de nodos seleccionados, cambiar el modo Edge y simétrizar la red.

En el grupo Analyze, las opciones se clasifican en cinco submenús:

  • Matrix: visualización o diagrama de adyacencia, cálculo Laplaciano, Grado o Matriz de Cocitación.
  • Cohesion: distancias, geodésica, excentricidad, diámetro, así como conectividad, coeficiente de agrupamiento, caminatas y matriz de alcance.
  • Prominence: los índices de Centrality y Prestige que SocNetV admite.
  • Communities: camarillas de cómputo, censo de tríada, etc.
  • Equivalence: los métodos de equivalencia estructural compatibles con SocNetV, como el Análisis jerárquico de conglomerados, las diferencias de perfil del vínculo, etc.

Cuando selecciona una opción, SocNetV calcula lo que pidió y muestra el informe (en formato HTML) en una nueva ventana del navegador.


Ejemplo de informe SocNetV (en HTML): coeficientes de Pearson

En el grupo Visualize, hay menús y casillas de verificación para incrustar diseños de visualización en la red actual.

Con un solo clic, SocNetV puede visualizar la red de formas intuitivas. Hay dos categorías de diseño:

  • Por índices de prominencia. Aquí puede seleccionar una métrica de prominencia (es decir, entrelazamiento) y un tipo de disposición (es decir, circular). Presiona "Aplicar" y ¡voila!
  • Por modelos dinámicos (es decir, dirigido a la fuerza), como el modelo Eades.



Ventana principal anotada

El lienzo

El lienzo es el área principal de interacción. Usted puede:

  • señalar y hacer clic en un nodo / enlace para seleccionarlo, haga clic con el botón izquierdo para abrir el menú contextual
  • haga doble clic en el espacio vacío para agregar un nodo,

Haga clic con el botón central en un nodo para agregarle un borde dirigido.
El color de fondo inicial se establece en "blanco", pero puede cambiarlo desde Editar -> menú Colores.

A continuación, describimos cómo trabajar con SocNetV.