Dinámica y construcción de grupos de colaboración en Wikipedia

Minería del grafo de Wikipedia: La estructura dinámica de la memoria colectiva

De Volodymyr Miz


Este es el blog que acompaña a nuestro próximo trabajo de investigación (pronto en arXiv); Trabajo conjunto con Kirell Benzi, Benjamin Ricaud y Pierre Vandergheynst (EPFL, LTS2). Aquí, nos centramos en los resultados, omitiendo los detalles del algoritmo y la implementación.

Introducción

Wikipedia es una gran fuente de análisis de datos debido a su destacada escala y la estructura del grafo. Decenas de millones de visitantes lo navegan a diario, dejando su huella en la Web. La combinación de la estructura del grafo de Wikipedia y la actividad del visitante en las páginas nos da el grafo dinámico - el grafo con señales de la serie de tiempo en los nodos. La naturaleza dinámica del grafo hace que el problema de análisis a gran escala sea bastante complicado.

En el artículo original analizamos el grafo de Wikipedia. El objetivo es detectar eventos y recuerdos colectivos utilizando la actividad de los visitantes de Wikipedia. Utilizamos un enfoque basado en grafos para construir nuestro modelo. El modelo computacional se inspira en la plasticidad sináptica y en la teoría de Hebbian.

No es sorprendente que no pudiéramos incluir todos los resultados en el trabajo. Aparte de eso, PDF es un formato bastante pobre para comunicar los hallazgos de la investigación. El objetivo de este post es mostrar los resultados de manera interactiva. Al leer el artículo y esta publicación, le recomendamos que abra los grafos, que aparezcan en todas partes en esta publicación y que juegue con ellos: haga clic con el botón de zoom, haga clic, mueva, busque y seleccione. Esta es de lejos la forma más divertida de sumergirnos en los principales resultados de nuestro trabajo.

Los grafos son interactivos

1. Haga clic en cualquier grafo de este post para abrirlo en una nueva ventana.
2. Haga zoom, haga clic en los nodos, busque las páginas por nombre, resalte los grupos por color.
• Al hacer clic en un nodo, se seleccionan todos los vecinos.
• Cuando selecciona un clúster, selecciona todos los nodos de este clúster.
• La lista de nodos seleccionados aparece a la derecha.

Funciona mejor en la última versión de Chrome. NO intente abrir los grafos en un smartphone. Los grafos son demasiado grandes y puede tardar una eternidad en renderizarlos.

Conjunto de datos

Los conjuntos de datos originales están disponibles públicamente en el sitio web de Wikimedia. Tomamos los volcados SQL de los artículos de Wikipedia en inglés para crear el grafo. La actividad visitante es el número de visitas por página por hora. Consideramos el período de 02:00, 23 de septiembre de 2014 hasta las 23:00, 30 de abril de 2015. Los detalles de pre-procesamiento se describen en nuestro artículo en la sección Dataset.

Dinámica de la red Wikipedia

7 meses de dinámica Wikipedia graph

En el trabajo se supone que la dinámica del grafo puede afectar su estructura. Aplicamos la regla de actualización, basada en la señal en los nodos, para observar este efecto. Aquí mostramos que el grafo de Wikipedia puede auto-organizarse en los conjuntos de comunidades significativas de los nodos, si tenemos en cuenta la dinámica de actividad de los visitantes de la gráfica. Haga clic en el grafo de la derecha y explore el resultado por sí mismo.

Este grafo es el resultado de la dinámica de 7 meses de actividad de los visitantes en Wikipedia. Aquí puede encontrar los principales eventos que se han llevado a cabo durante el período considerado. Los eventos estables o programados, como torneos, ceremonias de premios, concursos y festividades más populares forman grandes grupos. Los eventos inestables o inesperados, como incidentes y accidentes, se agrupan en pequeños grupos. A pesar de que, este grafo proporciona un buen resumen de los patrones dinámicos, sólo podemos ver el resultado final. Lo que es más importante, es obtener información sobre la dinámica del grafo en el tiempo. ¿Cómo emergen los agrupamientos, evolucionan y desaparecen? Para responder a esta pregunta, elegimos un evento en particular y observamos su dinámica en detalles.

Dinámica de un evento: campeonato de la NFL

Con el fin de comprender la dinámica de la evolución del grafo, elegimos uno de los eventos más populares, destacado en la Wikipedia en inglés - el campeonato de la NFL. Consideramos la temporada 2014-2015. La parcela está a la derecha (haga clic para ampliar). Para la interpretabilidad de la trama extraímos 30 equipos de la NFL de 485 páginas en el grupo original. La línea de tiempo muestra la actividad general del grupo durante el período de 7 meses. La línea de tiempo de la dinámica del grafo y la evolución del cluster NFL se ilustra en la fila superior. Refleja el interés de los fanáticos de la NFL en el campeonato. El grupo es pequeño y escaso al principio del campeonato y se vuelve más denso y más grande, acercándose a la fecha final del juego. El comportamiento de los visitantes de Wikipedia durante el día del juego final Super Bowl es excepcional. La actividad de los aficionados de la NFL es mucho mayor, en comparación con la actividad de otros usuarios de Wikipedia. Hace una analogía con la vida real, cuando durante las finales los fans se convierten en la gente más activa en las calles.



