Mapa de Internet Bashny.Net

Tomado de aquí
Hola a todos!

Quiero presentarles un mapa de Internet o el resultado de la agrupación de más de 350 mil sitios de acuerdo con el usuario navega entre ellos. El tamaño del círculo es determinado por el tráfico del sitio, color - nacionalidad y ubicación en el mapa - vincula a otros sitios. Si dos sitios tienen un flujo constante de usuarios entre ellos, entonces van a "probar" a permanecer cerca uno del otro. Sobre la terminación del algoritmo, el mapa se puede ver grupos de sitios (clusters) están unidos por los usuarios comunes.





Por ejemplo, si escribe en el habrahabr.ru búsqueda, podemos ver que dirty.ru y leprosorium.ru en la misma "constelación" y sin embargo, lejos livejournal.ru. Esto sugiere que los que están leyendo este texto, y con una alta probabilidad de visitar estos sitios (en relación con el usuario de Internet ruso promedio por supuesto).

Un ejemplo aún más interesante de la agrupación se puede ver en la parte inferior del mapa, entre Japón y púrpura amarillento Brasil: hay un tamaño pornostrana conjunto comparable con todo Euronet. Curiosamente, ser lo suficientemente competente en la materia, dentro de un gran pornoklastera puede distinguir subgrupos temáticos más pequeño.

Para aquellos interesados ​​en una breve descripción técnica - la bienvenida bajo la
corte
Ingeniería parte

Todo el proyecto está escrito en C #, y consta de tres partes: un programa de agrupamiento, el programa de generación de azulejos y sitio web. Cada parte merece especial consideración y, si hay interés, podría entonces nos dicen más sobre ellos.



Los datos de referencia se obtuvieron de Alexa, que representan un registro de asistencia, aguas arriba y aguas abajo (transiciones usuarios aguas arriba - de dónde venían, aguas abajo - donde hizo). Después de la normalización, obtenemos un grafo no dirigido ponderado con vértices y 350.000 más de 2 millones de dólares. Las costillas.

Contando este gráfico - un problema computacional compleja, por lo que fue escrito por un módulo especial para la GPU, pero afortunadamente no lo necesitamos. Después de optimizaciones difíciles estafando a todos tomaron un par de semanas de trabajo continuo de un poderoso, pero sigue siendo una plancha doméstica.

Hablando simplemente, el algoritmo fue sitios incrementales en el mapa de acuerdo con las fuerzas que actúan sobre ellos. Muchos usuarios transiciones - una poderosa fuerza tratando de reunir a los sitios; Si los sitios están demasiado cerca, se inicia la fuerza de repulsión, etc. Más detalles se pueden encontrar en este reports-archive.adm.cs.cmu.edu/anon/1998/CMU-CS-98-189.pdf trabajo

El principal problema era la enorme complejidad computacional de este algoritmo. Después de resolver el problema "cabeza" en cada paso debe calcularse superposición de fuerzas para cada sitio, es decir, calcular la potencia para cada par de sitios, y estos pares de alrededor de 122 millones de dólares. (bueno para un paso, ¿no?). Por lo tanto, se llevó a cabo duro y lleno paralelización algoritmo de optimización. Afortunadamente plataforma .net era sorprendentemente bueno para este tipo de diversiones.

El segundo paso es la generación de azulejos. Azulejos - una pequeña imagen de 256x256 píxeles que componen la imagen de un mapa de google maps, Yandex y otros servicios. En general, nada complicado - Generar cuadro grande, cortado en cuadrados de tamaño deseado, el negocio de alguna manera. Pero estas imágenes era casi 30 millones. Aunque sólo sea para copiar o eliminar un directorio con azulejos en las ventanas que tarda dos días. Y verter en acoger un tema aparte.

La tercera fase - la eliminatoria motor de google maps, poner las piezas juntas, y conseguir que se muestre un mapa. Aquí, en general, no hay nada difícil, aunque hubo algunas dificultades con las proyecciones y el posicionamiento de la tarjeta.

La última etapa - la elección de alojamiento y liberación. Aquí, también, no fue sin aventura. Ahora se convierte en una nube de Amazon y que era mucho más fácil y más barato de lo que había imaginado.

En general, he acumulado cierta experiencia, y yo estaré encantado de compartir con una comunidad respetada. Por supuesto, en general, nada especial, Habré son proyectos muy interesantes y soluciones triviales, pero aún así, creo que, para muchos puede ser divertido.

También espero que cualquier idea, comentario, crítica - cualquier regeneración!

Fuente: