El programa que extrae la información usando la API de Twitter está usando exploración aleatoria. Es decir, selecciona aleatoriamente el siguiente hash tag a solicitar. Este enfoque resulta muy práctico y nos permite descubrir muchos hash tags. Por ejemplo, después de haber ejecutado el programa algunas horas, este ha visitado alrededor de 3,000 nodos pero ha descubierto alrededor de 150,000. Esto nos da un grafo bastante incompleto, lo cual puede ser frustrante al momento de ejecutar algoritmos como el de encontrar la ruta más corta, ya que es muy probable que si seleccionamos dos nodos al azar sólo haya una ruta entre ellos. Lo ideal sería poder visitar la mayoría de los nodos que conocemos; el problema es que el realizar las peticiones de tweets es una operación costosa.
Por ello es que decidí modificar el programa para visitar sólo aquellos hash tags que luzcan más “relevantes”. La definición de relevancia es un tanto arbitraria y la definí intuitivamente. Obtuve algunas métricas con los nodos que he visitado hasta el momento para obtener un parámetro que no fuera del todo subjetivo.
NOTA: las siguientes conclusiones están basadas en los aproximadamente 3,000 hash tags que visite usando el programa descrito en secciones anteriores. Por lo que estás conclusiones pueden ser incompletas e incluso incorrectas, pero son un buen inicio para los propósitos de este tutorial.
El término hash tag y nodo son equivalentes en la siguiente discusión.
La primer métrica es el número de vecinos de un nodo: en promedio tienen 133 vecinos. En la siguiente gráfica observamos que más del 40% de los nodos tienen 90 o más vecinos. Esto concuerda con nuestros resultados (sólo 3,000 visitados pero ya llevamos 150.000 descubiertos); es decir, el universo de nodos descubiertos crece muy rápidamente conforme vamos visitando más nodos.
Es interesante ver como hay también un buen porcentaje de nodos con muy pocos vecinos, tal vez esto se deba a hash tags esporádicos.
Bueno, regresando a la pregunta de qué es un nodo relevante, decidí ver la fortaleza entre dos hash tags, y esto es simplemente cuantas veces aparece un hash tag en la búsqueda de otro. Por ejemplo, cuando buscamos #Toluca, de los 400 tweets obtenidos, el hash tag #futbol apareció 20 veces; en este caso digo que la fortaleza de #Toluca a #futbol es 20.
La siguiente gráfica muestra la distribución de las fortalezas de los enlaces. Noten como el 70% de los enlaces sólo tienen fortaleza 1, pareciera que la mayoría de las relaciones entre hash tags son esporádicas. Sin embargo, existe un porcentaje considerable de enlaces con fortaleza igual o mayor a 9.
Precisamente está es la métrica que utilicé para decidir que nodos visitar. Sólo visitaremos aquellos nodos que estén muy conectados a alguno de los nodos que hayamos visitado. Obviamente hay que cuidar no ser muy restrictivo que lleguemos al punto de no encontrar más nodos. Para ello obtuve la siguiente gráfica donde podemos ver que aproximadamente la mitad de los nodos están conectados a por lo menos otro nodo con fortaleza 9 o mayor. Lo cual es un buen indicador que aún cuando estamos reduciendo el espacio de búsqueda, seguiremos encontrando nuevos nodos.
Primero probé con enlaces de fortaleza 4, pero aún así el número de nodos conocidos crecía muy rápidamente. Así que ajuste este valor a 10.
El código lo pueden encontrar aquí. El archivo tweets_old.zip contiene la información usada para las métricas. El archivo tweet_graph.py calcula y despliega las métricas. Tweet_search.py es el programa de extracción de tweets con las modificaciones mencionadas.