El campeonato de la NFL es sólo un ejemplo de un evento detectado y su evolución. Puede explorar los grafos de la actividad mensual y consultar otros clústeres de eventos detectados. El número total de eventos detectados es 172. Haga clic en los grafos siguientes para abrir una versión interactiva y explorar por sí mismo.

      Octubre       Noviembre      Diciembre         Enero               Febrero           Marzo           Abril

El clúster NFL es un buen ejemplo de un evento estable, representado como uno de los clusters más grandes en el grafo resultante. ¿Qué pasa con los eventos no programados, como ataques y otros accidentes?

Memoria colectiva

Los eventos traumáticos, como ataques terroristas, accidentes aéreos, guerras y conflictos, a menudo nos recuerdan el pasado. Estos recuerdos son a menudo comunes para un grupo de personas en una comunidad social. Esa es la razón por la que se llaman recuerdos colectivos. Nuestro enfoque permite detectar estos recuerdos y sirve como un modelo general para la emergencia de la memoria colectiva. Proporcionamos los ejemplos de 3 eventos, detectados entre los demás.

Ejemplos de memorias colectivas se presentan en la siguiente tabla. Para mostrar los detalles de las memorias colectivas detectadas, seleccionamos 3 eventos particulares entre los otros detectados: Ferguson disturbio (segunda ola - 24 de noviembre de 2014), Charlie Hebdo ataque (07 de enero 2015), vuelo de Germanwings 9525 accidente de avión (24 de marzo , 2015). La fila superior contiene los grupos extraídos de memorias colectivas para cada uno de los eventos discutidos. La fila inferior muestra la actividad detallada de cada página en los clústeres.

Disturbios en Ferguson		Ataque a Charlie Hebdo		Caída del Germanwings 9525

Vemos que los eventos centrales desencadenan recuerdos relevantes. Los disturbios de Ferguson nos recuerdan otros disturbios, disparos de gente inocente, e incluso nos lleva de regreso a la esclavitud en los Estados Unidos. Charlie Hebdo tiroteo tiene vínculos con otros ataques terroristas, derramamiento de sangre, y las agencias de aplicación de la ley. El accidente de Germanwings está rodeado por el denso grupo de los otros accidentes aéreos, lo que indica que los accidentes de vuelo están completamente estructurados en Wikipedia.

Aunque, podemos ver un poco de ruido en los racimos. El ruido es relevante para los temas principales de los conglomerados y no afecta la formación del conglomerado. Normalmente, la fuente principal del ruido es un nodo, que es relevante para varios grupos de eventos. Por ejemplo, el grupo de disturbios de Ferguson contiene el grupo nodo anónimo. Este nodo enlaza otro gran grupo de empresas líderes en tecnología y comercio electrónico. En este caso, el primer aumento constante de la actividad es causado por la página de compras en línea, ya que el día más rentable para las tiendas en línea se detectó el 11/11/2014. Otro ejemplo del ruido está en el racimo de Germanwings. La causa principal del ruido es la página del día - 24 de marzo - que contiene la mayoría de los acontecimientos históricos notables.

A pesar de que el ruido es causado por páginas bastante populares, el algoritmo sigue siendo capaz de localizar los eventos más pequeños y crear clusters relevantes. Para detectar eventos más pequeños, como los presentados en los ejemplos, se utilizó una ventana de tiempo menor de una semana. Los pequeños eventos aún se pueden encontrar en los grafos dinámicos mensuales, presentados en la sección anterior de la tabla de línea de tiempo. Revise los grafos y busque los eventos de su interés.

Conclusiones

Wikipedia puede decirnos más de lo que está escrito en sus páginas. Es una gran fuente de datos para la investigación colectiva del comportamiento humano. Sin embargo, la naturaleza dinámica de los datos estructurados por grafos genera nuevos retos para la ciencia de los datos y el aprendizaje automático. En el artículo propusimos un nuevo método para la detección de patrones en grafos dinámicos a gran escala. Aplicamos el método a los conjuntos de datos de Wikipedia. Hemos logrado detectar patrones dinámicos en términos de eventos y recuerdos colectivos en Wikipedia usando la combinación del grafo de hipervínculos y la actividad de los visitantes en el sitio web. El siguiente paso es mejorar la parte de filtrado del algoritmo para disminuir la cantidad de ruido, descrita en la sección de memoria colectiva de este post.

Herramientas y código

Hacemos todos los experimentos utilizando Apache Spark GraphX. El código está escrito en Scala y disponible en GitHub. El pre-procesamiento de datos se puede hacer usando el código Python, disponible en otro repositorio de GitHub.

Expresiones de gratitud

Me gustaría dar las gracias a Michaël Defferrard por fructíferas discusiones y sugerencias útiles.