miércoles, 28 de junio de 2017

Status económico y posición en la red

Infiriendo el estatus económico personal desde la ubicación de la red social

Shaojun Luo, Flaviano Morone, Carlos Sarraute, Matías Travizano y Hernán A. Makse
Nature Communications 8, Número del artículo: 15227 (2017)
Doi: 10.1038 / ncomms15227


Resumen -
Se cree comúnmente que los patrones de lazos sociales afectan la situación económica de los individuos. Aquí traducimos este concepto en una definición operativa a nivel de red, lo que nos permite inferir el bienestar económico de los individuos a través de una medida de su ubicación e influencia en la red social. Analizamos dos fuentes de gran escala: las telecomunicaciones y los datos financieros de la población de todo un país. Nuestros resultados muestran que la ubicación de un individuo, medida como la influencia colectiva óptima para la integridad estructural de la red social, está altamente correlacionada con la situación económica personal. Los patrones de influencia social observados imitan los patrones de desigualdad económica. Para el uso pragmático y la validación, llevamos a cabo una campaña de marketing que muestra un aumento de tres veces en la tasa de respuesta dirigida a los individuos identificados por nuestras métricas de red social en comparación con la orientación aleatoria. Nuestra estrategia también puede ser útil para maximizar los efectos de las políticas de estímulo económico a gran escala.


Introducción

El problema de larga data de cómo la red de contactos sociales1,2,3 influye en la situación económica de los individuos ha llamado la atención debido a su importancia en una diversidad de temas socioeconómicos que van desde la política al mercadeo4,5,6,7. Los análisis teóricos han señalado la importancia de la red social en la vida económica5 como medio para difundir las ideas8,9 a través de los efectos de los "agujeros estructurales" 10 y los "lazos débiles" en la red4. Del mismo modo, la investigación ha reconocido el efecto económico positivo de ampliar los contactos de un individuo fuera de su propio grupo social estrechamente conectado1,11,12,13. Mientras que el trabajo previo ha establecido la importancia de la influencia de la red social a la situación económica, el problema de cómo cuantificar dicha correspondencia a través de las redes sociales o métricas3,14 permanece abierto.

Los estudios que emplean datos de comunicación telefónica móvil y otros indicadores sociales han encontrado una variedad de efectos en la red sobre indicadores socioeconómicos como oportunidades de empleo15,16, movilidad social17,18,19, desarrollo económico6,20,21,22 y comportamiento del consumidor23,24. Un trabajo reciente también proporciona evidencia de tales efectos sobre la riqueza de un individuo y destaca la necesidad de mejores indicadores25. Recientemente, un estudio numérico ha probado el efecto de la diversidad de redes en el desarrollo económico6. Este estudio analizó el desarrollo económico definido a nivel comunitario. Sin embargo, la cuestión de cómo se pueden utilizar las métricas de redes sociales para inferir la situación financiera a nivel individual, necesaria, por ejemplo, para las campañas de mercadotecnia o de intervención social, sigue sin respuesta. La dificultad se debe, en parte, a la falta de datos empíricos que combinen la información financiera de un individuo con el patrón de sus lazos sociales a nivel de red en gran escala de toda la sociedad.

En este trabajo abordamos este problema directamente combinando dos grandes conjuntos de datos: una red social de toda la población de un país latinoamericano y datos bancarios financieros a nivel individual. Descubrimos que la optimalidad de la localización de un individuo en la red, medida por la influencia colectiva (CI) métrica26, está altamente correlacionada con la situación económica del individuo a nivel de población: cuanto mayor es el CI, mayor es el nivel socioeconómico. La bondad de ajuste de esta correlación puede ser tan alta como R2 = 0,99 cuando también se incluye la edad. Estos resultados indican que la optimización de la ubicación en la red social medida por la métrica CI puede predecir con precisión los indicadores socioeconómicos a nivel personal.

