Stanley Milgran, fue un psicólogo social estadounidense, que creo el concepto de: «Los seis grados de concepto de separación», basándose en el  «experimento del pequeño mundo» en el cual rastreó cadenas de conocidos en los Estados Unidos. En el experimento, Milgram envió varios paquetes a 160 personas aleatorias que vivían en Omaha, Nebraska, pidiéndoles que remitieran el paquete a un amigo o conocido que pensaban que acercaría el paquete a un individuo final, un corredor de bolsa de Boston, Massachusetts.

Cada «iniciador» recibió instrucciones de enviar una carpeta a través de la Oficina de Correos de los Estados Unidos a un destinatario, pero con algunas reglas. Los iniciadores sólo podían enviar el paquete a alguien que realmente conocieran personalmente y que coincidiera con el primer nombre. Al hacerlo, cada participante ordenó a su destinatario que enviara por correo el paquete a una de las personas conocidas de este último con las mismas instrucciones, con la esperanza de que su conocido pudiera por casualidad, conocer al destinatario objetivo.

Al final del experimento,  la entrega de cada paquete solamente llevó, como promedio, entre cinco y siete intermediarios, lo que hizo famosa la frase «seis grados de separación», en el argot popular, dando incluso el nombre a una película.

Facebook, en el 2008,  realizo el calculo (page rank) de las conexiones promedio entre todos sus usuarios y el resultado fue 4,74, mejorando aun el promedio de 6 establecido por Milgran.

Ahora si por nuestra cuenta queremos comprobar las conexiones entre personas, les recomiendo la pagina del Oraculo de Bacon:  https://oracleofbacon.org/movielinks.php

Sabemos quien es Kevin Bacon (el actor de Footloose, el Hombre Invisible y muchas otras). La pagina lleva su nombre porque es el actor con mayor numero de conexiones entre los demás actores (compañeros de trabajo), es decir tiene la mayor centralidad de grado.

sm2

La pagina tiene casi 20 años, y toma los datos del IMDB, la base de datos de las películas, pero ha mejorado en dos aspectos. El primero es que los criterios están abiertos para consultar el numero de conexiones entres dos actores distintos a Kevin Bacon, y el segundo es que la base del IMDB, es ahora global y no solo de películas de Hollywoood.

Hice la prueba entre dos artistas ecuatorianos: Julio Jaramillo y Maria Elisa Camargo  (recalco que ambos son ecuatorianos), y el numero de conexiones fue de 3. Esto a pesar de que Julio Jaramillo, lleva 40 años fallecido.

oraculo

La rama que estudia las conexiones entre individuos es el análisis de redes sociales,  y se utiliza activamente en sociología, antropología, ciencia política, gestión organizacional y medios de comunicación.  En muchos casos el análisis de redes sociales se fundamenta en el estudio de los agentes en la estructura de la red, para ello se hace un análisis de las medidas de centralidad de los actores de la propia red social con el objetivo de ver las relaciones de poder, de protagonismo, confianza y la detección de comunidades y grupos.

Los conceptos de analisis de redes sociales, son aplicados a través de algoritmos computacionales,  y nos pueden permitir descubrir como están conformadas redes sociales tales como: Facebook, Twitter, Likendin, Youtube, Google plus y demás, ya sea propias,  de una marca, negocio o celebridad. Esto con el fin de detectar los usuarios mas influyentes de esa red, las comunidades que se forman alrededor de un tema o tópico de interés y como se propagan los mensajes en las distintas comunidades conformadas en las redes sociales, entre otros puntos.

 

Los medios sociales anotados geográficamente son extremadamente valiosos para la recuperación moderna de la información. Sin embargo,  los usuarios de redes sociales rara vez publican información de localización. conforman su red social.

geo

El paper: Geotagging One Hundred Million Twitter Accounts with Total Variation Minimization, de  Ryan Compton, David Jurgens y David Allen, ofrece un nuevo enfoque para solucionar este problema, proponiendo un algoritmo que  infiere la ubicación de un usuario desconocido, a partir de ubicaciones de los amigos con los que se conecta a través  de menciones en tweets,  y que conforman su red social.

