Algoritmo para la detección de estructuras núcleo-periferia en redes

Identificación de la estructura núcleo-periferia en redes

Xiao Zhang, Travis Martin, y M. E. J. Newman,


Archivo PDF en Arxiv.org

Resumen

Muchas redes se pueden descomponer útilmente en un núcleo denso más una estructura periférica, ligeramente conectada. Aquí se propone un algoritmo para realizar una descomposición de este tipo en redes empíricas de datos utilizando métodos de inferencia estadística. Nuestro método se ajusta a un modelo generativo de la estructura núcleo-periferia a los datos observados utilizando una combinación de un algoritmo de maximización de valor esperado para calcular los parámetros del modelo y un algoritmo de propagación de creencia para calcular la descomposición en sí. Encontramos que el método es eficiente, escalando fácilmente a redes con un millón o más nodos y lo probamos en una variedad de redes, incluyendo ejemplos del mundo real, así como puntos de referencia generados por computadora, para lo cual identifica con éxito la estructura núcleo-periferia conocida con baja tasa de error. También demostrar que el método es inmune a la transición de detectabilidad observada en el problema de detección de la comunidad relacionada, que impide la detección de la estructura de la comunidad cuando la estructura es demasiado débil. No existe tal transición para la estructura núcleo-periferia, que es detectable, aunque con algún error estadístico, no importa cuán débil sea.


Fig. 3 (izquierda): División núcleo-periferia de una representación de 1470 nodos de Internet a nivel de sistemas autónomos [16].
Los nodos colocados en el núcleo por nuestro análisis se dibujan más grandes y en azul; Los nodos en la periferia son más pequeños y en amarillo. La red fue construida a partir de los datos del Proyecto Rutas de Oregón y representa una instantánea más antigua, elegida para el tamaño relativamente pequeño de la red. Nuestros métodos pueden aplicarse fácilmente a redes más grandes, pero un tamaño menor hace que la visualización de los resultados sea más clara.
FIG. 4 (derecha): División núcleo-periferia de una red de hipervínculos entre blogs políticos tomados de [35]. La red se separa naturalmente en comunidades conservadoras y liberales, claramente visibles como los dos grupos en este cuadro. Dentro de cada grupo nuestro algoritmo encuentra un núcleo y una periferia separados indicados por los nodos azules y amarillos respectivamente.

1409 4813