El 1% superior del estrato económico tiene patrones de red precisos de formación de enlaces que muestran relativamente baja conectividad local rodeada por una jerarquía de centros estratégicamente ubicados en esferas de influencia de creciente tamaño en la red. Este patrón no se observa en el resto de la población, en particular, en el 10% inferior caracterizado por bajos valores de CI. Así, la influencia medida a partir de patrones de redes sociales imita la desigualdad observada en el estado económico27.

También encontramos una alta correlación entre la diversidad de vínculos de los individuos y su situación financiera (R2 = 0,96), empleando el análisis basado en la ubicación de la red y la edad. El análisis de la covarianza sugiere que el efecto de la influencia de la red es significativo e independiente de otros factores. Validamos estos resultados llevando a cabo una campaña de marketing dirigida en la que comparamos la tasa de respuesta para diferentes grupos de personas con diferentes ubicaciones de red. Al dirigir el grupo con los valores CI superiores, la tasa de respuesta puede llegar hasta 1%; Aproximadamente tres veces la tasa de respuesta encontrada por orientación al azar y cinco veces la tasa de respuesta de las personas de CI baja.

Así, los individuos con alto nivel socioeconómico (1% superior) desarrollan un patrón muy característico de lazos sociales en comparación con el 10% inferior. Si bien este resultado se puede esperar, es notable que la diferencia en el patrón de las interacciones sociales entre los ricos y los pobres pueden ser capturados con precisión por una métrica de red midiendo su CI en la red social26. La capa socioeconómica superior de la sociedad también representa el conjunto mínimo de personas que proporciona integridad a toda la red social a través de su gran CI. El hecho de que los individuos de mayor estatus económico estén ubicados en regiones de gran CI en la red eleva la evidencia anecdótica anterior a un principio de organización de la red a través de la optimización de la influencia de las personas afluentes que afectan la integridad estructural de la red social. Al mismo tiempo, sugiere la aparición del fenómeno de CI en la sociedad como resultado de la optimización de las interacciones socioeconómicas.


Resultados

Construcción de redes

La red social se construye a partir de datos móviles (llamadas y metadatos SMS) y de comunicaciones residenciales recopilados por un período de 122 días (Nota complementaria 1, datos agregados en kcorelab.com). La base de datos contiene 1.10 × 108 usuarios de teléfono. Después de filtrar los nodos no humanos activos mediante un modelo aprendido por la máquina y entrenado en el comportamiento de la comunicación natural humana (Nota Complementaria 2, con Figuras 1-4 adicionales), construimos una red final de 1,07 × 108 nodos en un componente conectado gigante hecho de 2,46 × 108 enlaces. Los lazos, o enlaces, en la red corresponden a comunicaciones telefónicas, ya que esperamos que los patrones de comunicación sean indicativos de la ubicación de un individuo en la red social28,29,30. El costo financiero del uso de los servicios telefónicos hace posible que exista un sesgo sistemático en la cantidad de personas ricas que utilizan los servicios telefónicos en relación con las personas que tienen menos dinero para gastar en llamadas telefónicas. Aunque el efecto podría ser limitado (nota complementaria 1), no podemos descartar esta posibilidad con los datos actuales.

La situación financiera se obtiene del límite de crédito combinado de las tarjetas de crédito asignadas por las instituciones bancarias a cada cliente. El límite de crédito se basa en factores compuestos de ingresos e historial de crédito y, por lo tanto, refleja la situación financiera del individuo (ver discusión en la Nota Suplementaria 1). El límite de crédito se extrae de una base de datos de bancos cifrados e identificado por los números de teléfono de los clientes cifrados registrados en el banco. Por lo tanto, somos capaces de correlacionar precisamente la información financiera de un individuo con su ubicación social en la red de llamadas telefónicas a nivel de país. Hay 5.02 × 105 clientes bancarios que han sido identificados en la red móvil cuyo límite de crédito oscila entre USD $ 50 a $ 3.5 × 105 (convertido desde el país de estudio). Por lo tanto, los conjuntos de datos están conectados con precisión proporcionando una oportunidad sin precedentes para probar la correlación entre la ubicación de la red y el estado financiero.

