Crawlers for Social Networks & Structural Analysis of Twitter

Debido al gran crecimiento que han tenido las redes sociales (Open Social Networks OSN), por ejemplo se menciona a Facebook con más de 800 millones de usuarios, es básicamente imposible tener una copia de la imagen de la estructura de cada red y que sea mantenida con información al día.

La primera razón que brindan como motivación para su investigación es el entendimiento de las características fundamentales de las redes sociales como leyes de potencias en grados de distribución o propiedades de mundos pequeños. Esta información les permitiría reflexionar sobre las similitudes y diferencias entre las redes de tipo OSN y también conocer información sobre ellas y la dinámica de sus comunidades.

La segunda motivación se concentra en la capacidad de crear modelos generativos para las OSNs tal que pequeñas redes representativas puedan ser simuladas para entender su dinámica y validar los análisis teóricos.

Para la construcción de los crawlers se tomaron en cuenta los siguientes puntos:

• Cobertura de nodo: El número de nodos visto como proporción del total de nodos presentes en la red social después de un número determinado de pasos del algoritmo.
• Capacidad de interpretación de las acciones de marcas por espías o fisgones de terceros: Es importante que las búsquedas de una marca en un proveedor de red social no pueda ser interpretado de tal forma que se pueda hacer una predicción de sus acciones.
• Uso de tokens de autenticación de la red social: Debido a la existencia de un límite de peticiones que pueden ser llevadas a cabo a los servidores, se trata de maximizar las peticiones que pueden llevar a cabo cada token autenticado.
• Facilidad de ser atrapado en un cluster local del que no sea fácil salir: Tener en cuenta que debido a la naturaleza de redes como Twitter, si no se cuenta con backtracking en el algoritmo, se puede quedar varado.
• Facilidad de paralelización: Se busca construir varios crawlers que trabajen de forma paralela para obtener la información requerida. Debe ser capaz de escalar hacia arriba como hacia abajo dependiendo de los recursos de procesamiento disponibles.

Por su parte, los algoritmos considerados para crear los crawlers fueron los siguientes:

• Random Walk: Se inicia en un nodo, explora todos sus vecinos y de manera aleatoria elige uno para continuar explorando. Puede quedarse atorado si un nodo solo tiene enlaces entrantes o tiene deshabilitada la exploración debido a las restricciones de seguridad. Aunque es fácil de implementar y paralelizable, es susceptible a visitar el mismo nodo varias veces cuando atraviesa la red.
• Random Walk with Backtrack: Para evitar quedar atascado, si no se encuentran enlaces para continuar se hace backtrack de un paso y se elige de nuevo un nodo al azar.
• Metropolis Hastings Random Walk (MHRW): Las caminatas aleatorias tienden a favorecer el visitar nodos de grados mayores. Se asegura un muestreo uniforme de la red.
• Breadth First Search (BFS): La búsqueda toma un nodo inicial y pone a todos sus vecinos en una cola de nodos visibles que todavía no son explorados. Después toma al primer nodo en la cola y lo explora, pone a todos sus vecinos que todavía no estén presentes en la cola y continúa el proceso. Es fácil de implementar pero requiere una gran cantidad de capacidad de almacenamiento para la cola. No es fácil de paralelizar al tener a todos los nodos compartiendo la misma cola.
• Randomized Search: Al igual que el anterior se toma un nodo inicial y se pone a sus vecinos en una lista. En lugar de tomar al primer nodo, se toma uno al azar de la lista. Se debe asegurar que los nodos que ya fueron visitados no sean incluidos de nuevo en la lista y solo entradas únicas existen en ella.
• Greedy: Se basa en el BFS pero la cola esta ordenada por el grado de enlaces salientes de cada nodo respecto al grafo explorado. A pesar de ser fácil de implementar y de paralelizar, se debe calcular el grado de enlaces salientes de manera constante.
• Lottery: Es similar al Greedy pero el nodo que será explorado se escoge de manera probabilística. Los nodos con mayor grado de enlaces salientes tienen mayor probabilidad. Al igual que Greedy, se necesitan calcular las probabilidades de manera constante.
• Hypothetical Greedy: Es similar al Greedy pero en lugar de basarse en el grado de enlaces salientes sobre el grafo explorado, se emplea el grafo entero. Se requiere un token extra de autenticación para llevarse a cabo.

La siguiente tabla muestra las características evaluadas en cada uno de los algoritmos:

Dentro de los resultados presentados encontraron algunos fenómenos como el hecho de que hacer el BFS como inferior al visitar los nodos como se muestra en la siguiente figura:

Al final decidieron quedarse con la implementación de Random Search para mantener bajos los requerimientos de procesamiento, optimizar el uso de tokens de autenticación y prever el espionaje de terceros.

La base de datos que contiene la información de descargada de Twitter o de cualquier otra red social se espera que crezca en gran dimensión. Otra consideración tomada en cuenta consiste en que la información esta limitada por lo que se puede obtener mediante los tokens de autenticación.

Para asegurar que no se repitan nodos que ya fueron procesados, siempre se lleva registro de ellos y van cambiando simplemente su lugar. En la siguiente figura se muestra la arquitectura general del proceso de la base de datos.

Se hacen algunas reflexiones dependiendo del número de seguidores como que los famosos tienen muchos más seguidores que su grupo de amigos. Otro caso parece ser el de los bots con pocos seguidores y que siguen a muchas personas. Esto se ve en la siguiente figura:

Otros resultados consisten en el número de usuarios por país y por zona horaria presentados a continuación:

En general el artículo se centra en las diferentes técnicas que evaluaron según sus criterios para llevar a cabo el descubrimiento de la estructura de una red social. Se menciona que al momento de la escritura, se tenían 5 millones de nodos, 950 millones de conexiones y 16 millones de perfiles capturados.

Saroop, A., & Karnik, A. (2011). Crawlers for social networks & structural analysis of Twitter. 2011 IEEE 5th International Conference on Internet Multimedia Systems Architecture and Application (pp. 1–8). IEEE. doi:10.1109/IMSAA.2011.6156368