gep1

Donde f = (f1; fn) es la locación estimada para cada usuario y  L es el set de usuarios, d es la distancia geodésica y wij, los pesos equivalentes al mínimo número de menciones.

El enfoque busca una red tal que la suma sobre todas las distancias geográficas entre usuarios conectados sea lo más pequeña posible. Esta suma se conoce como la variación total.

Metodología.

Se construyó una red social, G = (V; E), con usuarios como vértices y @menciones entre usuarios como aristas, usando  10% de la muestra de  tweets públicos  de Abril 2012 hasta Abril del  2014., con un peso de  76,9TB de datos, con 25.312.399.718 de @menciones. Se filtraron las menciones reciprocas, para conformar una red de  1.034.362.407 enlaces y 110.893.747 usuarios.  Del  número total de usuarios, el subtotal con localizaciones confirmadas vía GPS o auto-informes es 24.545.425.  Los usuarios con ubicaciones conocidas por GPS constituyen sólo una pequeña porción de las redes de menciones.

En cada iteración, el algoritmo actualiza simultáneamente la ubicación de cada usuario con la mediana l1 multivariante de las ubicaciones de sus amigos. Sólo después de que todas las actualizaciones estén completas comunicamos nuestros resultados a través de la red.

El framework Apache Spark se utilizó para implementar el algoritmo en una arquitectura Big Data. Permite distribuir los datos en la memoria del clúster haciendo uso de conjuntos de datos distribuidos resilientes (denominados RDD) y operando en estos conjuntos de datos, con código Scala.

geo2

La  red y las locaciones de usuarios se almacenan en los RDDs edgeList y userLocations., los cálculos de estos RDD hacen uso de todos los recursos de la CPU del clúster disponibles. El algoritmo se implementa con un simple map y un filtro. La comunicación de las ubicaciones actualizadas a través de la red se logra con una combinación en la lista de vértices, seguida de un groupByKey, que establece una lista de adyacencias para el siguiente mapa.

Análisis de resultados

El algoritmo fue ejecutado en la red bidireccional y los resultados se informan después de 5 iteraciones. El número de usuarios geo codificados después de cada iteración es el siguiente:

geo3

La probabilidad de que un usuario sea geo codificado por el método planteado aumenta cuando existe un incremento un nivel de actividad de la función. Una gran fracción de usuarios  pierde el interés en Twitter después de generar un pequeño número de Tweets, lo que dificulta su localización calculada.

geo5

Para evaluar la cobertura, se examinaron 4.835.561.225 tweets recogidos entre el 2013-01-01 y el 2013-04-07. Estos tweets fueron generados por 117.215.282 usuarios. El método fue capaz de geo codificar el 89% de los tweets. Podría aumentar el porcentaje si todas las ubicaciones reportadas no-vacías no fueran ambiguas.

geo6

Para la precisión se realizo una validación cruzada, tomando un 10% del set de  12.297.785 usuarios que revelaron su posición GPS.  Después de 5 iteraciones del algoritmo, se pudo inferir la locación de 966.515 usuarios, con una Desviación absoluta mediana (median error) de 6,33 kms .

Conclusiones

  • El uso de Apache Spark está justificado por el gran volumen de datos a ser procesados para la conformación de las redes y el cálculo de las distancias geográficas.
  • El hecho que se pueda inferir las locaciones de usuarios, a partir de datos públicos, permite que se  analicen nuevos algoritmos para el cálculo de las distancias geográficas, con mayor precisión y con mejor cobertura.
  • Implementar métodos para eliminar datos de localizaciones (auto-informes) que sean ambiguos, ya que generan errores en el procesamiento de las distancias de usuarios.
  • Se conseguiría mejor cobertura si el método considera que la relación por menciones sea unidireccional.