A pesar de la gran escala de nuestra fuente de datos, observamos que trabajar en un solo país específico como en el presente estudio no es suficiente para otorgar generalidad a nuestros resultados. Para probar la validez general de los resultados actuales, se necesitaría el acceso a conjuntos de datos bancarios y de comunicaciones a nivel de toda la población de otros países. A medida que más conjuntos de datos estén disponibles, la generalidad de nuestros resultados puede ser probada a través de diferentes sistemas económicos y sociales.

La Figura 1a, b muestra los patrones de comunicación geolocalizados en todo el país de los individuos en el 1% superior y el 10% inferior de los límites de crédito, respectivamente. La desigualdad en los patrones de comunicación entre la clase económica superior y la más baja es sorprendente y imita la desigualdad económica a nivel de país27. Es visualmente evidente que el 1% superior (que representa el 45,2% del crédito total en el país) muestra un patrón de comunicación completamente diferente que el 10% inferior; El primero se caracteriza por vínculos más activos y diversos, especialmente conectando ubicaciones remotas y comunicándose con otras personas igualmente afluentes. Otros resultados utilizando el análisis de entropía también sugieren que la estructura de la red puede ser significativamente diferente entre las personas en el ranking de cuantil superior e inferior del límite de crédito (nota complementaria 3, cuadro complementario 1). Ejemplos particulares de las redes de ego ampliadas para dos individuos (con el mismo número de lazos) que ocupan el 1% superior y el 10% inferior proporcionan una imagen ampliada de tales diferencias (Fig. 1c, d, respectivamente). Los 1-por ciento más ricos tienen una mayor diversidad de contactos móviles y están ubicados centralmente, rodeados por otras personas altamente conectadas (hubs de red). Por otro lado, los individuos más pobres tienen una diversidad de contacto baja y están débilmente conectados a menos centros. El quid de la cuestión es encontrar una métrica de red social confiable para cuantificar esta diferencia visual en los patrones de estructura de red entre los ricos y los pobres, como se muestra a continuación.

Figura 1: Los patrones de influencia de la red imitan patrones de desigualdad de ingresos.

Visualización de la actividad de comunicación de la población en el primer 1% (con límite de crédito superior a USD $ 25.000, convertido, en el país de estudio) y (b) inferior 10% (con límite de crédito inferior a USD $ 600) del total Clases de límite de crédito. Los enlaces están entre los clientes del banco que han registrado su código postal. La resolución de ambas parcelas es de 1.700 × 1.000. El número de clientes bancarios dentro de cada comunidad se refleja en el tamaño del nodo. El límite de crédito promedio se indica mediante la escala de grises de un nodo. El color y grosor de los bordes refleja el número de eventos de comunicación entre diferentes comunidades. (C) Ejemplos de la red de ego (extendida a dos capas) para un individuo en la clase rica superior del 1% y (d) un individuo en la clase inferior del 10%. Las redes muestran dos patrones distintos de lazos sociales de acuerdo con la alta y baja situación económica: la primera se caracteriza por una IC grande, la segunda por CI baja. (E) Representación esquemática de una red bajo la descomposición de k-shell33. (F) Ejemplo de cálculo de CI. El CI Bola de radio alrededor del nodo i es el conjunto de nodos contenidos dentro de la esfera y ∂Ball es el conjunto de nodos en el límite (marrón). CI es el grado-menos-uno del nodo central veces la suma del grado-menos-uno de los nodos en el límite de la esfera de influencia.


Influencia de la red y situación financiera

