Estructura e inferencia en redes anotadas
M. E. J. Newman y Aaron Clauset
Nature Communications 7, Número del artículo: 11863 (2016)
Doi: 10.1038 / ncomms11863
Resumen
Para muchas redes de interés científico conocemos tanto las conexiones de la red como la información sobre los nodos de la red, como la edad o el género de los individuos en una red social. Aquí se demuestra cómo estos "metadatos" se puede utilizar para mejorar nuestra comprensión de la estructura de la red. Nos centramos en particular en el problema de la detección de comunidades en redes y desarrollamos un enfoque matemático basado en principios que combina una red y sus metadatos para detectar comunidades con mayor precisión de lo que se puede hacer con solo. Crucialmente, el método no asume que los metadatos están correlacionados con las comunidades que estamos tratando de encontrar. En su lugar, el método aprende si existe una correlación y utiliza o ignora correctamente los metadatos dependiendo de si contienen información útil. Demostramos nuestro método en redes sintéticas de estructura conocida y en redes del mundo real, grandes y pequeñas, provenientes de dominios sociales, biológicos y tecnológicos.
Introducción
Las redes surgen en muchos campos y proporcionan una representación potente y compacta de la estructura interna de una amplia gama de sistemas complejos1. Los ejemplos incluyen redes sociales de interacciones entre personas, redes tecnológicas y de información como Internet o la World Wide Web y redes biológicas de moléculas, células o especies enteras. Las dos últimas décadas han sido testigos de un rápido crecimiento tanto en la disponibilidad de datos de la red como en el número y la sofisticación de las técnicas de análisis de redes. Tomando ideas de la teoría de grafos, la física estadística, la informática, las estadísticas y otras áreas, el análisis de redes tiende a caracterizar las características estructurales de una red de una manera que arroja luz sobre el comportamiento del sistema descrito por la red. Estudios de redes sociales, por ejemplo, podrían identificar a los individuos más influyentes o centrales en una población. Los estudios de las redes de carreteras pueden arrojar luz sobre los flujos de tráfico o cuellos de botella dentro de una ciudad o país. Los estudios de vías en redes metabólicas pueden conducir a una comprensión más completa de la maquinaria molecular de la célula.
La mayor parte de la investigación en esta área trata a las redes como objetos de topología pura, conjuntos sin adornos de nodos y sus interacciones. Sin embargo, la mayoría de los datos de la red están acompañados por anotaciones o metadatos que describen las propiedades de los nodos como la edad, el género o la etnia de una persona en una red social, el modo de alimentación o la masa corporal de las especies en una red alimenticia, la capacidad de datos o la ubicación de los nodos. El Internet y así sucesivamente. (Puede haber metadatos en los enlaces de una red, así como en los nodos2, pero nuestro enfoque aquí es en el caso del nodo.) En este artículo, consideramos cómo ampliar el análisis de las redes para incorporar directamente estos metadatos. Nuestro enfoque se basa en métodos de inferencia estadística y en principio se puede aplicar a una serie de diferentes tareas de análisis de red. Aquí nos centramos específicamente en una de las tareas más estudiadas, el problema de detección de la comunidad. La detección de la comunidad, también llamada agrupación de nodos o clasificación, busca una buena división de los nodos de una red en grupos o clases3. Normalmente, se busca una estructura asociativa, agrupaciones de nodos tales que las conexiones son más densas dentro de los grupos que entre ellas. Esta estructura es común en las redes sociales, por ejemplo, donde los grupos pueden corresponder a conjuntos de amigos o compañeros de trabajo, pero también ocurre en otros casos, incluyendo las redes biológicas y ecológicas, la Web, las redes de transporte y distribución y otras. Menos común, pero no menos importante, es la estructura desastrosa, en la que las conexiones de red son más escasas dentro de los grupos que entre ellas, y también pueden ocurrir mezclas de estructura asociativa y desastrosa, donde diferentes grupos pueden tener propensiones variables para conexiones dentro o entre grupos .
En algunos casos, los grupos identificados por la detección de la comunidad se correlacionan significativamente con otras propiedades o funciones de la red, como las lealtades o los intereses personales en las redes sociales3,4 o la función biológica en las redes metabólicas5,6. Sin embargo, algunas investigaciones recientes han sugerido que estos casos pueden ser la excepción más que la regla7,8, un punto importante que abordaremos más adelante en este artículo.
Se ha propuesto un gran número de métodos para detectar comunidades en redes no anotadas3. Entre ellos, algunos de los más poderosos, tanto en términos de rendimiento rigurosamente demostrable y de velocidad cruda, son los basados en la inferencia estadística. Aquí construimos sobre estos métodos para incorporar los metadatos del nodo, ya sean categóricos o de valor real, en el problema de detección de la comunidad de una manera flexible y flexible. (Para los metadatos de valor real, nos limitamos al caso escalar o unidimensional, pero los metadatos multidimensionales, como las ubicaciones en el espacio físico o latente9,10,11, serían un enfoque natural para futuras extensiones de nuestro enfoque). Los métodos resultantes tienen varias características atractivas. En primer lugar, pueden hacer uso de metadatos en formato arbitrario para mejorar la precisión de la detección de la comunidad. En segundo lugar, y fundamentalmente para nuestros objetivos, no asumen a priori que los metadatos se correlacionan con las comunidades que buscamos encontrar. En cambio, detectan y cuantifican la relación entre los metadatos y la comunidad, si existe, explotan esa relación para mejorar los resultados. Incluso si la correlación es imperfecta o ruidosa, el método todavía puede usar qué información está presente para obtener resultados mejorados. A la inversa, si no existe correlación, el método ignorará automáticamente los metadatos, devolviendo resultados basados únicamente en la estructura de la red.
Tercero, nuestros métodos nos permiten seleccionar entre divisiones competidoras de una red. Muchas redes tienen una serie de diferentes divisiones posibles12. Por ejemplo, una red social de conocidos puede tener divisiones significativas a lo largo de las líneas de edad, género, raza, religión, idioma, política o muchas otras variables. Mediante la incorporación de metadatos que se correlacionan con una división de intereses en particular, podemos favorecer esa división sobre otros, dirigiendo el análisis en una dirección deseada. Por ejemplo, si nos interesa, por ejemplo, en una división de una red social a lo largo de las líneas de edad, y tenemos datos de edad para Alguna fracción de los nodos, podemos usar esos datos para dirigir el algoritmo hacia divisiones correlacionadas con la edad. Incluso si los metadatos son incompletos o ruidosos, el algoritmo todavía puede utilizarlos para guiar su análisis. Sin embargo, si entregamos los metadatos del algoritmo que no se correlacionan con ninguna buena división de la red, el método se negará a seguir ciegamente y nos informará que no existe una buena correlación.
Finalmente, la correlación entre los metadatos y la estructura de la red aprendida por el algoritmo (si existe) es interesante por derecho propio. Una vez encontrado, nos permite cuantificar el acuerdo entre las comunidades de la red y los metadatos, y predecir la pertenencia a la comunidad de nodos para los que carecemos de datos de red y solo tenemos metadatos. Si hemos aprendido, por ejemplo, que la edad es un buen predictor de las agrupaciones sociales, entonces podemos hacer predicciones cuantitativas de la pertenencia a grupos de individuos sobre los que conocemos su edad y nada más.
Varios otros investigadores han investigado formas de incorporar metadatos en los cálculos de detección de la comunidad13,14,15,16,17,18,19, aunque normalmente han hecho suposiciones más fuertes sobre la naturaleza de las comunidades o metadatos, asumiendo, por ejemplo, que Las comunidades son siempre asortativas, o que los metadatos representan ubicaciones en el espacio físico. Tal vez lo más cercano a nuestro enfoque son los métodos de aprendizaje semi-supervisados17,20,21,22, donde se supone que se nos dan las asignaciones exactas de la comunidad de alguna fracción de los nodos y el objetivo es deducir el recordatorio. Una variante de este enfoque es el aprendizaje activo, en el que se da la pertenencia a la comunidad de algunos nodos, pero los nodos conocidos no se especifican a priori, sino que son elegidos por el propio algoritmo a medida que se ejecuta23,24. Otra vena de la investigación, un poco más lejos de nuestro enfoque, considera el caso en el que se nos dice que algunos pares de nodos que están definitivamente en o definitivamente no en la misma comunidad, y luego asigna a las comunidades sujetas a estas restricciones25,26.
Nuestro enfoque, que se describe en detalle en la sección Métodos, toma como entrada una red acompañada de un conjunto de metadatos de nodo, que puede ser, por ejemplo, valores numéricos o etiquetas arbitrarias textuales o alfanuméricas, y produce como salida una división de la Nodos de la red en un número especificado
k de grupos o comunidades. El método no asume, como lo hacen algunos métodos, un patrón particular de conexiones entre comunidades -como conexiones más densas dentro de grupos que entre ellas- y es numéricamente eficiente, haciendo uso de un supuesto esquema de propagación de creencias para realizar una rápida inferencia de Las asignaciones de grupo óptimas que hacen posibles aplicaciones a redes muy grandes. La red más grande que hemos analizado utilizando el método tiene más de 1,4 millones de nodos.
En las secciones siguientes damos resultados que muestran que nuestro método es capaz de recuperar comunidades conocidas en conjuntos de datos de referencia con mayor precisión que los algoritmos basados únicamente en la estructura de la red, que podemos seleccionar entre divisiones comunitarias competidoras en pruebas reales y sintéticas, Es capaz de divinizar las correlaciones entre la estructura de la red y los metadatos, o determinar que no existe tal correlación y que las correlaciones aprendidas entre la estructura y los metadatos pueden usarse para predecir la pertenencia a la comunidad basándose únicamente en los metadatos.
Resultados
Redes sintéticas
Nuestras primeras pruebas están en redes (sintéticas) generadas por computadora que han conocido la estructura de la comunidad incrustada dentro de ellas. Estas redes se crearon utilizando el modelo de bloque estocástico, un modelo estándar de estructura de red en el que n nodos se asignan a grupos, entonces los enlaces se colocan entre ellos de forma independiente con probabilidades que son una función de la pertenencia a un grupo solamente27,28. Después de que se creen las redes, generamos metadatos de nodos de valor discreto que coinciden con las asignaciones de nodos reales de una fracción dada del tiempo y se eligen aleatoriamente de los valores no coincidentes. Esto nos permite controlar la medida en que los metadatos se correlacionan con la estructura de la comunidad y por lo tanto probar la capacidad del algoritmo para hacer uso de metadatos de calidad variable.
La figura 1a muestra los resultados de un conjunto de tales redes que tienen dos comunidades de igual tamaño, con las probabilidades de enlace
pin=cin/n y
pout=cout/n para los enlace dentro del grupo y entre los grupos, respectivamente, donde n es el número de nodos Como antes y
cin y
cout son constantes cuyos valores elegimos. Cuando
cin es mucho mayor que
cout las comunidades son fáciles de detectar de la estructura de la red por sí sola, pero como
cin enfoques de la estructura se vuelve más débil y más difícil de detectar. Cada curva de la figura muestra la fracción de nodos clasificados en sus grupos correctos por nuestro algoritmo, ya que varía la fuerza de la estructura de la comunidad, medida por la diferencia
cin-
cout. Las curvas individuales muestran resultados para diferentes niveles de correlación entre comunidades y metadatos.
Figura 1: Pruebas en redes sintéticas de referencia con n = 10.000 nodos.
(A) Fracción de nodos asignados correctamente para redes con dos comunidades plantadas con grado medio c = 8, en función de la diferencia entre los números de conexiones dentro y entre grupos. Las cinco curvas muestran resultados para las redes con una coincidencia entre los metadatos y las comunidades plantadas en una fracción de 0,5, 0,6, 0,7, 0,8 y 0,9 de los nodos (de abajo hacia arriba). La línea vertical discontinua indica el umbral teórico de detectabilidad, por debajo del cual ningún algoritmo sin metadatos puede detectar las comunidades. (B) Fracción de 100 redes de prueba de cuatro grupos donde el algoritmo selecciona una división bidireccional en particular, entre varias posibilidades de competencia, con y sin la ayuda de metadatos que están débilmente correlacionados con la división deseada. Se considera que una corrida encuentra la división correcta si la fracción de nodos correctamente clasificados supera el 85%. Los parámetros de red son cout = 4 y cin = 20.
Cuando los metadatos y la comunidad coinciden exactamente con la mitad de los nodos (curva inferior) no hay correlación entre los dos, y los metadatos no pueden ayudar en la detección de la comunidad. Por lo tanto, no es de extrañar que esta curva muestra la tasa de éxito más baja. A niveles más altos de correlación, los metadatos contienen información útil y el rendimiento del algoritmo mejora en consecuencia.
Examinando la figura, surge un patrón claro. Para el
cin-
cout grande la red contiene la estructura de comunidad fuerte y el algoritmo clasifica confiablemente esencialmente todos los nodos en los grupos correctos, como nosotros esperaríamos de cualquier algoritmo eficaz. A medida que la estructura se debilita, la fracción de nodos correctos disminuye, pero sigue siendo mayor en todos los casos en los que los metadatos son útiles que en la curva más baja donde no lo son. Además, la tasa de éxito del algoritmo parece mejorar monotónicamente con el nivel de correlación entre los metadatos y las comunidades.
Cuando no hay metadatos, se sabe que el algoritmo de propagación de creencias que usamos proporciona respuestas óptimas al problema de detección de la comunidad en el sentido de que ningún otro algoritmo clasificará una fracción mayor de nodos correctamente en promedio29. El hecho de que nuestro algoritmo hace mejor cuando hay metadatos implica que el algoritmo con metadatos es mejor que cualquier algoritmo posible sin metadatos.
Además, se ha demostrado previamente que por debajo del llamado umbral de detectabilidad, que se produce en
(indicado por la línea vertical discontinua en la figura, y alineado con la transición aguda en la curva de fondo), la estructura de la comunidad se vuelve tan débil como para ser Indetectable por cualquier algoritmo que dependa sólo de la estructura de la red29,30. Muy por debajo de este umbral, sin embargo, nuestro algoritmo aún clasifica correctamente una fracción de los nodos aproximadamente igual a la fracción de metadatos que coinciden con las comunidades, lo que significa que el algoritmo hace mejor con los metadatos que sin que incluso por debajo del umbral. La Figura 1a también muestra que la fracción de nodos clasificados correctamente supera este nivel basal para valores de
cin-
cout algo por debajo del umbral, lo que sugiere que el uso de los metadatos cambia el umbral hacia abajo o tal vez lo elimina por completo.
En resumen, nuestro método combina automáticamente la información disponible de la estructura de la red y los metadatos para realizar un mejor trabajo de detección en la comunidad que cualquier algoritmo basado únicamente en la estructura de la red. Y cuando la red o los metadatos no contienen información sobre la estructura de la comunidad, el algoritmo los ignora correctamente y devuelve una estimación basada únicamente en la otra.
La figura 1b muestra una prueba sintética diferente, de la capacidad del algoritmo para seleccionar entre divisiones competidoras de una red. En esta prueba, las redes se generaron con cuatro comunidades de igual tamaño, pero el algoritmo se encargó de encontrar una división en sólo dos comunidades. Hay ocho maneras de dividir dicha red en dos si queremos mantener indivisibles los cuatro grupos subyacentes. Imaginamos una situación en la que nos interesa encontrar uno de estos ocho. Un algoritmo convencional de detección de la comunidad podría encontrar una división razonable de estas redes, pero no hay garantía de que encontraría la parte "correcta" de una parte del tiempo en que podemos esperar encontrar una de las divisiones competidoras. Pero si a nuestro algoritmo se le da un conjunto de metadatos que se correlacionan con la división de intereses, incluso si la correlación es pobre, entonces esa división será favorecida sobre las otras.
En nuestras pruebas la división deseada era una que coloca dos de los cuatro grupos subyacentes en una comunidad y los dos restantes en la otra. Se generaron metadatos de dos valores que coinciden con esta división el 65% del tiempo, un nivel de correlación relativamente débil, no muy por encima del 50% de los datos completamente no correlacionados. Sin embargo, como se muestra en la Fig. 1b, esto es suficiente para que el algoritmo encuentre de manera fiable la división correcta de la red en casi todos los casos-el 98% del tiempo en nuestras pruebas. Sin los metadatos, por el contrario, tenemos éxito sólo el 6% del tiempo. Algunas aplicaciones prácticas de esta capacidad para seleccionar entre divisiones competidoras se dan en la siguiente sección.
Redes del mundo real
En esta sección describimos aplicaciones de nuestro método a una serie de redes del mundo real, extraídas de los dominios sociales, biológicos y tecnológicos.
Para nuestra primera aplicación analizamos una red de estudiantes escolares, extraída del Estudio Nacional Longitudinal de Salud del Adolescente de los Estados Unidos. La red representa patrones de amistad, establecidos por encuesta, entre los 795 estudiantes de una escuela secundaria estadounidense de tamaño mediano (grados 9°-12°, 14-18 años) y su escuela secundaria de alimentación (grados 7° y 8°, 14 años).
Dado que esta red combina escuelas intermedias y secundarias, no es de extrañar que haya una clara división (previamente documentada) en dos comunidades de la red correspondientes aproximadamente a las dos escuelas. Trabajos anteriores, sin embargo, también han demostrado la presencia de divisiones por origen étnico31. Nuestro método nos permite seleccionar entre divisiones usando metadatos que se correlacionan con el que nos interesa.
La figura 2 muestra los resultados de aplicar nuestro algoritmo a la red tres veces. Cada vez, pedimos al algoritmo dividir la red en dos comunidades. En la Fig. 2a, usamos los seis grados escolares como metadatos y el algoritmo identifica fácilmente una división en los grados 7 y 8 por un lado y los grados 9-12 en el otro, es decir, la división en la escuela media y secundaria. En la Fig. 2b, por el contrario, utilizamos la autoidentificación étnica de los estudiantes como metadatos, que en este conjunto de datos toma uno de los cuatro valores: blanco, negro, hispano u otro (más un pequeño número de nodos con datos faltantes). Ahora el algoritmo encuentra una división completamente diferente en dos grupos, un grupo compuesto principalmente de estudiantes negros y uno de blanco. (El pequeño número de estudiantes restantes se distribuye aproximadamente igual entre los grupos.)
Figura 2: Comunidades encontradas en una red de amistad de la escuela secundaria con varios tipos de metadatos.
Tres divisiones de una red de amistad escolar, utilizando como metadatos (a) grado escolar, (b) origen étnico y (c) género.
Uno podría estar preocupado de que en estos ejemplos el algoritmo está principalmente siguiendo los metadatos para determinar la pertenencia a la comunidad, e ignorando la estructura de la red. Para probar esta posibilidad, se realizó un tercer análisis, utilizando el género como metadatos. Cuando hacemos esto, como se muestra en la Fig. 2c, el algoritmo no encuentra una división en grupos masculinos y femeninos. En cambio, encuentra una nueva división que es un híbrido de las divisiones de grado y etnicidad (estudiantes blancos de secundaria en un grupo y todos los demás en el otro). Es decir, el algoritmo ha ignorado los metadatos de género, porque no había una buena división de red que se correlaciona con ella, y en su lugar encontró una división basada en la estructura de la red solo. El algoritmo hace uso de los metadatos sólo cuando hacerlo mejora la calidad de la división de red (en el sentido del ajuste de máxima verosimilitud descrito en la sección Métodos).
La medida en que las comunidades encontradas por nuestro algoritmo coinciden con los metadatos (o cualquier otra variable de "verdad del suelo") se pueden cuantificar mediante el cálculo de una información mutua normalizada (NMI) 32,33, como se describe en la sección Métodos. NMI varía en el valor de 0 cuando los metadatos no son informativos sobre las comunidades a 1 cuando los metadatos especifican las comunidades por completo. Las divisiones mostradas en la Fig. 2a, b tienen puntuaciones NMI de 0,881 y 0,820, respectivamente, lo que indica que los metadatos son fuertemente pero no perfectamente correlacionada con la pertenencia a la comunidad. Por el contrario, la división en la Fig. 2c, donde el género se utilizó como metadatos, tiene un puntaje de NMI de 0,003, lo que indica que los metadatos contienen esencialmente información cero sobre las comunidades.
Nuestra próxima aplicación es a una red ecológica, una red alimentaria de interacciones predador-presa entre 488 especies marinas que viven en el Mar de Weddell, una gran bahía frente a la costa de la Antártida34,35. Existen diferentes metadatos disponibles para estas especies, incluyendo el modo de alimentación (alimentador de depósitos, alimentador de suspensión, depurador, etc.), zona dentro del océano (bentónica, pelágica, etc.) y otros. En nuestro análisis, sin embargo, nos enfocamos en uno en particular, la masa corporal promedio de un adulto. Las masas corporales de las especies en este ecosistema tienen una amplia gama, de los microorganismos que pesan nanogramos o menos a los centenares de toneladas para las ballenas más grandes. Convencionalmente, en tales casos uno trabaja a menudo con el logaritmo de la masa, que hace la gama más manejable, y lo hacemos aquí. Entonces realizamos descomposiciones de la comunidad k-modos usando esta masa de registro como metadatos, para varios valores de
k.
La figura 3a muestra los resultados para k = 3. Los nodos se colorean de acuerdo con su papel en el ecosistema-carnívoros, herbívoros, productores primarios y así sucesivamente. La división encontrada por el algoritmo parece corresponder a estos papeles muy de cerca, con un grupo compuesto casi enteramente de productores primarios y herbívoros, uno de omnívoros y un tercero que contiene la mayoría de los carnívoros. Los tamaños de nodos en la figura son proporcionales a log-masa, que aumenta a medida que subimos la figura, lo que indica que el algoritmo ha recuperado de la estructura de la red la bien conocida correlación entre la masa corporal y el papel del ecosistema36. Este punto es aún más acentuado por las probabilidades de pertenencia a los tres grupos, que son una incidental, pero a menudo útil, salida adicional del algoritmo que utilizamos (ver Métodos). Estas probabilidades, trazadas como una función de la masa corporal en la Fig. 3b, demuestran que los organismos de baja masa son abrumadoramente propensos a estar en el primer grupo, y los de alta masa en el tercer grupo. Los organismos de masa intermedia tienen una distribución más amplia, pero están particularmente concentrados en el segundo grupo.
Figura 3: Resultados de la aplicación del método de este trabajo a la red alimentaria de especies marinas en el Mar de Weddell.
A) Descomposición tridireccional de la red alimentaria marina descrita en el texto, con el logaritmo de la masa corporal media utilizada como metadatos. Los tamaños de los nodos son proporcionales a la masa de log, y los colores indican el papel de la especie dentro del ecosistema. B) Las probabilidades aprendidas de pertenecer a cada una de las comunidades en función de la masa corporal. Utilizamos masa de registro como la variable de metadatos en nuestros cálculos, pero el eje horizontal aquí se calibra para leer en términos de la masa original en gramos utilizando una escala logarítmica. Las curvas azules, verdes y rojas corresponden, respectivamente, a las comunidades etiquetadas 1, 2 y 3 en a.
Las probabilidades de pertenencia también son de interés por derecho propio. Si, por ejemplo, aprendiéramos de una nueva especie, previamente no representada en nuestro conjunto de datos de la red alimentaria, entonces, incluso sin conocer su modelo de conexiones de red, podemos hacer una declaración acerca de su probabilidad de pertenecer a cada una de las comunidades, Así como su probabilidad de interacción con otras especies, siempre y cuando sepamos su masa corporal. Por ejemplo, una masa corporal baja de 10-12 g pondría una especie con alta probabilidad en el grupo 1 en la Fig. 3, lo que significa que es casi seguramente un productor primario o un herbívoro, con los patrones de interacción que implica.
La detección de la comunidad es ampliamente estudiada precisamente porque se cree que las comunidades de la red están correlacionadas con la función de la red. Más específicamente, se supone comúnmente que las comunidades se correlacionan con alguna variable funcional subyacente, que puede o no ser observada. Sin embargo, esta suposición ha sido cuestionada por trabajos recientes que compararon las comunidades en redes del mundo real con las variables de metadatos de "verdad fundamental" y encontraron poca correlación entre los dos7,8. Este es un descubrimiento sorprendente, pero hay una advertencia. Como hemos visto, a menudo hay múltiples divisiones comunitarias significativas de una red (como en la red de amistad escolar de la Figura 2, por ejemplo), y el hecho de que una división no está correlacionada con una variable de metadatos dada no descarta la posibilidad Que otro podría ser.
Nuestro tercer ejemplo de aplicación del mundo real ilustra estos problemas utilizando una de las mismas redes estudiadas en la referencia. 8, una representación de 46.676 nodos de la estructura peering de Internet a nivel de sistemas autónomos. La variable "verdad del suelo" para esta red es el país en el que se encuentra cada sistema autónomo. El análisis de la ref. 8 encontró poca correlación entre la estructura de la comunidad y los países.
Primero analizamos esta red sin metadatos, realizando una división tradicional 'ciega' de la comunidad, en cinco grupos usando métodos estándar. A continuación, repetimos el análisis utilizando el algoritmo de este documento, con los países como metadatos. Recuerde que, al hacerlo, no forzamos al algoritmo a encontrar una división de comunidad que se alinea con los metadatos si no existe tal división, pero si existe una división, será favorecida sobre las divisiones competidoras que no se alinean con los metadatos. Hay 173 países distintos en el conjunto de datos, un número significativamente mayor de valores de metadatos que para cualquiera de las otras redes que hemos considerado, pero de ninguna manera más allá de las capacidades de nuestro método.
Como antes, evaluamos los resultados usando la información mutua normalizada. Si de hecho hay muchas divisiones competitivas de la red, sólo algunas de las cuales se correlacionan con los metadatos particulares que se nos dan, entonces esperamos que nuestro análisis ciego devuelva una gama de valores de NMI en diferentes ejecuciones, algunas bajas y (quizás) algunas más altas . Esto es realmente lo que vemos, con el NMI en nuestros cálculos que van desde un máximo de 0.626 a un relativamente bajo 0.398, este último está de acuerdo con los resultados citados en ref. 8. A la inversa, cuando el algoritmo de este documento se aplica con países como metadatos, encontramos un puntaje de NMI significativamente mayor que cualquiera de estas cifras, en 0.870, lo que sería interpretado convencionalmente como una indicación de correlación fuerte.
Estos resultados hacen hincapié en que una aparente falta de correlación entre las comunidades de la red y los metadatos podría ser el resultado de la presencia de divisiones de la competencia de la red, que no están correlacionados con los metadatos particulares que tenemos a mano. El algoritmo de este trabajo nos permite seleccionar entre las divisiones y por lo tanto encontrar los que se correlacionan con la variable de interés.
Nuestro cuarto ejemplo se extrae del conjunto de datos FB100 de Traud et al.37, que es un conjunto de redes de amistad entre los estudiantes universitarios de las universidades estadounidenses compiladas a partir de relaciones de amigos en el sitio de redes sociales Facebook. Las redes datan de los primeros días de Facebook cuando sus servicios sólo estaban disponibles para universidades y cada universidad formaba un subgrafo separado e inconexo en la red más grande. Los nodos de estas redes representan a los participantes, que son principalmente aunque no exclusivamente estudiantes, los bordes representan las relaciones de amigos en Facebook, y además de la estructura de la red hay metadatos de varios tipos, incluyendo el género, el año universitario (es decir, el año de Graduación universitaria), mayor (es decir, tema principal del estudio de los estudiantes, si se conoce) y un código numérico que indica en qué residen los estudiantes de dormitorios.
Las divisiones principales en estas redes parecen ser por edad, o más específicamente por año de universidad. Por ejemplo, hemos examinado en detalle la red de la Universidad de Harvard, el lugar de nacimiento de Facebook, que tiene 15.126 nodos. La mayoría de ellos representan a los estudiantes de pregrado, que abarcan los años universitarios 2003-2009, pero también hay un pequeño número de ex alumnos (es decir, antiguos estudiantes), principalmente los recién graduados (años de graduación 2000-2002), así como estudiantes graduados, Estudiantes de verano, y algunos profesores y personal.
La Figura 4a muestra los resultados de una división de cinco vías de la red utilizando nuestro algoritmo con el año como metadatos. Este cálculo proporciona otro ejemplo de la utilidad de las probabilidades aprendidas de pertenencia a grupos para arrojar luz sobre la estructura de la red. La figura muestra una visualización de las probabilidades en función del año, con los colores mostrando la probabilidad relativa de pertenecer a cada una de las comunidades. Cada una de las barras en la parcela tiene la misma altura de 1, ya que las probabilidades se requieren para sumar a 1, mientras que el equilibrio de colores muestra la distribución sobre las comunidades. El examen del panel superior de la figura muestra claramente una división de la red a lo largo de las líneas de edad. Dos grupos, naranja y amarillo, a la derecha de la parcela, corresponden a los dos últimos años de estudiantes en el momento del estudio (años de graduación 2008 y 2009) y el siguiente, en rojo, representan los dos años anteriores (2006 y 2007). La comunidad morada corresponde a los tres años siguientes, 2003-2005, mientras que el sexto grupo, que se muestra en azul, corresponde a los alumnos. Finalmente, los estudiantes para los cuales el año no fue registrado se muestran en la columna marcada 'Ninguno', que es una mezcla de los cinco grupos.
Figura 4: Probada probabilidad previa de pertenecer a la comunidad para dos divisiones de cinco vías de la red de amistad de Facebook en Harvard descrita en el texto.
El eje horizontal es (a) año de graduación y (b) dormitorio, y los colores representan las probabilidades previas aprendidas de pertenecer a cada una de las comunidades.
Estos resultados se alinean bien con el análisis original de los mismos datos por Traud et al.37, quienes realizaron una división comunitaria tradicional de la red y luego realizaron pruebas estadísticas post hoc para medir las correlaciones entre comunidades y metadatos. Encontraron fuertes correlaciones con los metadatos del año escolar, de acuerdo con nuestros resultados. Con el beneficio de la retrospectiva los resultados pueden parecer no sorprendentes-cualquiera que haya estado en la universidad sabe que un gran número de sus amigos están en el mismo año que usted- pero ciertamente podría formular hipótesis competidoras. Una alternativa que Traud et al. Se consideró que la amistad podría estar influenciada por el lugar donde viven los estudiantes, y los estudiantes que viven en el mismo dormitorio tienen más probabilidades de ser amigos, independientemente del año en que se encuentren. Traud et al. Encontró que había alguna evidencia para esta hipótesis, pero que el efecto era más débil que el de la edad, y nuestro análisis lo confirma. El panel inferior de la Fig. 4 muestra una gráfica de los priores para una división con dormitorios estudiantiles como la variable de metadatos y hay una correlación clara entre el dormitorio y la pertenencia a la comunidad, pero no es tan limpio como en el caso de la edad. Parece que hay dos grupos que se alinean fuertemente con conjuntos particulares de dormitorios (de color rojo y morado en la figura), mientras que el resto de los dormitorios son una mezcla de diferentes comunidades (la región en el centro de la figura). La impresión de que la estructura de la comunidad está más alineada con el año de graduación que con el dormitorio también está corroborada por los valores normalizados de información mutua para las dos divisiones, que son 0.668 para el año de graduación, pero 0.255 para el dormitorio.
Nuestro ejemplo de la red del mundo real final se extrae de una red de recombinación génica para el parásito humano Plasmodium falciparum, que causa la malaria. La malaria es endémica en las regiones tropicales y es responsable de aproximadamente un millón de muertes anuales, en su mayoría niños en el África subsahariana38. Durante la infección, los parásitos evaden el sistema inmune del huésped y prolongan la infección cambiando repetidamente un camuflaje de proteínas que aparece en la superficie de un glóbulo rojo infectado. Para permitir este comportamiento, cada parásito tiene un repertorio de aproximadamente 60 proteínas inmunológicamente distintas, cada una de las cuales está codificada por un gen var en el genoma del parásito39. Estos genes experimentan una recombinación frecuente, produciendo nuevas proteínas mezclando y empalmando subcadenas de genes var existentes.
El proceso de recombinación induce una red bipartita natural con dos tipos de nodos, genes var por un lado y sus subcadenas constitutivas en el otro, donde cada nodo del gen está conectado por un borde a cada subcadena que contiene40,41. La recombinación en estos genes ocurre principalmente dentro de un número de regiones altamente variables distintas (HVRs) y cada HVR representa un conjunto distinto de bordes entre los mismos nodos. Aquí nos centramos en las proyecciones de gen-gen de un modo de las subredes HVR 5 y HVR 6, que han sido previamente analizadas utilizando métodos de detección de comunidades sin metadatos40,41. Cada una de estas redes de un modo consta de 297 genes.
Analizamos estas redes utilizando como metadatos las etiquetas Cys derivadas de la secuencia HVR 6 y las etiquetas Cys-PoLV (CP) derivadas de las secuencias adyacentes a HVR 5 y 6 (refs 39, 42, 43). Ambos tipos de etiquetas dependen únicamente de las características de las secuencias: Cys indica el número de cisteínas que contiene la secuencia HVR 6 (2 o 4), mientras que CP subdivide las clasificaciones Cys en seis grupos dependiendo de los motivos de secuencias particulares. Así, cada nodo tiene dos valores de metadatos, una etiqueta Cys y una etiqueta CP. Los marcadores de Cys son biológicamente importantes porque los recuentos de cisteína han sido implicados en fenotipos severos de la enfermedad39,42.
En nuestros cálculos usamos las seis etiquetas de CP como metadatos para una división comunitaria de dos vías de la red y luego evaluamos el grado en que las comunidades inferidas se correlacionan con los metadatos Cys. La Figura 5 muestra los resultados para la red HVR 6 con y sin las etiquetas de CP como metadatos. Sin metadatos, las etiquetas Cys se mezclan entre los grupos inferidos (Figura 5a), pero con los metadatos obtenemos una partición casi perfecta (Fig. 5b). Esto indica que la etiqueta del CP se correlaciona bien con la estructura de la comunidad de la red, un hecho que se oscureció en el análisis sin metadatos. Además, las comunidades inferidas se correlacionan fuertemente con las etiquetas de Cys más gruesas, que no se mostraron al método: observar que un gen tiene dos cisteínas es altamente predictivo (96% de probabilidad) de ese gen que está en un grupo, mientras que tiene cuatro cisteínas es modestamente Predictivo (67% de probabilidad) de estar en el otro grupo. Por lo tanto, el método ha descubierto por sí mismo que las secuencias de motivos que definen las etiquetas de CP, junto con sus comunidades de red correspondientes, se correlacionan con los conteos de cisteína y sus fenotipos de enfermedad grave asociados39, 42.
Figura 5: Comunidades inferiores para la red de recombinación de genes HVR 6 de la malaria.
Las comunidades inferen (a) sin metadatos y (b) con metadatos para la red HVR 6 del parásito de la malaria humana P. falciparum, donde los valores de metadatos son los marcadores de CP para los genes y los nodos se colorean de acuerdo con su etiqueta Cys biológicamente relevante.
Las comunidades en la red HVR 6 representan patrones altamente no aleatorios de recombinación, que se cree que indican restricciones funcionales en la estructura de la proteína. Trabajos anteriores ha conjeturado que las limitaciones comunes en la recombinación span distintos HVRs [40]. Podemos probar esta hipótesis usando los métodos descritos en este artículo. No hay razón a priori para esperar que la estructura de la comunidad de HVR 6 debe correlacionar con la de HVR 5 porque el Cys y CP etiquetas se derivan de fuera de la HVR 5 secuencias-Cys etiquetas reflejan cisteína cuenta en HVR 6 mientras CP etiquetas subdivide Cys Etiquetas basadas en motivos de secuencias adyacentes a, pero fuera de, HVR 5. Aplicando nuestros métodos a HVR 5 sin metadatos (figura 6a), encontramos mezcla de los HVR 6 Cys etiquetas a través de la HVR 5 comunidades. Por el contrario, utilizando las etiquetas CP como metadatos para la red HVR 5, nuestro método encuentra una partición mucho más limpia (Figura 6b), lo que indica que de hecho las etiquetas HVR 6 Cys se correlacionan con la estructura de la comunidad de HVR 5.
Figura 6: Comunidades inferiores para la red de recombinación de genes HVR 5 de la malaria.
Las comunidades inferen (a) sin metadatos y (b) con metadatos para la red HVR 6 del parásito de la malaria humana P. falciparum, donde los valores de metadatos son los marcadores de CP para los genes y los nodos se colorean de acuerdo con su etiqueta Cys biológicamente relevante.
Discusión
Existen varias extensiones posibles de este trabajo. En el nivel más simple se podrían incluir tipos de metadatos más complejos, como combinaciones de variables discretas y continuas o variables vectoriales como coordenadas espaciales. Los metadatos también podrían incorporarse a métodos para detectar otros tipos de estructura, como jerarquías44, motivos45, estructuras núcleo-periferia46, clasificaciones47 o estructuras de espacio latente48. Y los ajustes resultantes podrían formar el punto de partida para una variedad de aplicaciones adicionales, como la predicción de enlaces perdidos o metadatos faltantes en conjuntos de datos incompletos. Estas y otras posibilidades que dejamos para el trabajo futuro.
Referencias
1. Newman, M. E. J. Networks: An Introduction Oxford Univ. Press (2010).
2. Aicher, C., Jacobs, A. Z. & Clauset, A. Learning latent block structure in weighted networks. J. Complex Networks 3, 221–248 (2015).
3. Fortunato, S. Community detection in graphs. Phys. Rep. 486, 75–174 (2010).
4. Adamic, L. A. & Glance, N. The political blogosphere and the 2004 U.S. election: divided they blog. In Proceedings of the 3rd International Workshop on Link Discovery 36–43 (2005).
5. Holme, P., Huss, M. & Jeong, H. Subnetwork hierarchies of biochemical pathways. Bioinformatics 19, 532–538 (2003).
6. Guimerà, R. & Amaral, L. A. N. Functional cartography of complex metabolic networks. Nature 433, 895–900 (2005).
7. Yang, J. & Leskovec, J. Community-affiliation graph model for overlapping community detection. In Proceedings of the 12th IEEE International Conference on Data Mining (ICDM), 1170–1175 (2012).
8. Hric, D., Darst, R. K. & Fortunato, S. Community detection in networks: structural communities versus ground truth. Phys. Rev. E 90, 062805 (2014).
9. Barthélemy, M. Spatial networks. Phys. Rep. 499, 1–101 (2011).
10. Jacobs, A. Z. & Clauset, A. A unified view of generative models for networks: models, methods, opportunities, and challenges. Preprint at http://arxiv.org/abs/1411.4070 (2014).
11. Zuev, K., Marián Boguñá, G. B. & Krioukov, D. Emergence of soft communities from geometric preferential attachment. Sci. Rep. 5, 9421 (2015).
12. Good, B. H., de Montjoye, Y.-A. & Clauset, A. Performance of modularity maximization in practical contexts. Phys. Rev. E 81, 046106 (2010).
13. Bothorel, C., Cruz, J. D., Magnani, M. & Micenková, B. Clustering attributed graphs: models, measures and methods. Network Sci. 3, 408–444 (2015).
14. Yang, J., McAuley, J. & Leskovec, J. Community detection in networks with node attributes. In Proceedings of the 13th IEEE International Conference On Data Mining (ICDM), 1151–1156 (2013).
15. Binkiewicz, N., Vogelstein, J. T. & Rohe, K. Covariate assisted spectral clustering. Preprint at http://arxiv.org/abs/1411.2158 (2014).
16. Galbrun, E., Gionis, A. & Tatti, N. Overlapping community detection in labeled graphs. Data Min. Knowl. Discovery 28, 1586–1610 (2014).
17. Hansen, T. J. & Mahoney, M. W. Semi-supervised eigenvectors for large-scale locally-biased learning. J. Mach. Learn. Res. 15, 3871–3914 (2014).
18. Zhang, Y., Levina, E. & Zhu, J. Community detection in networks with node features. Preprint at https://arxiv.org/abs/1509.01173 (2015).
19. Expert, P., Evans, T. S., Blondel, V. D. & Lambiotte, R. Uncovering space-independent communities in spatial networks. Proc. Natl Acad. Sci. USA 108, 7663–7668 (2011).
20. Peel, L. Supervised blockmodeling. ECML/PKDD Workshop on Collective Learning and Inference on Structured Data http://arxiv.org/abs/1209.5561 (2012).
21. Eaton, E. & Mansbach, R. A spin-glass model for semi-supervised community detection. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI), 900–906 (2012).
22. Zhang, P., Moore, C. & Zdeborová, L. Phase transitions in semisupervised clustering of sparse networks. Phys. Rev. E 90, 052802 (2014).
23. Moore, C., Yan, X., Zhu, Y., Rouquier, J.-B. & Lane, T. Active learning for node classification in assortative and disassortative networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 841–849 (2011).
24. Leng, M., Yao, Y., Cheng, J., Lv, W. & Chen, X. in Database Systems for Advanced Applications (eds Meng W., Feng L., Bressan S., Winiwarter W., Song W. Vol. 7826, 324–338Springer (2013).
25. Maa, X., Gaoa, L., Yongb, X. & Fua, L. Semi-supervised clustering algorithm for community structure detection in complex networks. Phys. A 389, 187–197 (2010).
26. Zhang, Z.-Y. Community structure detection in complex networks with partial background information. Europhys. Lett. 101, 48005 (2013).
27. Holland, P. W., Laskey, K. B. & Leinhardt, S. Stochastic blockmodels: some first steps. Social Networks 5, 109–137 (1983).
28. Karrer, B. & Newman, M. E. J. Stochastic blockmodels and community structure in networks. Phys. Rev. E 83, 016107 (2011).
29. Decelle, A., Krzakala, F., Moore, C. & Zdeborová, L. Inference and phase transitions in the detection of modules in sparse networks. Phys. Rev. Lett. 107, 065701 (2011).
30. Mossel, E., Neeman, J. & Sly, A. Reconstruction and estimation in the planted partition model. Probab. Theory Related Fields 162, 431–461 (2015).
31. Moody, J. Race, school integration, and friendship segregation in America. Am. J. Sociol. 107, 679–716 (2001).
32. Danon, L., Duch, J., Diaz-Guilera, A. & Arenas, A. Comparing community structure identification. J. Stat. Mech. 2005, P09008 (2005).
33. McDaid, A. F., Greene, D. & Hurley, N. Normalized mutual information to evaluate overlapping community finding algorithms. Preprint at http://arxiv.org/abs/1110.2515 (2011).
34. Brose, U. et al. Body sizes of consumers and their resources. Ecology 86, 2545–2545 (2005).
35. Jacob, U. Trophic Dynamics of Antarctic Shelf Ecosystems Food Webs and Energy Flow Budgets PhD thesis, Univ. Bremen (2005).
36. Woodward, G. et al. Body size in ecological networks. Trends Ecol. Evol. 20, 402–409 (2005).
37. Traud, A. L., Mucha, P. J. & Porter, M. A. Social structure of Facebook networks. Phys. A 391, 4165–4180 (2012).
38. Report, W. M. World Malaria Report World Health Organization (2012).
39. Bull, P. C. et al. Plasmodium falciparum variant surface antigen expression patterns during malaria. PLOS Pathog. 1, e26 (2005).
40. Larremore, D. B., Clauset, A. & Buckee, C. Z. A network approach to analyzing highly recombinant malaria parasite genes. PLOS Comput. Biol. 9, e1003268 (2013).
41. Larremore, D. B., Clauset, A. & Jacobs, A. Z. Efficiently inferring community structure in bipartite networks. Phys. Rev. E 90, 012805 (2014).
42. Warimwe, G. M. et al. Plasmodium falciparum var gene expression is modified by host immunity. Proc. Natl Acad. Sci. USA 106, 21801–21806 (2009).
43. Bull, P. C. et al. An approach to classifying sequence tags sampled from Plasmodium falciparum var genes. Mol. Biochem. Parasitol. 154, 98–102 (2007).
44. Clauset, A., Moore, C. & Newman, M. E. J. Hierarchical structure and the prediction of missing links in networks. Nature 453, 98–101 (2008).
45. Milo, R. et al. Network motifs: simple building blocks of complex networks. Science 298, 824–827 (2002).
46. Borgatti, S. P. & Everett, M. G. Models of core/periphery structures. Social Networks 21, 375–395 (1999).
47. Ball, B. & Newman, M. E. J. Friendship networks and social status. Network Sci. 1, 16–30 (2013).
48. Hoff, P. D., Raferty, A. E. & Handcock, M. S. Latent space approaches to social network analysis. J. Am. Stat. Assoc. 97, 1090–1098 (2002).
49. Yedidia, J. S., Freeman, W. T. & Weiss, Y. in Exploring Artificial Intelligence in the New Millennium (eds Lakemeyer G., Nebel B. 239–270Morgan Kaufmann (2003).
50. Cover, T. M. & Thomas, J. A. Elements of Information Theory 2nd edn Wiley (2006).
Italian original paper ( PDF)
French full preprint ( PDF)
English summary* ( HTML)
