Encontrando estructura de comunidad en redes sociales de mega-escala
Ken Wakita [1] y Toshiyuki Tsurumi [2]
[1] Instituto de Tecnología de Tokio
2-12-1 Ookayama, Meguro-ku
Tokyo 152-8552, Japón
wakita@is.titech.ac.jp
[2] Instituto de Tecnología de Tokio
2-12-1 Ookayama, Meguro-ku
Tokyo 152-8552, Japón
tsurumi2@is.titech.ac.jp
ARXiv
Resumen
El algoritmo de análisis de comunidad propuesto por Clauset, Newman, y Moore (algoritmo CNM) encuentran estructuras de comunidad en las redes sociales. Por desgracia, el algoritmo CNM no se escala bien y su uso está prácticamente limitado a las redes cuyos tamaños son de hasta 500.000 nodos. En el documento se identifica que esta ineficiencia se debe a la fusión de las comunidades de manera desequilibrada. El artículo presenta tres tipos de indicadores (índice de consolidación) para controlar el proceso de análisis de la comunidad tratando de equilibrar los tamaños de las comunidades que se pueden fusionar. Tres matices de los algoritmos CNM se construyen para ser incorporados en esas métricas. La técnica propuesta se prueban s utilizando conjuntos de datos obtenidos a partir de un servicio de red social que alberga 5,5 millones de usuarios existente. Todos los métodos muestran una dramática mejora de la eficiencia de la ejecución en comparación con el algoritmo original CNM y muestra una alta capacidad de ampliación. El método más rápido procesa una red con 1 millón de nodos en 5 minutos y una red con 4 millones de nodos en 35 minutos, respectivamente. Otra procesa una red con 500.000 nodos en 50 minutos (7 veces más rápido que el algoritmo original), encuentra estructuras de la comunidad que ha mejorado la modularidad y báscula a una red con 5,5 millones.
Figura 3: Nuestras implementaciones de comunidades. Una comunidad mantiene un enlace a sus comunidades vecinas en una lista de comunidades pares y un par que tiene un máximo valor de ∆Q.
Figura 4: Mezcla de c1 y c5 en la Figura 3 producida una nueva comunidad c7. Durante la mezcla, los pares de comunidades para la fusión actualizando sus valores de Q.
Figura 5. Red Small-World, generada con Pajek, de 1000 nodos con probabilidad de enlace del 0,5.
Figura 6. El algoritmo WT detectó 43 comunidades