Se han considerado muchas métricas o centralidades para caracterizar la influencia o importancia de los nodos en una red3,14,31. Aquí consideramos sólo aquellas centralidades que pueden ser escaladas hasta el tamaño de la red grande considerado aquí (figura 1e, nota adicional 4): (a) la centralidad del grado ki (número de lazos del individuo i) es una de las más simples3, (B) PageRank, de Google fame32, es una centralidad de vectores propios que incluye la importancia no sólo del grado, sino también de los vecinos más próximos, (c) el índice ks  del k-shell de un nodo (Figura 1e), es decir, La localización de la cáscara obtenida mediante la poda iterativa de todos los nodos con un grado k<ks (referencia 33), y (d) la CI de un nodo de grado ki  (figura 1f) en una esfera de influencia del tamaño  definido por la frontera de la bola de influencia , y se prevé que sea  por la teoría de percolación óptima26. A diferencia de las otras centralidades heurísticas, CI se deriva de la teoría de la maximización de la influencia en la red34. Por lo tanto, los nodos CI superiores se identifican como influenciadores o distribuidores superiores de información, y lo son colocándose en ubicaciones estratégicas en el centro de esferas rodeadas por cubos situados jerárquicamente a distancias (figura 1d). Estos influyentes colectivos constituyen también un conjunto óptimo que proporciona integridad al tejido social: son el número más pequeño de personas que, al salir de la red (proceso matemáticamente conocido como percolación óptima26), desintegraría la red en pequeñas piezas desconectadas.

Por definición, todas las métricas tienen similitudes (por ejemplo, son proporcionales a k, y PageRank y CI se basan en los autovalores más grandes de las matrices de adyacencia y no retroceso, respectivamente26), y de hecho, encontramos que sus valores en La red de comunicaciones telefónicas están correlacionadas (Tabla 2 suplementaria). Más interesante, la Fig. 2 proporciona evidencia de correlación de las cuatro métricas de la red con el estado financiero (límite de crédito clasificado) cuando controlamos por edad, lo que indica que la ubicación de la red se correlaciona con la situación financiera. En esta figura, se representa la fracción de individuos ricos (definida como el cuarto cuantil superior, equivalente a un límite de crédito superior a USD $ 4.000, véase la Nota Complementaria 5 para detalles sobre los métodos de validación y la referencia 30) en una cuadrícula de muestreo para un valor dado De edad y métrica social como se indica.


Figura 2: Fracción de individuos ricos versus edad y métricas de red.

Correlación entre la fracción de individuos ricos frente a la edad y (a) grado k  (R2=0.92), (b) k-shell (R2=0.96), (c) PageRank (R2=0.96) y (d) log10CI (R2=0.93). Sólo se muestran en la parcela los grupos con población> 20. Las cuatro métricas se correlacionan bien con la situación financiera cuando se consideran con la edad. Otras correlaciones se estudian en la Nota Suplementaria 6, indicando que CI podría ser considerada como la métrica más conveniente de los cuatro debido a su alta resolución.

Si bien todas las métricas sociales muestran correlaciones con el estado financiero cuando se consideran con la edad (figura 2), la pregunta sigue siendo cuál métrica es el predictor más eficiente. Se observan correlaciones fuertes con el bienestar económico para los pares de características (edad, k-shell, R2 = 0,96, Fig. 2b) y (edad, CI; R2 = 0,93, Fig. 2d). La Nota Suplementaria 6 (Figuras Adicionales 7-9) proporciona una comparación adicional cuando se consideran las métricas por sí solas, indicando que k-shell y CI mejor captan la correlación con el límite de crédito. Entre estas dos métricas, CI garantiza un requisito para una correlación fuerte y suficiente resolución. K-shell no puede capturar más detalles debido a su limitación de valores (k-shell varía de 1 a 23, dividiendo a toda la población en este pequeño número de conchas con una típica concha conteniendo decenas de millones de personas), mientras que CI abarca más de siete órdenes de magnitud; Véase la Fig. 5. Esta alta resolución implica que CI es una firma social más precisa para la situación financiera de los individuos. Según su definición (figura 1d), un nodo CI superior es un hub moderado a fuerte rodeado por otros centros jerárquicamente situados a distancia. Sin embargo, enfatizamos que CI es sólo una estrategia útil por las razones expuestas anteriormente, y de ninguna manera la única o mejor estrategia para correlacionar la riqueza de los individuos y su influencia en la red.

Si bien la teoría detrás de CI es una maximización global de la influencia, CI representa la aproximación local a esta optimización global. Así, CI representa un equilibrio entre una optimización global y su aproximación local, teniendo en cuenta las primeras 2 o 3 capas de vecinos a través del parámetro , que representa el tamaño de la esfera de influencia utilizada para definir la importancia de un nodo. 1d. Al cambiar , descubrimos que CI con es suficiente para capturar la correlación entre la influencia de la red y la riqueza (Figura 10).

Para realizar un seguimiento del efecto de la IC independientemente de la edad, se investigan los efectos de la CI dentro de dos grupos de edad específicos en la Fig. 3a, b. En ambos grupos de edad, la CI alta siempre está acompañada por una población más alta de personas ricas. Una pendiente relativamente menor en el grupo de edad <30 sugiere que el efecto de la red de CI es más sensible para las personas mayores con niveles económicos más maduros y estables que para los jóvenes (Figura 6). Cuando combinamos la edad y la clasificación de cuantil CI en un compuesto de edad-red: ANC=αAge+(1−α) CI, con α = 0,5, se logra una notable correlación (R2 = 0,99, Fig. 3c). Al combinar la información de la red con la edad, la probabilidad de identificar a las personas con un límite de crédito alto alcanza el ~ 70% al nivel más alto de ingresos. Este nivel de precisión hace que el modelo sea práctico para inferir la aptitud financiera de los individuos usando la CI de la red como se muestra a continuación.

Figura 3: Fracción de individuos ricos en diferentes edades y grupos de clasificación compuestos.

Correlación entre la fracción de individuos ricos dada por el límite máximo de crédito del 25% y CI en diferentes grupos de edad de (a) 18-30 y (b)> 45. Las correlaciones entre la situación económica superior y la IC grande determinada por los valores de CI en diferentes edades son significativas en todos los grupos de edad, mientras que la pendiente de la regresión lineal es mayor en el grupo de mayor edad (0,053 comparado con 0,037). (C) Clasificación compositiva edad-red ANC = 1/2 Edad + CI 1/2, y (d) clasificación mixta edad-diversidad ADC = 1/2 Edad + 1/2 DR. Mediante la combinación de las métricas de red con la edad en un índice compuesto, la posibilidad de identificar a las personas de alto nivel financiero alcanza ~ 70% para valores altos del compuesto. Ambos R2 muestran un alto nivel de correlación (R2 = 0,99 y 0,96 para ANC y ADC, respectivamente), haciendo ambos compuestos buenos predictores de la riqueza en aplicaciones prácticas.

Validación por campaña de marketing

Para validar nuestra estrategia, realizamos una campaña de marketing social cuyo objetivo es la adquisición de nuevos clientes de tarjetas de crédito, mediante el envío de mensajes a las personas afluentes (identificadas por sus valores de CI) e invitando a los destinatarios a iniciar una solicitud de producto (nota complementaria 8) . Observamos que en este experimento usamos un conjunto de datos independiente de un marco de tiempo diferente, y usamos solamente los valores de CI extraídos de la red para clasificar las personas objetivo. En concreto, utilizamos la red de comunicaciones resultante de la agregación de llamadas y SMS intercambiados entre usuarios durante un período de 91 días. La red social resultante contiene 7,19 × 107 personas y 3,51 × 108 enlaces. La campaña se llevó a cabo en un total de 656.944 personas que fueron objeto de un mensaje SMS ofreciendo el producto de acuerdo a sus valores de CI en la red social. También enviamos mensajes a un grupo de control de 48.000 personas, elegidas al azar. Para evaluar la campaña, se midió la tasa de respuesta, es decir, el número de receptores que solicitaron el producto dividido por el número de personas objetivo, en función de la CI. En el grupo de control, la tasa de respuesta a los mensajes fue 0,331%. Nuestros resultados muestran que los grupos de IC creciente muestran un aumento en su tasa de respuesta, con una triple ganancia sana en la tasa de respuesta de los principales influenciadores (identificados por los valores superiores de CI) en comparación con el caso aleatorio. Cuando comparamos la respuesta de la IC alta con la de CI más baja, la tasa de respuesta se quintuplica. Los resultados del experimento se resumen en la Tabla 1 y en la Fig. 4.


