Привет всем!

Хочу представить вам Карту Интернета или результат кластеризации более чем 350 тысяч сайтов в соответствии с переходами пользователей между ними. Размер круга определяется посещаемостью сайта, цвет – национальной принадлежностью, а положение на карте – его связями с другими сайтами. Если два сайта имеют стабильный поток пользователей между ними, то они будут «стараться» расположиться ближе друг к другу. После завершения работы алгоритма, на карте можно наблюдать скопления сайтов (кластеры) объединенные общими пользователями.



Например, если ввести в поиск habrahabr.ru, то можно увидеть, что dirty.ru и leprosorium.ru в том же «созвездии», а еще подальше livejournal.ru. Это говорит о том, что тот, кто сейчас читает этот текст, также с высокой вероятностью посещает эти сайты (относительно усредненного пользователя Рунета конечно).

Еще более интересный пример кластеризации можно увидеть внизу карты, между фиолетовой Японией и желтоватой Бразилией: там расположилась целая порнострана по размерам сопоставимая со всем Евронетом. Интересно, что будучи достаточно компетентным в рассматриваемом вопросе, внутри большого порнокластера можно различить тематические подкластеры меньшего размера.

Тем, кого интересует краткое техническое описание – добро пожаловать под кат

Инженерная часть

Весь проект написан на языке C# и состоит из трех частей: программа кластеризации, программа генерации тайлов и веб-сайт. Каждая часть заслуживает отдельного рассмотрения и, если будет интерес, я бы мог потом рассказать о них подробнее.



Исходные данные были взяты у Алексы, они представляют собой записи о посещаемости, upstream и downstream переходах юзеров (upstream – откуда пришли, downstream – куда ушли). После нормализации мы получаем взвешенный ненаправленный граф с 350 тысячами вершин и более 2 млн. ребер.

Обсчет такого графа – сложная вычислительная задача, поэтому был написан специальный модуль для GPU, но к счастью он не понадобился. После хитрых оптимизаций весь обсчет занял несколько недель непрерывной работы мощного, но все-таки бытового железа.

Если говорить упрощенно, то работа алгоритма заключалась в пошаговом перемещении сайтов на карте в соответствии с силами действующими на них. Много переходов пользователей – сильная сила старается сблизить сайты; если сайты расположились слишком близко, то начинает работать сила отталкивания и т.д. Подробнее можно посмотреть в этой работе reports-archive.adm.cs.cmu.edu/anon/1998/CMU-CS-98-189.pdf

Основная проблема заключалась в колоссальной вычислительной сложности подобного алгоритма. Ведь при решении задачи «в лоб», на каждом шаге нужно вычислять суперпозицию сил для каждого сайта, т.е. вычислять силы для каждой пары сайтов, а таких пар около 122 млрд. (неплохо для одного шага, правда?). Поэтому была проведена жесткая оптимизация алгоритма и полное распараллеливание вычислений. К счастью платформа .net оказалась на удивление хорошей для подобного рода забав.

Вторым этапом идет генерация тайлов. Тайл – это маленькая картинка 256х256 пикселей из которых состоит изображение карты на google maps, yandex и других сервисах. В общем-то, ничего сложного – сгенерил большую картинку, разрезал ее на квадраты нужного размера, делов-то. Но таких картинок оказалось почти 30 млн. Даже просто скопировать или удалить каталог с тайлами в windows занимает два дня. А залить их на хостинг отдельная проблема.

Третий этап – прикрутить движок google maps, собрать все воедино и заставить его показывать карту. Здесь в общем-то нет ничего сложного, хотя были некоторые сложности с проекциями и позиционированием карты.

Последний этап – выбор хостинга и релиз. Здесь тоже не обошлось без приключений. Сейчас все вертится в облаке Амазона и это оказалось гораздо проще и дешевле, чем я себе представлял.

В общем, у меня накопился некоторый опыт, и я буду рад поделится им с уважаемым сообществом. Конечно в целом ничего особенного, на Хабре бывают действительно интересные проекты и нетривиальные решения, но все же, я думаю, многим это может быть интересно.

Также я буду рад любым идеям, отзывам, критике – любому фидбеку!

Спасибо всем за теплые слова! Для меня было очень важно получить поддержку от профессионального сообщества, от людей, которые не только видят результат, но понимают какая огромная работа была проделана для его достижения. Также спасибо Хабру за то, что в Рунете есть площадка объединяющая всех нас!

Продолжение: Веб архитектура Карты Интернета