Aaron Clauset,[1], M. E. J. Newman, [2] y Cristopher Moore1, [3]
[1] Department of Computer Science, University of New Mexico, Albuquerque, NM 87131
[2] Department of Physics and Center for the Study of Complex Systems,
University of Michigan, Ann Arbor, MI 48109
[3] Department of Physics and Astronomy, University of New Mexico, Albuquerque, NM 87131
Archivo PDF
El descubrimiento y análisis de estructuras de comunidad en redes es un tema de interés reciente considerable dentro de la comunidad de la física, pero la mayoría de los métodos propuestos hasta ahora no son adecuados para redes muy grandes debido a su coste computacional. Aquí presentamos un algoritmo de clasificación jerárquico para detectar estructura de la comunidad que es más rápido que muchos algoritmos en competencia: su tiempo de funcionamiento en una red con n vértices y m enlaces es O (md log n), donde d es la profundidad de la dendrograma que describe la estructura de la comunidad . Muchas redes del mundo real son escasos y jerárquica, con m ~ n y d ~ log n, en cuyo caso el algoritmo se ejecuta en tiempo esencialmente lineal, O (n log2 n). Como un ejemplo de la aplicación de este algoritmo que utilizamos para analizar una red de artículos para la venta en el sitio web de un gran minorista en línea, los elementos de la red que están unidas si se compran con frecuencia por el mismo comprador. La red cuenta con más de 400 000 vértices y 2 millones de aristas. Se demuestra que nuestro algoritmo puede extraer comunidades significativas a partir de esta red, revelando patrones a gran escala presentes en los hábitos de compra de los clientes.
Figura 2: Una visualización de la estructura de la comunidad a la máxima modularidad. Tenga en cuenta que los principales algunas comunidades tienen un gran número de comunidades "satélites" conectadas sólo a ellas (arriba, abajo a la izquierda, abajo a la derecha). Además, algunos pares de las principales comunidades tienen grupos de comunidades más pequeñas que actúan como "puentes" entre ellos (por ejemplo, entre la parte inferior izquierda e inferior derecha, cerca del centro)
No hay comentarios:
Publicar un comentario