Tabla 1: Resultados de la campaña de marketing de la vida real.


Rango CI CuentaCuantilRespuestasTasa de respuesta
(0, 48)66,4950.11700.26%
(48, 246)65,1640.22180.33%
(246, 600)65,9610.33160.48%
(600, 1,144)65,3760.43320.51%
(1,144, 1,992)65,4770.53630.55%
(1,992, 3,408)65,4770.64580.70%
(3,408, 6,032)65,7360.74930.75%
(6,032, 11,772)65,6410.85550.8%
(11,772, 28,740)65,6830.96571.0%
(28,740, 2,719,354)65,6831.05730.87%
  1. Los individuos ('Cuenta') fueron apuntados según su ranking de cuantil CI en toda la red social obtenida de la actividad de comunicaciones telefónicas. Se calculó la respuesta a la campaña ("Sí contestó") para calcular la tasa de respuesta.

Figura 4: Tasa de respuesta versus cuantil de CI en la campaña de marketing de la vida real basada en CI.

La tasa de respuesta aumenta aproximadamente linealmente con la clasificación CI. La campaña de CI-targeting muestra una ganancia triple para los principales influyentes con CI alta, en comparación con una campaña dirigida a un grupo control aleatorizado.


Análisis de la covarianza

Observamos que nuestra validación es indirecta ya que no es una predicción directa de la situación financiera, sino una tasa de respuesta exitosa a una campaña de marketing. Esta tasa de éxito puede depender en realidad de una serie de otros factores que pueden correlacionarse con la centralidad de la red. Por lo tanto, la métrica de CI puede no ser necesariamente la única causa de la tasa de éxito de la campaña específica (por ejemplo, la ubicación geográfica puede ser también importante). Para abordar este punto, realizamos un análisis de la covarianza35 sobre todas las características a las que tenemos acceso (edad, sexo y código postal registrado) para probar la varianza causada por las métricas de la red y otros factores (detalles en la Nota Complementaria 5 y Tabla 3). El análisis de la covarianza muestra que los efectos de las métricas de la red son independientes de los de los otros factores. La correlación entre el CI y la fracción de personas adineradas es positiva y significativa (P <0,001) en todos los grupos de comunidades geográficas, entre géneros y entre todas las edades mayores de 24 años (Figura 6). Los mismos resultados significativos también se obtienen bajo diferentes umbrales de riqueza. Estos efectos de red significativos y sólidos implican que las métricas de red pueden ser un indicador potencial de la situación financiera.

Diversidad de la red y situación financiera

Nuestros conjuntos de datos combinados también ofrecen la posibilidad de probar la importancia de la diversidad de vínculos, medida por lazos con comunidades distantes de la red que no están directamente conectadas con la comunidad de un individuo, a nivel de individuos individuales4,5,6. Para ello, primero detectamos las comunidades en la red social mediante la aplicación de algoritmos rápidos de detección de la modularidad de los pliegues (Nota Suplementaria 7, Figura 11) 36,37. La diversidad de los vínculos de un individuo puede ser cuantificada a través de la relación de diversidad DR = Wout / Win, definida como la proporción de eventos de comunicación total con personas fuera de su propia comunidad, Wout, con aquellos dentro de su propia comunidad, Win. Esta relación está débilmente correlacionada con CI (R = 0,4), lo que sugiere que captura una característica diferente de la influencia de la red. Implementamos las mismas estadísticas de clasificación compuesta como antes, resultando en un compuesto de diversidad de edades ADC = αAge + (1-α) DR, con un peso α = 0.5. El resultado (Fig. 3d) muestra que ADC se correlaciona con el bienestar financiero individual, generalizando los resultados agregados en ref. 6 a nivel individual. Así, las métricas sociales consideradas, DR y CI, expresan el hecho de que los niveles económicos más altos se correlacionan con la capacidad de comunicarse con individuos fuera de la comunidad social local estrechamente unida, una medida del principio de fuerza de los lazos débiles de Granovetter En ubicaciones de red particulares de CI alto que son óptimas para la difusión de la información y la estabilidad estructural de la red social. Observamos que no se puede establecer una inferencia causal con los datos actuales.

Discusión

Este resultado destaca la posibilidad de predecir el estado financiero y los beneficios de las políticas socialmente orientadas basadas en métricas de red, lo que conduce a mejoras tangibles en las campañas de marketing social. El alto rendimiento de la CI entre las métricas de la red también sugiere el posible papel de acceder y mediar información en la oportunidad financiera y el bienestar5. Esto tiene un impacto inmediato en el diseño de campañas de marketing óptimas mediante la identificación de los objetivos ricos sobre la base de su posición influyente en una red social. Este hallazgo puede también elevarse al nivel de un principio, que explicaría la aparición del fenómeno de CI mismo como resultado de la optimización de las interacciones socioeconómicas.


Referencias

1. Newman, M. E. The structure and function of complex networks. SIAM Rev. 45, 167–256 (2003).
2. Vespignani, A. & Caldarelli, G. Large Scale Structure and Dynamics of Complex Networks: from Information Technology to Finance and Natural Science World Scientific (2007).
3. Wasserman, S. & Faust, K. Methods and Applications, Vol. 8 (Cambridge Univ. Press, 1994).
4. Granovetter, M. S. The strength of weak ties. Am. J. Sociol. 78, 1360–1380 (1973).
5. Granovetter, M. The impact of social structure on economic outcomes. J. Econ. Perspect. 19, 33–50 (2005).
6. Eagle, N., Macy, M. & Claxton, R. Network diversity and economic development. Science 328, 1029–1031 (2010).
7. Singh, V. K., Freeman, L., Lepri, B. & Pentland, A. S. in 2013 Internation Conference on Social Computing (SocialCom) 174–179 (Washington, DC, USA, 2013).
8. Powell, W. W. & Smith-Doerr, L. The Handbook of Economic Sociology, Vol. 368, 380 (eds Neil J. Smelser & Richard Swedberg) (Princeton University Press, Princeton, NJ, USA, 1994).
9. Strang, D. & Soule, S. A. Diffusion in organizations and social movements: from hybrid corn to poison pills. Annu. Rev. Sociol. 24, 265–290 (1998).
10. Burt, R. S. Structural Holes: the Social Structure of Competition Harvard Univ. Press (2009).
11. Page, S. E. The Difference: how the Power of Diversity Creates Better Groups, Firms, Schools, and Societies Princeton Univ. Press (2008).
12. Fernandez, R. M. & Weinberg, N. Getting a job: networks and hiring in a retail bank. Graduate Business School Research Paper No. 1382, 1 (University of Stanford, CA, USA, 1996).
13. Zimmer, C. The Art and Science of Entrepreneurship 3–23 (Ballinger, 1986).
14. Freeman, L. C. Centrality in social networks conceptual clarification. Soc. Networks 1, 215–239 (1978).
15. Toole, J. L. et al. Tracking employment shocks using mobile phone data. J. R. Soc. Interface 12, 2015.0185 (2015).
16. Seidel, M.-D. L., Polzer, J. T. & Stewart, K. J. Friends in high places: the effects of social networks on discrimination in salary negotiations. Admin. Sci. Q. 45, 1–24 (2000).
17. Cho, E., Myers, S. A. & Leskovec, J. in Proceedings of the 17th ACM (International Conference on Knowledge Discovery and Data Mining) 1082–1090 (San Diego, CA, USA, 2011).
18. Phithakkitnukoon, S., Smoreda, Z. & Olivier, P. Socio-geography of human mobility: a study using longitudinal mobile phone data. PLoS ONE 7, e39253 (2012).
19. Deville, P. et al. Scaling identity connects human mobility and social interactions. Proc. Natl Acad. Sci. USA 113, 7047–7052 (2016).
20. Pappalardo, L. et al. An analytical framework to nowcast well-being using mobile phone data. Int. J. Data Sci. Anal. 2, 75–92 (2016).
21. Pan, W., Ghoshal, G., Krumme, C., Cebrian, M. & Pentland, A. Urban characteristics attributable to density-driven tie formation. Nat. Commun. 4, 1961 (2013).
22. Gutierrez, T., Krings, G. & Blondel, V. D. Evaluating socio-economic state of a country analyzing airtime credit and mobile phone datasets. Preprint at https://arxiv.org/abs/1309.4496 (2013).
+ Show context
23. Salah, A. A., Lepri, B., Pianesi, F. & Pentland, A. S. in International Workshop on Human Behavior Understanding (eds Salah, A. & Lepri, B.) 1–15 (Springer, 2011).
24. Decuyper, A. et al. Estimating Food Consumption and Poverty Indices with Mobile Phone Data. Technical Report (United Nations Global Pulse, New York, USA, 2014). Preprint at https://arxiv.org/abs/1412.2595 (2014).
25. Blumenstock, J. in Proceedings of 20th ACM SIGKDD (International Conference on Knowledge Discovery and Data Mining) (New York, NY, USA, 2014).
26. Morone, F. & Makse, H. A. Influence maximization in complex networks through optimal percolation. Nature 524, 65–68 (2015).
27. Stiglitz, J. E. The Price of Inequality: how Today’s Divided Society Endangers our Future W. W. Norton & Company (2012).
28. Onnela, J.-P. et al. Structure and tie strengths in mobile communication networks. Proc. Natl Acad. Sci. USA 104, 7332–7336 (2007).
29. Gonzalez, M. C., Hidalgo, C. A. & Barabasi, A.-L. Understanding individual human mobility patterns. Nature 453, 779–782 (2008).
30. Eagle, N., Pentland, A. S. & Lazer, D. Inferring friendship network structure by using mobile phone data. Proc. Natl Acad. Sci. USA 106, 15274–15278 (2009).
31. Pei, S. & Makse, H. A. Spreading dynamics in complex networks. J. Stat. Mech. Theor. Exp. 2013, P12002 (2013).
32. Page, L., Brin, S., Motwani, R. & Winograd, T. The Pagerank Citation Ranking: bringing Order to the Web. Technical Report 422 (Stanford InfoLab, Palo Alto, CA, USA, 1998).
33. Kitsak, M. et al. Identification of inuential spreaders in complex networks. Nat. Phys. 6, 888–893 (2010).
34. Kempe, D., Kleinberg, J. & Tardos, É. in Proceedings of 9th ACM SIGKDD (International Conference on Knowledge Discovery and Data Mining) 137–146 (Seattle, WA, USA, 2003).
35. Wildt, A. R. & Ahtola, O. Analysis of Covariance, Vol. 12 (Sage Publications, 1978).
36. Blondel, V. D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. Fast unfolding of communities in large networks. J. Stat. Mech. Theor. Exp. 2008, P10008 (2008).
37. Newman, M. E. Analysis of weighted networks. Phys. Rev. E 70, 056131 (2004).




sábado, 24 de junio de 2017

Estructura e inferencia en redes con metadatos

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).